Small Mem Alloc: The SGI-STL way

September 25, 2007 – 1:25 pm

最初接触 C 语言的时候就对它 malloc 的内存管理感到奇怪,那么多 mallocfree 调用,申请内存的大小也没有什么规律,怎么能高效地管理呢?后来大概了解了下,感觉似乎产生碎片之类的情况是不可避免的,要不如果让算法太过复杂的话,调用一次 malloc 的成本也又太高了,这样反而让我平时写程序的时候调用 malloc 都显得有些心有余悸。

不过事情始终是不可避免的,为了少产生碎片,C 程序员们都倾向于一次申请大块的内存吧。但是到了 C++ 里面情况又变了,有许多小对象(诸如智能指针或者 Functor 一类的对象)如果在 heap 上分配空间,效率就会降下来。这个时候最好的解决办法应该就是对小对象采用特殊的内存分配机制了。

最近在侯捷先生的 STL 源码剖析 一书中看到关于 SGI 的 STL 中小对象内存分配机制的讲解,在这里做下笔记,一来加深理解,二来方便以后查阅。

SGI 的 STL 也是使用经典的 freelist 的方式来管理内存块的,但是为了避免产生碎片,它将分配的内存大小按照 8 的倍数对齐,并为 8、16、24、32、……、128 这些大小的内存块各自维护一个 freelist ,而对于大于 128 bytes 的内存申请工作直接交给 malloc 。流程如下图所示:

这样分配和释放都在 freelist 里面进行,不会让 malloc 面对一大堆小块内存而焦头烂额,不过如果每次 freelist 缺少空闲内存都直接去调用 malloc 申请新内存的话,其实碎片的问题并没有得到根本性的解决。为此,这里还有一个内存池的机制。

freelist 是采用链表讲空闲的小块内存串联起来,它的内存资源来源于内存池。内存池则是维护一整块连续的空间,它直接向 malloc 要内存。为了尽量减轻 malloc 的负担,内存池会尝试进行尽量大块(当然要考虑实际的需求,不能无节制地滥用)内存的申请,因为 malloc 实际上是为管理大块内存而优化的。

内存池申请内存的流程是这样:

  • freelist 在没有可用的内存块的时候,就像内存池要内存块,通常是要 20 个单位(就是那个特定的 freelist 所管理的节点的大小)内存块那么大的空间。
  • 如果内存池空间足够,那么就直接分配。
  • 否则,再看是否够分配请求的至少一个单位块那么多的内存,如果够,则尽量多地分配内存给 freelist (当然,肯定是少于 20 个块了)。
  • 如果连一个块都分配不出来,那么就需要重新申请内存了。
  • 重新申请内存之前,先把自己剩下的那点零头内存分配到合适的 freelist 里面去。(想想,为什么要这么做?)
  • 调用 malloc 申请内存,如果成功最好,如果失败,还有一招:尝试去找单位块更大的 freelist ,看能否找到可用的内存块,因为更大的 freelist (比如 24 ,如果有空闲的内存块的话)至少能够为较小的 freelist (比如 16)分配一块的单位内存块出来。当然这已经是情况危急,系统内存耗尽的时候了,如果这种尝试都失败了,就只有 fall back 到系统默认行为了:期望发生奇迹,有 memory handle 能够从某处讨得一些内存,或者等着 bad_alloc “嘭”一声从深深的调用栈中弹飞出来。

最后是,为什么一定要在重新申请内存之前把零头分配出去呢?因为不分配出去的话就会泄漏掉,内存池只是维护一个连续的区块,而重新分配的内存并不能保证和原来的内存的连续性,所以只好交给不要求连续性而用链表进行管理的 freelist 接管。而正好零头内存的大小肯定刚好是某一个 freelist 的单位块的大小,这个也是很容易证明的,所以直接把那一块内存交给那个合适的 freelist 就好了。

以上便是 SGI 的 STL 里面管理小块内存的方法,如果想更深入更细节地了解一下,可以参考 STL 源码剖析 或者直接去看相应的源代码。

下次我会介绍 Modern C++ Design 一书里面讲到的 Loki 库里面所使用的小对象内存管理的办法,相比于 SGI STL 的做法,那里用到了更多 Modern 的 C++ 特性,应该对于 Modern 的 C++ 程序员们更具有亲和力一些。 :)

  1. 9 Responses to “Small Mem Alloc: The SGI-STL way”

  2. 那么,顶一下再收藏!^^

    By shawn on Sep 25, 2007

  3. 老兄的流程图用什么工具做的?好pp!

    By uniqueman on Sep 25, 2007

  4. to uniqueman:
    谢谢!这个是用 Inkscape 画的。

    By pluskid on Sep 26, 2007

  5. Hi pluskid, 内存管理有很多方法的,你说的是buddy system吧,根据2的power或者Fibonacci序列。

    By Jack on Sep 27, 2007

  6. to Jack:
    恩,是的,我是说的一种特殊的方法。我想大概管理小块内存主要就是这样的方法了吧。听说 TAOCP 里面对内存管理也有比较详细的介绍,有机会要找来看一下。

    By pluskid on Sep 27, 2007

  7. http://nextlib.lifegoo.com/user/jack/article/2617

    P.S: blog上的图很不错 :)

    By Jack on Sep 27, 2007

  8. >> 我想大概管理小块内存主要就是这样的方法了吧。

    我最近翻了一下算法导论,看了Fibonacci Heap, 其实主要看insert/remove/merge 这些操作的比重。

    By Jack on Sep 27, 2007

  9. Thank you, Jack!

    By pluskid on Sep 28, 2007

  1. 1 Trackback(s)

  2. Sep 30, 2007: Free Mind » Blog Archive » Small Mem Alloc: The Loki Way

Post a Comment