低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx
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维护了很多内存块，反正这些内存本身就是闲置的，因此我们就可以直接在这些内存里记录链表的信息(下一个元素)。
还是写点代码详细说下这个小技巧：
这样，通过header指针和next域，就可以逐块(这里是10byts)地访问mem所指向的内存，而这些链表的节点，都是直接保存在这块内存里的，所以完全没有额外消耗。
我用C模仿着SGI的这个allocator写了个可配置的内存池，在其上按照STL的标准包装了一个allocator，可以直接用于VC自带的STL里。测试代码稍微测试了下，发现在不同的机器上有明显的差距。
posted on 2008-06-12 21:26 Kevin Lynx 阅读(8001) 评论(10) 编辑 收藏 引用 所属分类: c/c++ 、game develop 、通用编程
我自己也曾经做过一个内存池，方法没去比较不知道如何。 我的内存池是一个模板，专门用于产生特定类型的对象。因此构造函数让人制定一次创建的Buffer的尺寸。然后使用平衡树组织了一个不可变大小的池从而获得一个可变大小的池。平衡树的比较由池之间的起始指针的比较结果决定，于是寻找一个指针属于哪个池也比较快。Buffer的尺寸可以根据实际需要调整，我用这个池实现自己的Yacc的时候，发现平衡树最多就三个节点，不过文法数量也不多，仅有100条，不能当压力测试看待。 每一个固定尺寸的池还有一个可变长度实现的堆栈，用于存放空闲位置。这样的话从一个固定尺寸的池获取和删除都是O(1)。 空间浪费在平衡树和这个空闲索引堆栈了。 回复 更多评论
唉 水已经满了 会错过很多东西的 回复 更多评论
以前我也试着这样子去造个轮子，但是到最后发现没有必要,STL这个就是一个free-list，但是如果你的这个用在多线程中就很崩溃的，你想想，不同的桶都有自己的一个琐，这样子琐就会很多，另外增加了复杂度还不讨好，除非在很关键的地方我使用我的内存管理器，其他的地方还是stl吧 回复 更多评论
@关中刀客 STL默认那个内存池。。。STL默认没内存池。SGI的STL里那个内存池不是标准的。VC下的STL就没这个。 回复 更多评论
终于对allocator有一点了解了，自己写的allocator里面放的内存池结构也可以用C++封装吧？还有allocator中的rebind结构是干什么用的呢？ 回复 更多评论
@Gohan rebind可以让allocator<Tp>的保存者分配其他类型的内存。例如，当实例化list时(例如list<int,my_allocator<int> > )，在list内部就保存着一个my_allocator<int>，但是list需要为自己分配list_node，就是说它需要另一个allocator，那么这个时候就可以通过rebind来完成。 回复 更多评论
@Kevin Lynx明白了，容器根据模板参数Alloc，可以用Alloc::rebind<list_node>::other这样就能得到一个list_node类型的内存分配对象了吧，多谢指点 回复 更多评论
很好；） 回复 更多评论
既然要这样设计，那为何不直接使用数组呢？ 回复 更多评论
有个疑问，如果创建很多个map，list，是否只能用同一个内存池？可以各个map对应不同的内存池吗？ 回复 更多评论
Powered by: C++博客 Copyright © Kevin Lynx