文档介绍：踏雪无痕
SGI STL的内存池
分类: C++ 技术摘录 2012-07-20 11:18 99人阅读评论(0) 收藏举报
stl中各种容器都有一个可选的模板参数:allocator,也就是一个负责内存分配的组件。STL标准规定的allcator被
定义在memory文件中。STL标准规定的allocator只是单纯地封装operator new,效率上有点过意不去。
SGI实现的STL里,所有的容器都使用SGI自己定义的allocator。这个allocator实现了一个small object的内存
池。Loki里为了处理小对象的内存分配,也实现了类似的内存管理机制。
该内存池大致上,就是一大块一大块地从系统获取内存,然后将其分成很多小块以链表的形式链接起来。其内部有
很多不同类型的链表,不同的链表维护不同大小的内存块。每一次客户端要求分配内存时,allcator就根据请求的
大小找到相应的链表(最接近的尺寸),然后从链表里取出内存。当客户端归还内存时,allocator就将这块内存放回
到对应的链表里。
我简单地画了幅图表示整个结构:

allocator内部维护一个链表数组,数组元素全部是链表头指针。链表A每一个节点维护一个8bytes的内存块,链表B
每一个节点维护一个16bytes的内存块。
当客户端请求分配10bytes的内存时,allocator将10调整为最接近的16bytes(只能大于10bytes),然后发现16bytes
这个链表(链表B)里有可用内存块,于是从B里取出一块内存返回。当客户端归还时,allocator找到对应的链表,将
内存重新放回链表B即可。
大致过程就这么简单,也许有人要说用链表维护一块内存,链表本身就会浪费一些内存(在我很早前接触内存池时,
总会看到类似的论点= =|),其实通过一些简单的技巧是完全可以避免的。例如,这里allocator维护了很多内存
块,反正这些内存本身就是闲置的,因此我们就可以直接在这些内存里记录链表的信息(下一个元素)。
还是写点代码详细说下这个小技巧:
struct Obj
     {
        Obj *next;
    }; 
    void *mem = malloc( 100 );
    Obj *header = (Obj*) mem;
1
Obj *header = (Obj*) mem;
    Obj *cur_obj = header;
    Obj *next_obj = cur_obj;
    for( int i = 0; ; ++ i )
    