6

我有一个 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. 对于每个超级块：超级块的末端是否有空间？把分配放在那里。（快速地）
  2. 如果没有，则在每个 SuperBlock 中搜索足够大小的空白空间并将分配放在那里。（减缓）
  3. 依然没有？分配另一个 SuperBlock 并将分配放在新 SuperBlock 的开头。

不幸的是，第 2 步可能会在一段时间后变得非常缓慢。随着对象的复制和临时变量的销毁，我得到了很多碎片。这会导致在内存结构中进行大量深度搜索。碎片化存在问题，因为我可以使用的内存有限（请参阅下面的注释）

任何人都可以建议改进这个算法来加快这个过程吗？我是否需要两种单独的算法（一种用于固定大小的分配，一种用于字符串分配器）？

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

4

6 回答 6

6

Can you have a separate memory allocation pool for each different fixed-size type you are allocating? That way there won't be any fragmentation, because the allocated objects will always align on n-byte boundaries. That doesn't help for the variable-length strings, of course.

There's an example of small-object allocation in Alexandrescu's Modern C++ design that illustrates this principle and may give you some ideas.

于 2011-05-17T16:49:42.513 回答
2

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

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

于 2011-05-17T16:57:49.590 回答
2

基于蒂姆的回答，我个人会使用类似于 BiBOP 的东西。

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

对此有一些改进。

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

固定大小的池的优势在于它可以很好地消除碎片。所有页面大小相同，您可以轻松地将空的 256 字节页面回收为 128 字节页面。

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

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

这些页面通常是无类型的（它们本身），因此您有一个页面的空闲列表，可以在其中准备新页面并放置“回收”页面。

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

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

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

简单地管理给定大小的“占用”页面列表：

  • 删除时：如果清空页面，则将其从列表中删除并推送到回收页面中，否则更新该页面的空闲单元列表（注意：找到当前页面的开头通常是一个简单的模运算地址上）
  • 插入时：从头开始搜索，一旦找到非完整页面，将其移动到列表前面（如果还没有）并插入您的项目

这种方案在内存方面确实是高性能的，只保留一个页面用于索引。

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

话虽如此，您是否尝试过 Boost.Interprocess ？它提供分配器。

于 2011-05-17T17:31:34.343 回答
1

For the fixed sizes you can easily use a small memory allocator type of allocator where you allocate a large block that's split into fixed-size chunks. You then create a vector of pointers to available chunks and pop/push as you allocate/free. This is very fast.

For variable length items, it's harder: You either have to deal with searching for available contiguous space or use some other approach. You might consider maintaining another map of all the free nodes ordered by block size, so you can lower_bound the map and if the next available node is say only 5% too big return it instead of trying to find usable available space of the exact size.

于 2011-05-17T16:52:29.410 回答
1

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

但是，您可以通过在向量中存储指针而不是对象来避免一些流失，也许是ptr_vector？

于 2011-05-17T17:03:12.110 回答
1

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

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

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

于 2011-05-17T16:59:17.473 回答