如何避免在 64 位指针上浪费内存
How to avoid wasting memory on 64-bit pointers
我希望就如何处理我即将进行的设计提出一些 high-level 的建议。
我的问题的直截了当的方法将导致数以百万计的指针。在 64 位系统上，这些可能是 64 位指针。但就我的应用程序而言，我认为我只需要一个 32 位地址 space。但是，我仍然希望系统能够利用 64 位处理器算法（假设这是我在 64 位系统上通过 运行 得到的结果）。
更多背景知识
我正在实现一个 tree-like 数据结构，其中每个 "node" 包含一个 8 字节的有效负载，但还需要指向四个相邻节点的指针（parent、left-child, middle-child, right-child).在使用 64 位指针的 64 位系统上，这相当于 32 个字节，仅用于 link 将 8 字节的有效负载写入树中——"linking overhead" 为 400%。
数据结构将包含数百万个这样的节点，但我的应用程序不需要太多内存，所以所有这些 64 位指针看起来很浪费。该怎么办？有没有办法在 64 位系统上使用 32 位指针？
我考虑过
将有效载荷存储在一个数组中，这样一个索引暗示（并且被暗示）一个 "tree address" 并且给定索引的邻居可以用简单的算法计算出来指数。不幸的是，这需要我根据树的最大深度来调整数组的大小，这是我事先不知道的，并且由于较低级别的空节点元素可能会产生更大的内存开销，因为不是树的所有分支去同样的深度。
将节点存储在一个足够大的数组中以容纳所有节点，然后使用索引而不是指向 link 邻居的指针。 AFAIK 这里的主要缺点是每个节点都需要数组的基地址才能找到它的邻居。所以他们要么需要存储它（超过一百万次），要么需要在每次函数调用时传递它。我不喜欢这样。
假设所有这些指针的most-significant 32位都为零，否则抛出异常，只存储least-significant 32位。所以需要的指针可以按需重构。系统很可能会使用超过 4GB，但进程永远不会。我只是假设指针从进程 base-address 偏移并且不知道这在通用平台（Windows、Linux、OSX).
存储 64 位 this 和指向邻居的 64 位指针之间的 差异，假设这个差异将在int32_t 的范围（如果不是则抛出）。然后任何节点都可以通过将该偏移量添加到 this.
有什么建议吗？关于最后一个想法（我目前认为这是我的最佳候选者），我可以假设在一个使用少于 2GB 的进程中，动态分配的 objects 将在 2GB 之内吗？或者根本不需要？
您断言 64 位系统必然 必须具有 64 位指针是不正确的。 C++ 标准没有做出这样的断言。
事实上，不同的指针类型可以有不同的大小：sizeof(double*)可能与sizeof(int*)不同。
简短回答：不要对任何 C++ 指针的大小做出任何假设。
我觉得您想构建自己的内存管理框架。
如果在 Linux 上，您可以考虑使用（并编译）x32 ABI。恕我直言，这是您问题的首选解决方案。
或者，不要使用指针，而是索引到一个巨大的数组（或 C++ 中的 std::vector），它可以是全局变量或 static 变量。管理单个巨大的堆分配节点数组，并使用节点索引而不是指向节点的指针。所以就像你的§2，但由于数组是全局或 static 数据，你不需要将它传递到任何地方。
（我猜优化编译器将能够生成聪明的代码，这几乎和使用指针一样高效）
结合题目中的思路2和思路4，将所有的节点放入一个大数组中，存储例如int32_t neighborOffset = neighborIndex - thisIndex。然后你可以从 *(this+neighborOffset) 得到邻居。这摆脱了 2 和 4 的 disadvantages/assumptions。
您可以通过利用内存区域的对齐来找到数组的基地址来消除 (2) 的缺点 "automatically"。例如，如果您想支持最多 4 GB 的节点，请确保您的节点阵列从 4GB 边界开始。
然后在地址为 addr 的节点内，您可以确定另一个位于 index 的地址为 addr & -(1UL << 32) + index。
这是公认解决方案 "relative" 的 "absolute" 变体。此解决方案的一个优点是 index 在树中始终具有相同的含义，而在相对解决方案中，您确实需要 (node_address, index) 对来解释索引（当然，您可以 也在有用的相对场景中使用绝对索引）。这意味着当你复制一个节点时，你不需要调整它包含的任何索引值。
"relative"解决方案相对于该解决方案在其索引中也丢失了 1 个有效索引位，因为它需要存储有符号的偏移量，因此使用 32 位索引，您只能支持 2^31 个节点（假设尾随零位完全压缩，否则只有 2^31 字节 个节点）。
您还可以将基础树结构（例如，指向根的指针以及您在节点本身之外拥有的任何簿记）存储在 4GB 地址处，这意味着任何节点都可以跳转到关联的基础结构无需遍历所有父指针或其他任何内容。
最后，您还可以在树本身中利用这种对齐方式来 "implicitly" 存储其他指针。例如，父节点可能存储在 N 字节对齐的边界，然后所有子节点都存储在同一个 N 字节块中，因此他们知道他们的父节点 "implicitly"。这有多可行取决于您的树的动态程度、扇出的变化程度等。
您可以通过编写自己的分配器来完成此类事情，该分配器使用 mmap 分配适当对齐的块（通常只保留大量虚拟地址 space 然后分配其中的块根据需要） - 通过 hint 参数或仅通过保留足够大的区域来保证您在该区域的某处获得所需的对齐。与公认的解决方案相比，需要弄乱分配器是主要缺点，但如果这是您程序中的主要数据结构，那可能是值得的。当您控制分配器时，您还有其他优势：如果您知道所有节点都分配在 2^N 字节边界上，您可以 "compress" 您的索引进一步，因为您知道低 N 位将始终为零，因此使用 32 位索引，如果您知道它们是 32 字节对齐的，您实际上可以存储 2^(32+5) = 2^37 个节点。
这些技巧实际上只在 64 位程序中可行，因为有大量的虚拟地址 space 可用，所以在某种程度上 64 位给予也带走了。
我希望就如何处理我即将进行的设计提出一些 high-level 的建议。
我的问题的直截了当的方法将导致数以百万计的指针。在 64 位系统上，这些可能是 64 位指针。但就我的应用程序而言，我认为我只需要一个 32 位地址 space。但是，我仍然希望系统能够利用 64 位处理器算法（假设这是我在 64 位系统上通过 运行 得到的结果）。
更多背景知识
我正在实现一个 tree-like 数据结构，其中每个 "node" 包含一个 8 字节的有效负载，但还需要指向四个相邻节点的指针（parent、left-child, middle-child, right-child).在使用 64 位指针的 64 位系统上，这相当于 32 个字节，仅用于 link 将 8 字节的有效负载写入树中——"linking overhead" 为 400%。
数据结构将包含数百万个这样的节点，但我的应用程序不需要太多内存，所以所有这些 64 位指针看起来很浪费。该怎么办？有没有办法在 64 位系统上使用 32 位指针？
我考虑过
将有效载荷存储在一个数组中，这样一个索引暗示（并且被暗示）一个 "tree address" 并且给定索引的邻居可以用简单的算法计算出来指数。不幸的是，这需要我根据树的最大深度来调整数组的大小，这是我事先不知道的，并且由于较低级别的空节点元素可能会产生更大的内存开销，因为不是树的所有分支去同样的深度。
将节点存储在一个足够大的数组中以容纳所有节点，然后使用索引而不是指向 link 邻居的指针。 AFAIK 这里的主要缺点是每个节点都需要数组的基地址才能找到它的邻居。所以他们要么需要存储它（超过一百万次），要么需要在每次函数调用时传递它。我不喜欢这样。
假设所有这些指针的most-significant 32位都为零，否则抛出异常，只存储least-significant 32位。所以需要的指针可以按需重构。系统很可能会使用超过 4GB，但进程永远不会。我只是假设指针从进程 base-address 偏移并且不知道这在通用平台（Windows、Linux、OSX).
存储 64 位
this和指向邻居的 64 位指针之间的 差异，假设这个差异将在int32_t的范围（如果不是则抛出）。然后任何节点都可以通过将该偏移量添加到this. 来找到它的邻居
有什么建议吗？关于最后一个想法（我目前认为这是我的最佳候选者），我可以假设在一个使用少于 2GB 的进程中，动态分配的 objects 将在 2GB 之内吗？或者根本不需要？
您断言 64 位系统必然 必须具有 64 位指针是不正确的。 C++ 标准没有做出这样的断言。
事实上，不同的指针类型可以有不同的大小：sizeof(double*)可能与sizeof(int*)不同。
简短回答：不要对任何 C++ 指针的大小做出任何假设。
我觉得您想构建自己的内存管理框架。
如果在 Linux 上，您可以考虑使用（并编译）x32 ABI。恕我直言，这是您问题的首选解决方案。
或者，不要使用指针，而是索引到一个巨大的数组（或 C++ 中的 std::vector），它可以是全局变量或 static 变量。管理单个巨大的堆分配节点数组，并使用节点索引而不是指向节点的指针。所以就像你的§2，但由于数组是全局或 static 数据，你不需要将它传递到任何地方。
（我猜优化编译器将能够生成聪明的代码，这几乎和使用指针一样高效）
结合题目中的思路2和思路4，将所有的节点放入一个大数组中，存储例如int32_t neighborOffset = neighborIndex - thisIndex。然后你可以从 *(this+neighborOffset) 得到邻居。这摆脱了 2 和 4 的 disadvantages/assumptions。
您可以通过利用内存区域的对齐来找到数组的基地址来消除 (2) 的缺点 "automatically"。例如，如果您想支持最多 4 GB 的节点，请确保您的节点阵列从 4GB 边界开始。
然后在地址为 addr 的节点内，您可以确定另一个位于 index 的地址为 addr & -(1UL << 32) + index。
这是公认解决方案 "relative" 的 "absolute" 变体。此解决方案的一个优点是 index 在树中始终具有相同的含义，而在相对解决方案中，您确实需要 (node_address, index) 对来解释索引（当然，您可以 也在有用的相对场景中使用绝对索引）。这意味着当你复制一个节点时，你不需要调整它包含的任何索引值。
"relative"解决方案相对于该解决方案在其索引中也丢失了 1 个有效索引位，因为它需要存储有符号的偏移量，因此使用 32 位索引，您只能支持 2^31 个节点（假设尾随零位完全压缩，否则只有 2^31 字节 个节点）。
您还可以将基础树结构（例如，指向根的指针以及您在节点本身之外拥有的任何簿记）存储在 4GB 地址处，这意味着任何节点都可以跳转到关联的基础结构无需遍历所有父指针或其他任何内容。
最后，您还可以在树本身中利用这种对齐方式来 "implicitly" 存储其他指针。例如，父节点可能存储在 N 字节对齐的边界，然后所有子节点都存储在同一个 N 字节块中，因此他们知道他们的父节点 "implicitly"。这有多可行取决于您的树的动态程度、扇出的变化程度等。
您可以通过编写自己的分配器来完成此类事情，该分配器使用 mmap 分配适当对齐的块（通常只保留大量虚拟地址 space 然后分配其中的块根据需要） - 通过 hint 参数或仅通过保留足够大的区域来保证您在该区域的某处获得所需的对齐。与公认的解决方案相比，需要弄乱分配器是主要缺点，但如果这是您程序中的主要数据结构，那可能是值得的。当您控制分配器时，您还有其他优势：如果您知道所有节点都分配在 2^N 字节边界上，您可以 "compress" 您的索引进一步，因为您知道低 N 位将始终为零，因此使用 32 位索引，如果您知道它们是 32 字节对齐的，您实际上可以存储 2^(32+5) = 2^37 个节点。
这些技巧实际上只在 64 位程序中可行，因为有大量的虚拟地址 space 可用，所以在某种程度上 64 位给予也带走了。