改进分配器算法实现的建议

Question

我有一个Visual Studio 2008 C ++应用程序，在其中使用了自定义分配器来为标准容器提供内存，以便它们的内存来自内存映射文件而不是堆。该分配器用于4种不同的用例：

1. 104字节固定大小结构std::vector< SomeType, MyAllocator< SomeType > > foo; 2. 200字节固定大小结构 3. 304字节固定大小结构 4. n字节字符串std::basic_string< char, std::char_traits< char >, MyAllocator< char > > strn;

我需要能够为每个用例大约分配32MB。

分配器使用指向分配大小的指针的std::map跟踪内存使用情况。typedef std::map< void*, size_t > SuperBlock; 每个SuperBlock代表4MB的内存。

如果一个SuperBlock的空间不足，则会有一个std::vector< SuperBlock >的容器，以便创建另一个SuperBlock。

分配器的算法如下所示：

1. 对于每个SuperBlock：末尾是否有空间？将分配放置在那里。（快速） 2. 如果没有，请搜索每个SuperBlock中是否具有足够大小的空闲空间，并将分配放置在那里。（慢） 3. 仍然没有吗？分配另一个SuperBlock并将分配放在新SuperBlock的开头。

不幸的是，步骤2在一段时间后可能变得非常慢。随着对象的复制和临时变量的销毁，我会遇到许多内存碎片化问题。这将导致在内存结构中进行大量深度搜索。由于我有一定量的内存可用（请参见下面的说明），因此碎片化是一个问题。

是否有人能够提出可以加快此算法速度的改进方法？我需要两个单独的算法（一个用于固定大小的分配，一个用于字符串分配）吗？

注：对于那些需要原因的人：我将在Windows Mobile中使用此算法，其中堆有32MB的进程槽限制。因此，通常的std::allocator行不通。我需要将分配放置在1GB的大型内存区域中以获得足够的空间，这就是这个算法所做的。

- PaulH

Answer 1

你能为每个不同的固定大小类型分配单独的内存分配池吗？这样就不会出现任何碎片，因为分配的对象始终对齐在n字节边界上。当然，这对于可变长度的字符串没有帮助。

在Alexandrescu的《Modern C++设计》中有一个小对象分配的例子，说明了这个原则，可能会给你一些启示。

- Tim Martin

---

这是加速大部分分配的好方法。谢谢您的想法。+1 - PaulH

Answer 2

对于固定大小的对象，您可以创建一个固定大小的分配器。基本上，您需要分配块，将其划分为适当大小的子块，并使用结果创建链接列表。如果有可用的内存，则从这样的块中进行分配是O(1)(只需从列表中删除第一个元素并返回指向它的指针)，回收也是如此(将块添加到空闲列表中)。在分配期间，如果列表为空，请获取新的超级块，将其划分并将所有块添加到列表中。

对于可变大小的列表，您可以通过仅分配已知大小的块来简化它：32字节、64字节、128字节、512字节。您需要分析内存使用情况以得出不同的桶，以便不浪费太多内存。对于大型对象，您可以返回到动态大小分配模式，这将会很慢，但希望大型对象的数量有限。

- David Rodríguez - dribeas

---

好主意将固定大小和可变大小结合起来。我刚刚实现了这个，确实非常快。谢谢。 - PaulH

你应该仔细阅读Matthieu M.的回答，它更加完整、相当不错，并且解决了你在部署自己的分配器时会遇到的许多问题。 - David Rodríguez - dribeas

Answer 3

在 Tim 的回答基础上，我个人会使用类似 BiBOP（Binary Balanced Pooled Allocator）的东西。

基本思想很简单：使用固定大小的池。

这其中还有一些细节需要处理。

首先，池的大小通常是固定的。它取决于您的分配例程，通常如果您知道所在的操作系统使用 malloc 时至少映射4KB，则使用这个值。对于内存映射文件，您可能可以增加此值。

固定大小池的优点在于它可以有效地防止碎片化。所有页面都具有相同的大小，您可以轻松地将一个空的256字节页面回收成一个128字节页面。

对于大对象仍然存在一些碎片化，这些对象通常是在此系统之外分配的。但是它很低，特别是如果你将大对象放入页面大小的倍数中，这样内存将更容易回收利用。

其次，如何处理池？使用链表。

页面通常是无类型的（本身），因此您必须准备新页面并将“回收”的页面放入可用页面列表中。

对于每个尺寸类别，您需要一个“已占用”页面列表，在其中分配了内存。对于每个页面，您需要保留：

- 分配大小（针对此页面） - 已分配对象的数量（用于检查是否为空） - 指向第一个空闲单元的指针 - 指向前一个和后一个页面的指针（可能指向列表的“头”）

每个空闲单元本身都是指向下一个空闲单元的指针（或索引，具体取决于您的大小）。

给定尺寸的“已占用”页面列表非常容易管理：

- 在删除时：如果您清空了页面，则从列表中删除它并将其推入回收页面，否则更新此页面的空闲单元列表（注意：通常可以通过地址上的模数运算来找到当前页面的开头） - 在插入时：从头开始搜索，一旦找到未满的页面，请将其移动到列表前面（如果尚未），然后插入您的项目

这种方案在内存方面真的很有效率，只需要一个页面用于索引。

对于多线程/多进程应用程序，您需要添加同步功能（通常每个页面使用一个互斥锁），以防止出现问题。如果有兴趣，您可以看看 Google 的 tcmalloc（尝试查找另一个页面而不是阻塞，使用线程本地高速缓存来记住您最后使用的页面）。

话虽如此，你尝试过 Boost.Interprocess 吗？它提供了分配器。

- Matthieu M.

Answer 4

对于固定大小的数据，您可以轻松使用小型内存分配器类型的分配器，在其中分配一个大块，然后将其分成固定大小的块。然后，您创建一个指向可用块的指针向量，并在分配/释放时进行弹出/推入操作。这非常快速。

对于可变长度的数据，情况就比较难了：您要么必须处理搜索可用连续空间，要么使用其他方法。您可以考虑维护另一个按块大小排序的所有空闲节点的映射，以便您可以lower_bound该映射，如果下一个可用节点只比所需大小大5％，则返回它，而不是尝试找到完全相同大小的可用空间。

- Mark B

Answer 5

对于可变大小的项目，我的倾向是尽可能避免直接持有数据指针，而是保留句柄。每个句柄都是超级块的索引和超级块内项目的索引。每个超级块都会分配自上而下的项目列表和自下而上的项目。每个项目的分配都将在其长度之前进行，并且由其所代表的项目的索引；使用一个位来指示项目是否“固定”。

如果一个项目适合在最后分配的项目之后，只需分配它即可。如果它会撞到固定的项目，将下一个分配标记移过固定的项目，找到更高的固定项目，然后再次尝试分配。如果该项目会与项目列表发生冲突，但某处有足够的空闲空间，则压缩块的内容（如果有一个或多个项目被固定，最好使用另一个超级块，如果有一个可用）。根据使用模式，可能希望从仅压缩自上次收集以来添加的内容开始；如果这不能提供足够的空间，则压缩所有内容。

当然，如果只有几种离散的项目大小，可以使用简单的固定大小块分配器。

- supercat

---

这看起来非常有趣。如果我需要更快地分配大型可变大小的块，我可能会尝试这个。+1 - PaulH

@PaulH：我不知道你对于最坏情况时间和平均时间的需求是什么，但你可能想要调整一下你的超级块的大小。另外，如果你有一些先验知识，知道某些分配的生命周期很短，而其他的生命周期较长，那么将预期寿命相似的对象放入同一个超级块中会很有帮助。理想情况是，一些超级块会经常填满，但在它们填满时，其中大部分的内容已被删除，只需要复制很少的内容。 - supercat

Answer 6

我同意Tim的观点 - 使用内存池来避免碎片化。

然而，通过在向量中存储指针而不是对象，也许可以避免一些繁琐的操作，比如ptr_vector？

- Douglas Leeder

---

哇！对于那些可以使用ptr_vector的类型进行切换确实产生了巨大的影响。谢谢！ - PaulH