內存池的設計和實現，（轉）內存池實現

話說一直想找一個別人寫好的使用，可惜沒什么人會拿這小東西發布，只好自寫一個。

1.多級鏈表分配池
我不知道這種設計的具體學名是什么，這部分的內容也許你去看《STL源碼分析》的有關章節更合適一些，這里我只能用我粗陋的語言描述一下。內存池的設計和實現？
內存池，完全可以從字面上理解為從池子里申請內存，釋放的時候還給池子。
最簡單的內存池應該是fix_pool吧，即每次分配出來的內存塊大小是固定的。Java 內存模型，這種池子的管理結構是一個鏈表，鏈表的每一個節點為固定大小的內存塊。分配的時候，直接返回鏈表的第一個節點，節點不足時，從系統申請大塊內存分成多個節點加入鏈表；釋放的時候更簡單，將釋放的內存加入鏈表頭。
假設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*,?int,?const?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就沒有什么必要了。