随笔 - 119  文章 - 290  trackbacks - 0

博客搬家了哦,请移步
叫我abc

常用链接

留言簿(12)

随笔分类

我的博客

搜索

  •  

积分与排名

  • 积分 - 294006
  • 排名 - 83

最新评论

阅读排行榜

话说一直想找一个别人写好的使用,可惜没什么人会拿这小东西发布,只好自写一个。

1.多级链表分配池
我不知道这种设计的具体学名是什么,这部分的内容也许你去看《STL源码分析》的有关章节更合适一些,这里我只能用我粗陋的语言描述一下。
内存池,完全可以从字面上理解为从池子里申请内存,释放的时候还给池子。
最简单的内存池应该是fix_pool吧,即每次分配出来的内存块大小是固定的。这种池子的管理结构是一个链表,链表的每一个节点为固定大小的内存块。分配的时候,直接返回链表的第一个节点,节点不足时,从系统申请大块内存分成多个节点加入链表;释放的时候更简单,将释放的内存加入链表头。
假设fix_pool的fix size = 128,那么内存池可以为128byte以下的任意大小的请求进行分配,但是这样做相当浪费呢,于是unfix_pool就在此基础上出现了。
由多个分配大小不同的fix_pool所组成的内存池就叫做多级链表分配池,我是这么定义的。
常规上会定义8,16,24,32,...,112,120,128这些分配大小,共16级。分配或者释放的时候,判断请求的大小在哪一级别上,用该级别的fix_pool链表进行分配或者释放。


2.泄漏检测
当所有的分配都经过你的手的时候,泄漏检测什么的再简单不过了。
找个地方把分配的东西记录下来,释放的时候把记录去掉。程序退出的时候还存在的分配记录就是泄漏了。
我个人选用的方法是给每一个分配请求多分配一些内存,用来记录分配的信息,并将这部分信息用双向链表串起来。释放的时候对释放的指针做一下指针偏移就可以找到信息记录并移出双向链表。
这个方法的开销是常数级的,不过无法处理重复删除的问题。


3.operater new
要把你的内存池应用到每一个角落,需要定义operator new和operator delete。
 void* operator new(size_t) throw(std::bad_alloc);
 void operator delete(void* p);
但是这还不够,谁也不想看到一堆泄漏信息而找不到泄漏的位置,因此还需要定义带附加参数的operator。
对于placement new而言,operator new[]和operator delete[]是必须的,无法省略。

void* operator new(size_t, const char* file, int line, const char* function);
void* operator new[](size_t, const char*intconst char*);
void operator delete(void* p);
void operator delete[](void* p);
为了能用上新的operator,需要在头文件中重新定义new,并包含进每一个cpp文件。

//op_new.h
#define DEBUG_NEW new(__FILE__, __LINE__, __FUNCTION__)
#define new DEBUG_new
不过重定义new会和自行使用placement new的地方冲突,如stl容器库,这时候要undef new后才能编译冲突组件。

#undef new
#include 
<vector>
#include 
"op_new.h"


4.线程安全
我没听说过new/delete,malloc/free是线程不安全的,所以在内存池的allocate/deallocate接口处直接加了锁。
想降低开销的同学可以使用spin lock,而不是mutex。


5.bench
AMD5000+ X2, memory 2G,测试分配大概900M
 1     for(int x=0; x<REPEAT; ++x)
 2     {
 3         clock_t t1 = clock();
 4         for(int i=0; i<15990000++i)
 5         {
 6             size_t size = rand() % 121;
 7             char* p = new char[size];
 8             bufs.push_back(p);
 9         }
10         tm = tm + clock() - t1;
11         printf("time alloc %d\n", tm);
12 
13         t1 = clock();
14         for(int i=0; i<bufs.size(); ++i)
15         {
16             char* p = bufs[i];
17             delete [] p;
18         }
19         t2 = t2 + clock() - t1;
20         printf("time free %d\n", t2);
21         bufs.clear();
22     }

repeat=1
win32下分配效率提升大概50%,释放效率提升170%;
linux下技不如人,输了。。。。

repeat=15,应该存在内存碎片这种东西了
win32下分配效率提升100%,释放效率提升140%;
linux下分配效率提升大概15%左右,释放效率提升50%以上。

猜测结论: linux的内存分配机制很高效。我的实现可能写得不怎样,或者内存池已经out了。

补充:
由eXile推荐的tcmalloc,进行了性能测试,linux平台
repeat=1
tcmalloc和系统分配半斤八两,难出其右。
repeat=15
tcmalloc分配效率提升30%以上,释放效率提升100%以上。
我想果然还是我实现里使用mutex的缘故,去掉加锁后,速度超英赶美,释放效率更是比tcmalloc提升了50%以上。
也许将mutex换成spin lock就能和tcmalloc的效率接近了,但是对于thread cache这一点我是没法比的,可以不加锁分配,多线程下的效率很高。
不过既然有tcmalloc,自己写这种general pool就没有什么必要了。
posted on 2009-11-11 21:57 LOGOS 阅读(9799) 评论(11)  编辑 收藏 引用

FeedBack:
# re: 内存池实现 2009-11-12 08:54 cm
crt这层已经使用内存池了。不过为什么自己再弄一层,性能会有提高?看看crt的实现可能更清楚点。  回复  更多评论
  
# re: 内存池实现 2009-11-12 09:28 tangrongjun
@cm
除了垃圾收集技术外没有任何一种算法可以解决内存碎片问题。特别是在多线程,高内存使用,长时间运行的环境下内存碎片绝对是头号问题。以我的理解,自己内存管理最好不要整个进程空间进行--因为libc(linux环境)已经进行整个进程空间管理了。需要进行局部内存管理以我的经验有两个需求:一是局部化可以适应自己程序特殊的需要。二是可以隔离自己写的动态库对引用它的组件的影响。  回复  更多评论
  
# re: 内存池实现[未登录] 2009-11-12 09:49 关中刀客
以前听一个朋友说他们在linux上面,不需要实现内存池,因为linux自身的分配策略已经很高效了,他们都是直接的new/delete  回复  更多评论
  
# re: 内存池实现 2009-11-12 11:28 xiaowang
楼主,共享一下代码吧  回复  更多评论
  
# re: 内存池实现 2009-11-12 12:30 eXile
用google的TCMalloc 直接替换malloc实现  回复  更多评论
  
# re: 内存池实现 2009-11-12 14:27 OwnWaterloo
同意cm的意见:缓存的层次越少越好。
真要做,就直接与VirtualAlloc, mmap, sbrk交互,不通过crt。


解决内存碎片的算法除了垃圾收集以外,也是存在的。
但这个算法是要client端(内存的使用者)配合才行。
如果内存分配器对内存的请求的方式一无所知,只靠猜测,这种generic内存分配器已经没有提高余地了。
要继续提高内存分配效率,必须让client告诉内存分配器他会以何种方式使用内存。内存分配器根据不同的使用方式来优化自己的算法。

例如,假设实现一种类似<<c interfaces and implementations>>中的arena,并且不通过crt,直接使用VirtualAlloc。当arena被释放的时候,确实就不存在任何碎片。

  回复  更多评论
  
# re: 内存池实现 2009-11-12 19:44 LOGOS
@eXile
tcmalloc果然不错,采用了。
补充了新测评。

@xiaowang
网上到处有贴,我就不献丑了
你想要的话留个邮箱,私下发给你
  回复  更多评论
  
# re: 内存池实现 2009-11-13 11:02 哦哦
boost pool 就很不错了  回复  更多评论
  
# re: 内存池实现 2011-03-08 15:24 trueboy
发一份给我啊: yzsb1118@gmail.com  回复  更多评论
  
# re: 内存池实现 2011-03-08 16:02 trueboy
@LOGOS
发一份给我啊:yzsb1118@gmail.com  回复  更多评论
  
# re: 内存池实现 2011-03-29 21:17 ladenol
发一份代码给我吧,最近正好要用,谢谢!
dsapp@163.com  回复  更多评论
  

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