用于提高分配算法的实施意见 [英] suggestions for improving an allocator algorithm implementation

问题描述

我有一个Visual Studio 2008的C ++应用程序，其中我使用了一个自定义的分配器标准容器，使他们的记忆来自于内存映射文件，而不是堆。这个分配器用于4种不同的用例：

I have a Visual Studio 2008 C++ application where I'm using a custom allocator for standard containers such that their memory comes from a Memory Mapped File rather than the heap. This allocator is used for 4 different use cases:

1. 104字节的固定尺寸结构的std ::矢量＆lt; SOMETYPE，MyAllocator＆LT; SOMETYPE＆GT; ＆GT;富;
2. 200字节的固定尺寸结构
3. 304字节的固定尺寸结构
4. n字节的字符串的std :: basic_string的＆LT;焦炭，性病:: char_traits＆LT;焦炭＆gt;中MyAllocator＆LT;焦炭＆GT; ＆GT; STRN;

1. 104-byte fixed size structure std::vector< SomeType, MyAllocator< SomeType > > foo;
2. 200-byte fixed size structure
3. 304-byte fixed size structure
4. n-byte strings std::basic_string< char, std::char_traits< char >, MyAllocator< char > > strn;

我需要能够以大致分配32MB总为每个这些。

I need to be able to allocate roughly 32MB total for each of these.

分配器跟踪使用指针来分配大小的的std ::地图内存使用情况。 的typedef的std ::地图＆LT;无效*，为size_t＆GT;超级块; 每个超级块重新presents 4MB的内存

The allocator tracks memory usage using a std::map of pointers to allocation size. typedef std::map< void*, size_t > SuperBlock; Each SuperBlock represents 4MB of memory.

有一个的std ::矢量＆lt;超级块＆GT; 这万一有超级块是没有足够的空间

There is a std::vector< SuperBlock > of these in case one SuperBlock isn't enough space.

用于分配的算法是这样的：

The algorithm used for the allocator goes like this:

1. 对于每一个超级块：有没有在超级块的最后空间？把分配存在。 （快）
2. 如果没有，每一个超级块中搜索了足够大小的空的空间，并把分配存在。 （慢）
3. 还有什么？分配另一个超级块，并把分配的新超级块的开始。

不幸的是，第2步可以成为一段时间后，非常缓慢。作为对象的拷贝制作和临时变量毁灭，那么我得到了很多的碎片。这将导致大量的深搜索的存储器结构中。碎片是问题，因为我有一个有限的存储空间一起工作（参见下面的注释）

Unfortunately, step 2 can become VERY slow after a while. As copies of objects are made and temporary variables destroyed I get a lot of fragmentation. This causes a lot of deep searching within the memory structure. Fragmentation is in issue as I have a limited amount of memory to work with (see note below)

任何人都可以提出改进算法，将加快这一进程？我需要两个独立的算法（1个用于固定大小的分配，一个用于字符串分配器）？

Can anybody suggest improvements to this algorithm that would speed up the process? Do I need two separate algorithms (1 for the fixed-size allocations and one for the string allocator)?

注意：的对于那些需要一个理由：我使用这种算法，在Windows Mobile，其中有一个32MB的过程插槽限制堆。因此，通常的的std ::分配器将不会削减它。我需要把分配了1GB超大存储区中有足够的空间，这也正是这样做。

Note: For those that need a reason: I'm using this algorithm in Windows Mobile where there's a 32MB process slot limit to the Heap. So, the usual std::allocator won't cut it. I need to put the allocations in the 1GB Large Memory Area to have enough space and that's what this does.

推荐答案

对于固定大小的物体，你可以创建一个固定大小的分配器。基本上你分配块，分割成适当大小的子块，并创建一个链表的结果。从这样的模块分配是O（1）如果有可用内存（只是删除列表中的第一个元素，并返回一个指向它的指针）如同释放（加块空闲列表）。配置过程中，如果列表是空的，抓住了新的超级块，分区，并添加所有块到列表中。

For the fixed sized objects, you can create a fixed sized allocator. Basically you allocate blocks, partition into subblocks of the appropriate size and create a linked list with the result. Allocating from such a block is O(1) if there is memory available (just remove the first element from the list and return a pointer to it) as is deallocation (add the block to the free list). During allocation, if the list is empty, grab a new superblock, partition and add all blocks into the list.

有关的可变大小的列表，您可以通过分配只能阻止已知大小的它简化为固定大小的块：32字节，64字节，128字节，512字节。您必须分析内存使用情况，拿出不同的桶，这样你就不会浪费太多的内存。对于大型的对象，你可以回去了动态的大小分配格局，这将是缓慢的，但希望大对象的数量是有限的。

For the variable sized list, you can simplify it to the fixed size block by allocating only blocks of known sizes: 32 bytes, 64 bytes, 128 bytes, 512 bytes. You will have to analyze the memory usage to come up with the different buckets so that you don't waste too much memory. For large objects, you can go back to a dynamic size allocation pattern, that will be slow, but hopefully the amount of large objects is limited.

这篇关于用于提高分配算法的实施意见的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！