0

假设我有一个程序（例如 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. 使用第二种方法，我会有一个页面列表（向量？数组？），然后查找当前页面，然后在所选页面上使用类似于 1 的方法。

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

所以我的问题是：解决此类问题的最有效方法是什么？是选项 1、选项 2 还是我在这里没有考虑过的其他选项？是否需要/足以为现实情况得出结论？ 我了解不同的操作可能会执行不同的操作，但我正在寻找一个整体指标。

4

6 回答 6

1

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

但是，如果不确切知道您使用什么指标，就很难界定“最有效”。

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

分配：

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

1 查看那个大小的对象的释放链接列表，看看是否有任何东西被释放，如果是，则取第一个释放

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

2.1 分配一个由 N 个对象组成的数组，该数组的大小是被分配的。

3 返回所需大小的下一个空闲对象。

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

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

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

释放：

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

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

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

于 2010-06-29T12:45:35.137 回答
0

从您的问题中不清楚为什么需要提前分配一大块内存而不是根据需要为每个对象分配内存。我假设您将它用作连续数组。malloc否则，在需要时对每个对象的内存更有意义。

如果它确实充当数组，则malloc-ing another block 会为您提供另一块内存，您必须通过另一个指针（在您的情况下page2）访问该内存块。因此它不再位于连续块上，您不能将这两个块用作一个数组的一部分。

realloc另一方面，分配一个连续的内存块。如果有单独的块，您可以将它用作单个数组并执行各种指针运算是不可能的。realloc当您实际上想要缩小正在使用的块时也很有用，但这可能不是您在这里想要做的。

因此，如果您将其用作数组，realloc则基本上是更好的选择。否则，没有任何问题malloc。实际上，您可能希望为malloc您创建的每个对象使用，而不必跟踪和微观管理内存块。

于 2010-06-29T12:36:14.507 回答
0

您尚未提供有关您正在试验的平台的任何详细信息。例如和realloc之间存在一些性能差异。LinuxWindows

根据情况，如果它不能增长当前内存块并将旧内存复制到realloc新内存块，则可能必须分配一个新内存块，这很昂贵。如果您真的不需要连续的内存块，则应避免使用.realloc

我的建议是使用第二种方法，或者使用自定义分配器（您可以实现一个简单的伙伴分配器 [2]）。

您还可以使用更高级的内存分配器，例如

于 2010-06-29T12:41:16.750 回答
0

在最坏的情况下，选项 1 可能会导致原始内存的“移动”，这是一项额外的工作。如果不移动内存，无论如何都会初始化“额外”大小，这也是其他工作。所以realloc会被 malloc 方法“打败”，但要说多少，你应该做测试（我认为当内存请求完成时系统的状态存在偏差）。

根据您期望 realloc/malloc 必须执行多少次，它可能是一个有用的想法或一个无用的想法。无论如何我都会使用 malloc 。

免费策略取决于实施。要释放整个页面，“遍历”它们就足够了；我会使用链接的“页面”而不是数组：将 sizeof(void *) 添加到“页面”大小，您可以使用额外的字节来存储指向下一页的指针。

如果您必须释放位于其中一个页面中任何位置的单个对象，它会变得有点复杂。我的想法是保留一个非顺序自由“块”/“插槽”的列表（适合容纳任何对象）。当请求一个新的“块”时，首先从这个列表中弹出一个值；如果它是空的，那么你会在最后一个使用页面中获得下一个“插槽”，最终触发一个新页面。释放一个对象，意味着只是将空槽地址放入堆栈/列表中（无论您喜欢使用什么）。

于 2010-06-29T12:44:42.427 回答
0

在 linux（可能还有其他 POSIX 系统）中，还有第三种可能性，即使用带有shm_open. 一旦您访问这样的区域，它就会被零初始化，但是您从不访问的 AFAIK 页面是免费的，如果它不仅仅是您保留的虚拟内存中的地址范围。因此，您可以在执行的开始（比您需要的更多）保留一大块内存，然后从一开始就逐渐填充它。

于 2010-06-29T13:03:44.770 回答
0

解决此类问题的最有效方法是什么？是选项 1、选项 2 还是我在这里没有考虑过的其他选项？是否需要/足以为现实情况得出结论？

选项 1。为了提高效率，NEW_SIZE 必须非线性地依赖旧大小。否则，由于冗余复制，您可能会遇到 realloc() 的 O(n^2) 性能。我通常会这样做new_size = old_size + old_size/4（增加 25%），因为理论上最好new_size = old_size*2在最坏的情况下保留太多未使用的内存。

选项 2。它应该更优化，因为大多数现代操作系统（感谢 C++ 的 STL）已经针对大量小内存分配进行了很好的优化。小分配导致内存碎片的机会更小。

最后，这一切都取决于您分配新对象的频率以及您如何处理释放。如果你用#1 分配了很多，你会在扩展时有一些冗余复制，但释放很简单，因为所有对象都在同一页中。如果您需要释放/重用对象，使用#2 您将花费一些时间浏览页面列表。

根据我的经验，#2 更好，因为在大内存块周围移动可能会增加堆碎片率。#2 还允许使用指针，因为对象不会更改它们在内存中的位置（尽管对于某些应用程序，我更喜欢使用 pool_id/index 对而不是原始指针）。如果以后浏览页面成为问题，则可能过于优化。

In the end you should also consider option #3: libc. I think that libc's malloc() is efficient enough for many many tasks. Please test it before investing more of your time. Unless you are stuck on some backward *NIX, there should be no problem using malloc() for every smallish object. I used custom memory management only when I needed to put objects in exotic places (e.g. shm or mmap). Keep in mind the multi-threading too: malloc()/realloc()/free() generally are already optimized and MT-ready; you would have to reimplement the optimizations anew to avoid threads being constantly colliding on memory management. And if you want to have memory pools or zones, there are already bunch of libraries for that too.

于 2010-06-29T15:29:56.490 回答