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

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内存.

std::vector< SuperBlock >如果一个SuperBlock没有足够的空间,则有其中一个.

用于分配器的算法如下:

1. 对于每个SuperBlock:超级块的末尾是否有空格？把分配放在那里.(快速)
2. 如果没有,在每个SuperBlock中搜索足够大的空白空间并将分配放在那里.(慢)
3. 依然没有？分配另一个SuperBlock并将分配放在新SuperBlock的开头.

不幸的是,一段时间后,第2步可能变得非常缓慢.随着对象的复制和临时变量的破坏,我得到了很多碎片.这导致在存储器结构内进行大量深度搜索.碎片存在问题,因为我使用的内存有限(请参阅下面的注释)

任何人都可以建议改进这种算法来加速这个过程吗？我需要两个单独的算法(1个用于固定大小的分配,1个用于字符串分配器)？

注意:对于那些需要理由的人:我在Windows Mobile中使用此算法,其中Heap有32MB的进程槽限制.所以,通常std::allocator不会削减它.我需要将分配放在1GB大内存区域中以获得足够的空间,这就是它的作用.

Answer 1

对于要分配的每种不同的固定大小类型,是否可以有单独的内存分配池？这样就不会有任何碎片,因为分配的对象将始终在n字节边界上对齐.当然,这对可变长度的字符串没有帮助.

在Alexandrescu的Modern C++设计中有一个小对象分配的例子,它说明了这个原理,可能会给你一些想法.

Answer 2

对于固定大小的对象，您可以创建固定大小的分配器。基本上，您分配块，分区为适当大小的子块，并使用结果创建一个链接列表。如果有可用内存（只需从列表中删除第一个元素并返回指向它的指针），那么从这样的块中进行分配的时间复杂度为 O(1)，就像释放（将块添加到空闲列表中）一样。在分配过程中，如果列表为空，则获取一个新的超级块，分区并将所有块添加到列表中。

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