Small Mem Alloc: The Loki Way

September 30, 2007 – 8:03 pm

Modern C++ Design 一书中有 Loki 库中用于小对象内存分配方法的详细介绍,不过书中用的 Loki 库的版本和我下到的版本应该不一样(我下载到的是 0.1.6 版),所以中间有一些细微的差别,不过总体上是一样的。

整体架构是这样:最上层是 SmallObjectSmallValueObject ,分别用于多态和 POD 情况下的小对象的基类,只要继承自他们就可以拥有小对象内存分配的特殊的 newdelete 函数。这两个类的区别就是是否有 virtual 的析构函数。如果是 POD 则不需要虚拟西沟函数,并且 SmallValueObject 这个时候把析构函数设置为 protected 避免误用基类指针来调用之类的析构函数。

两个类有一个共同的基类 SmallObjectBase ,因为其实小块内存管理的大部分代码是相同的。而真正的管理工作其实由一个叫做 SmallObjAllocator 类的一个 Singleton 来完成。这便是其上的包装代码,要使用这个架构非常简单,只要让你的类继承自 SmallObject 或者 SmallValueObject 即可。

不过我们关心的是它底下的 SmallObjAllocator 到底如何来完成内存管理的:这就需要介绍 ChunkFixedAllocator 了。其实底层的组织方式和前面提到的 SGI STL 里面用的 freelist 是类似的。

Chunk 就是以类似于 freelist 的方式管理一堆 block ,FixedAllocator 则管理一堆的 Chunk ,专门分配某一固定大小的内存,SmallObjAllocator 则建立一个 pool ,存放许多 FixedAllocator 以满足不同大小的对象的构建。书中描述的是按需填充 pool ,并在使用的时候用二分查找定位。不过我找到的源代码里面已经没有使用这种策略了,也许是觉得效率不太好吧。这里 Loki 也采用了直接定位的方式,就是将要分配的空间的大小按照一个值对齐(这里默认值是 4),然后直接将这个数值映射(除以 4)为 pool 里面的对应的 FixedAllocator 的 index ,所以一开始就为各个大小的小对象做好了 FixedAllocator 了。

const std::size_t allocCount = GetOffset(maxObjectSize, objectAlignSize);
pool_ = new FixedAllocator[allocCount];
for (std::size_t i = 0; i < allocCount; ++i)
    pool_[i].Initialize((i+1)*objectAlignSize, pageSize);

其中 GetOffset 就是用于对齐的:

(numBytes + alignment-1)/alignment

这里 FixedAllocator + Chunk 一起充当了 SGI STL 方式里面的 freelist 的工作。为什么需要两个类呢?这里存在一个设计上的问题:Chunk 并不是以普通指针来串联 freelist 的,而是一一个 byte 大小的变量,以块内偏移的方式来串联 free 的 block ,这样就不能跨 Chunk 串联了,并且还限制了 Chunk 的大小。这本来有一个优点:不会出现用于装维护信息的变量比要申请的变量所占的空间大的情况,如果用一个 4 字节的指针,那么一个 block 至少要 4 个字节,就限制了申请内存的最小单位为 4 个字节,而许多小对象实际上是“空对象”,只占用一个字节的空间就够了。这应该对书上描述的管理 FixedAllocator 的方式有用,但是现在实际的代码里面使用对齐到 4 并且预先分配所有的 FixedAllocator 的方法,这样就显得有些多此一举了。关键是这样就带来了一个问题:多个 Chunk 之间无法自己串联起来,于是就需要 FixedAllocator 来管理它们(当然,它还保存诸如分配的单位空间的大小等变量)。FixedAllocator 也没有比较好的管理办法了,它使用一个 vector 来存放 Chunk ,虽然使用了许多缓存技巧,但是仍然有不可避免的情况就是在分配(更严重的是在释放)内存的时候需要一次线性查找来找到对应的 Chunk

总的来说,我觉得 Loki 的这个做法似乎是有些把事情搞复杂了,这样做大概就只有一个优点(当然,在特定的时候也会变成性能瓶颈):被小内存分配器所占用了的内存可以方便地释放回系统内存中,而 SGI STL 那边更趋向于一直由小内存分配器管理那些碎片,以便日后使用。无论如何,我更喜欢 SGI STL 的做法。 :)

  1. 2 Responses to “Small Mem Alloc: The Loki Way”

  2. Fit first算法? 内部碎片和外部碎片管理是内存管理上算法设计上要考虑的吧

    By Jack on Oct 1, 2007

  3. to Jack:
    Not fit first. 经过 round up 以后每个 size (4、8、16、……)有其单独的分配器。

    By pluskid on Oct 1, 2007

Post a Comment