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

Question

我有一个Visual 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;

我需要能够为每一项分配大约32 of的总数。

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

如果一个std::vector< SuperBlock >没有足够的空间，就会有一个SuperBlock。

用于分配器的算法如下所示：

1. 对于每个SuperBlock:在SuperBlock的末尾是否有空间？把配给放在那里。(快)
2. 如果没有，则在每个SuperBlock中搜索足够大小的空空间，并将分配放在那里。(缓慢)
3. 还是什么都没有？分配另一个SuperBlock并将分配放在新SuperBlock的开头。

不幸的是，步骤2可能会在一段时间后变得非常慢。随着对象的复制和临时变量的销毁，我得到了很多碎片。这在内存结构中引起了大量的深入搜索。碎片是有问题的，因为我有有限的内存来处理(见下面的说明)。

有人能建议改进这个算法来加速这个过程吗？我是否需要两个单独的算法(一个用于固定大小的分配，一个用于字符串分配器)？

注意:对于那些需要一个原因的人:我在Windows中使用这个算法，在这里，Heap有一个32‘m的进程时隙限制。所以，通常的std::allocator不会剪掉它。我需要将分配放在1GB的大内存区域中，以便有足够的空间，这就是它所做的。

Answer 1

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

对于可变大小的列表，可以将其简化为固定大小的块，只分配已知大小的块: 32字节、64字节、128字节、512字节。您必须分析内存使用情况，才能产生不同的存储桶，这样就不会浪费太多内存。对于大型对象，您可以回到动态大小分配模式，这将是缓慢的，但希望大对象的数量是有限的。

Answer 2

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

在Alexandrescu的https://rads.stackoverflow.com/amzn/click/com/0201704315中有一个小对象分配的例子，它说明了这个原理，并可能给你一些想法。

Answer 3

在提姆回答的基础上，我个人会使用类似于BiBOP的东西。

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

这方面有一些改进。

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

固定大小池的优点是它能很好地抵御碎片。所有的页面都是相同大小的，您可以轻松地将一个空的256字节页回收到128字节的页面中。

对于大型对象仍然存在一些碎片，这些对象通常是在此系统之外分配的。但是它很低，特别是如果您将大型对象安装到页面大小的倍数中，这样就可以很容易地回收内存。

第二，如何处理泳池？使用链接列表。

页面通常是非类型化的(自行)，所以您有一个免费的页面列表来准备新的页面并放入“可回收的”页面。

对于每个大小类别，您都有一个“已占用”页的列表，其中已分配了内存。对于您保存的每一页：

• 分配大小(对于此页面)
• 分配对象的数量(检查是否为空)。
• 指向第一个空闲单元格的指针
• 指向上一页和下一页的指针(可能指向列表的“头”)

每个空闲单元本身就是指向下一个自由单元格的指针(或索引，取决于您的大小)。

对给定大小的“已占用”页的列表进行简单管理：

• 删除:如果您清空页面，然后从列表中删除它并将其推入回收的页面中，否则，更新此页面的空闲单元格列表(注意:查找当前页面的开头通常是地址上的简单模块操作)。
• 插入:从头开始搜索，一旦你找到一个非完整的页面，将它移到列表的前面(如果还没有)并插入你的项目。

这种方案实际上是在内存方面表现良好，只保留一个页面进行索引.

对于多线程/多进程应用程序，您将需要添加同步(通常每页一个互斥)，如果您可以从Google的tcmalloc获得灵感(尝试找到另一个页面而不是阻塞，使用线程本地缓存来记住您上次使用的页面)。

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