c++ - 如何避免在 64 位指针上浪费内存

Question

我希望就如何处理我即将进行的设计获得一些高级建议。

解决我的问题的直接方法将导致数以百万计的指针。在 64 位系统上，这些可能是 64 位指针。但就我的应用程序而言，我认为我需要的地址空间不超过 32 位。但是，我仍然希望系统能够利用 64 位处理器算法(假设这是我在 64 位系统上运行所获得的结果)。

更多背景

我正在实现一个树状数据结构，其中每个“节点”包含一个 8 字节的有效负载，但还需要指向四个相邻节点(父节点、左子节点、中子节点、右子节点)的指针。在使用 64 位指针的 64 位系统上，这相当于 32 个字节，仅用于将 8 字节有效负载链接到树中——400% 的“链接开销”。

数据结构将包含数百万个这样的节点，但我的应用程序不需要太多内存，所以所有这些 64 位指针看起来都很浪费。该怎么办？有没有办法在 64 位系统上使用 32 位指针？

我考虑过

1. 将有效负载存储在数组中的方式使得索引暗示(并被暗示)“树地址”，并且给定索引的邻居可以使用该索引的简单算术计算。不幸的是，这需要我根据树的最大深度来调整数组的大小，这是我事先不知道的，并且由于较低级别的空节点元素可能会产生更大的内存开销，因为不是树的所有分支去同样的深度。

2. 将节点存储在一个大到足以容纳所有节点的数组中，然后使用索引而不是指针来链接邻居。 AFAIK 这里的主要缺点是每个节点都需要数组的基地址才能找到它的邻居。所以他们要么需要存储它(超过一百万次)，要么需要在每次函数调用时传递它。我不喜欢这样。

3. 假设所有这些指针的最高 32 位为零，否则抛出异常，并仅存储最低有效的 32 位。所以需要的指针可以按需重构。系统很可能会使用超过 4GB，但进程永远不会。我只是假设指针从进程基地址偏移，并且不知道这在通用平台(Windows、Linux、OSX)上有多安全(如果有的话)。

4. 存储 64 位 this 之间的差异和指向邻居的 64 位指针，假设这个差异将在 int32_t 的范围内(如果不是，则 throw )。然后任何节点都可以通过将该偏移量添加到 this 来找到它的邻居.

有什么建议吗？关于最后一个想法(我目前认为这是我的最佳候选者)，我可以假设在使用小于 2GB 的进程中，动态分配的对象将在 2GB 以内吗？或者根本不需要？

Answer 1

结合问题中的想法 2 和 4，将所有节点放入一个大数组中，并存储例如int32_t neighborOffset = neighborIndex - thisIndex。然后你可以从 *(this+neighborOffset) 获取邻居。这消除了 2 和 4 的缺点/假设。