c - 高效内存重新分配问题

Question

假设我有一个程序(例如 C++)，它分配多个对象，但永远不会大于给定的大小(我们称之为 MAX_OBJECT_SIZE)。

我在堆上还有一个区域(我将其称为“页面”)(用 malloc(REGION_SIZE) 分配，其中 REGION_SIZE >= MAX_OBJECT_SIZE)。
我一直在该页面中保留空间，直到填充的空间等于 PAGE_SIZE(或至少达到 > PAGE_SIZE - MAX_OBJECT_SIZE)。

现在，我想分配更多内存。显然我之前的“页面”还不够。所以我至少有两个选择:

1. 使用 realloc(page, NEW_SIZE)，其中 NEW_SIZE > PAGE_SIZE；
2. 分配一个新的“页面”(page2)并将新对象放在那里。

如果我想要一个自定义分配函数，那么:

1. 使用第一种方法，我会看到我填充了多少，然后将我的新对象放在那里(并将对象的大小添加到我填充的内存变量中)。
2. 使用第二种方法，我会得到一个页面列表( vector ？数组？)，然后查找当前页面，然后在所选页面上使用类似于 1 的方法。

最终，我也需要一种释放内存的方法，但我可以弄清楚那部分。

所以我的问题是:解决此类问题最有效的方法是什么？是选项 1、选项 2 还是其他我没有考虑过的选项？是否需要一个小基准/足以对现实世界的情况得出结论？我知道不同的操作可能会有不同的表现，但我正在寻找一个总体指标。

Answer 1

根据我的经验，选项 2 更容易使用且开销最小。 Realloc不保证它会增加现有内存的大小。而在实践中几乎从来没有这样做过。如果您使用它，您将需要返回并重新映射所有旧对象。这需要您记住分配的每个对象的位置...这可能会带来大量的开销。

但是，如果不确切知道您使用的指标，就很难定义“最高效”。

这是我一直使用的内存管理器。它适用于整个应用程序，而不仅仅是一个对象。

分配:

对于每次分配，确定分配的对象的大小。

1 查看该大小对象的释放链接列表，看看是否有任何内容已被释放，如果是，则获取第一个释放

2 在查找表中查找，如果没有找到

2.1 分配一个由 N 个对象组成的数组，其大小已分配。

3 返回所需大小的下一个自由对象。

3.1 如果数组已满则添加新页面。

N 个对象可以由程序员调整。如果您知道有一百万个 16 字节对象，您可能希望 N 稍高一些。

对于超过某个大小 X 的对象，不要保留数组，而只是分配一个新对象。

免费:

确定对象的大小，将其添加到frees的链接列表中。

如果分配的对象的大小小于指针的大小，则链接列表不需要产生任何内存开销。只需使用已分配的内存来存储节点即可。

此方法的问题是，直到应用程序退出或程序员决定对内存进行碎片整理之前，内存永远不会返回到操作系统。碎片整理是另一篇文章。可以办到。