那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

研究了一下SGI STL的内存算法

原理在STL源码剖析中已经有阐述,这里简单的说一下,该内存池采用HASH-LIST数据结构管理数据,分配一块内存时,如果所要求的内存超过了某个数量就直接调用malloc分配内存, 否则首先进行数据对齐,根据这个对齐的结果得到所在的HASH表,在该HASH-LIST中查找时候存在可用的节点,如果有就直接返回,否则每次以20个节点元素为数量开始增加LIST中的元素数量,如果仍然分配失败了就去下一个HASH表中查找可用内存,依次类推.

比如,这里的实现对齐大小为512字节,如果要求分配的内存不大于512字节就自动调整为512字节的数据大小,在512字节的HASH-LIST中查找可用节点.

代码和测试程序见附件,个人认为很巧妙,适合小对象的频繁分配/释放,效率比之单纯的使用malloc/free提高了很多.

不知道还有哪些优秀的内存池实现算法可以参考的?

BTW:这份代码不是我写的,网上搜索所得,作者模拟了SGI STL的内存池算法,我自己做了一些整理和注释,向作者致敬.

另外,在我的机器上的测试结果为:
采用内存池:
real    0m10.723s
user    0m10.710s
sys     0m0.000s

采用系统的malloc/free:
real    0m12.969s
user    0m12.950s
sys     0m0.000s

点击这里下载代码.

posted on 2008-04-01 19:55 那谁 阅读(6506) 评论(6)  编辑 收藏 引用 所属分类: C\C++算法与数据结构服务器设计

评论

# re: 研究了一下SGI STL的内存算法  回复  更多评论   

http://www.cppblog.com/CppExplore/archive/2008/02/18/42890.html
http://www.cppblog.com/CppExplore/archive/2008/02/19/42952.html
http://www.cppblog.com/CppExplore/archive/2008/02/20/42986.html
2008-04-01 21:00 | cppexplore

# re: 研究了一下SGI STL的内存算法[未登录]  回复  更多评论   

@cppexplore
准备下一步研究在这里面评价最好的APR.

其实说到实践证明,STL和APR都是有成功项目证明的产品,可靠性会更高些.其他的毕竟还是个人的产品,没有经过千锤百炼.

2008-04-01 22:39 |

# re: 研究了一下SGI STL的内存算法  回复  更多评论   

@创
你看的第一篇吧,对于小对象后面的loki和boost都不错的。
不要浪费精力研究了,就是一个结构,原理都很简单,看的太仔细了也是没什么意思,呵呵。
2008-04-01 22:50 | cppexplore

# re: 研究了一下SGI STL的内存算法[未登录]  回复  更多评论   

@cppexplore
另外,很奇怪你的系列文章中居然没有分析STL内存池实现的。
2008-04-01 22:51 |

# re: 研究了一下SGI STL的内存算法  回复  更多评论   

@创
呵呵,不奇怪啊。我压根就没看stl的内存池,ACE的看了,果然是集大成者,到是想写呢,后来写多了加上去写其他方面的 就懒了。
现在网络模型的也是写了一半,下一篇估计就是去写定时期了,呵呵
2008-04-01 22:53 | cppexplore

# re: 研究了一下SGI STL的内存算法  回复  更多评论   

去看了下cppex的文章,发现问了句废话,呵呵,已经改掉了。
希望看到ACE内存池详细分析的文章。
2008-04-02 01:46 | 矩阵操作

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理