原理在STL源碼剖析中已經(jīng)有闡述,這里簡(jiǎn)單的說一下,該內(nèi)存池采用HASH-LIST數(shù)據(jù)結(jié)構(gòu)管理數(shù)據(jù),分配一塊內(nèi)存時(shí),如果所要求的內(nèi)存超過了某個(gè)數(shù)量就直接調(diào)用malloc分配內(nèi)存, 否則首先進(jìn)行數(shù)據(jù)對(duì)齊,根據(jù)這個(gè)對(duì)齊的結(jié)果得到所在的HASH表,在該HASH-LIST中查找時(shí)候存在可用的節(jié)點(diǎn),如果有就直接返回,否則每次以20個(gè)節(jié)點(diǎn)元素為數(shù)量開始增加LIST中的元素?cái)?shù)量,如果仍然分配失敗了就去下一個(gè)HASH表中查找可用內(nèi)存,依次類推.
比如,這里的實(shí)現(xiàn)對(duì)齊大小為512字節(jié),如果要求分配的內(nèi)存不大于512字節(jié)就自動(dòng)調(diào)整為512字節(jié)的數(shù)據(jù)大小,在512字節(jié)的HASH-LIST中查找可用節(jié)點(diǎn).
代碼和測(cè)試程序見附件,個(gè)人認(rèn)為很巧妙,適合小對(duì)象的頻繁分配/釋放,效率比之單純的使用malloc/free提高了很多.
不知道還有哪些優(yōu)秀的內(nèi)存池實(shí)現(xiàn)算法可以參考的?
BTW:這份代碼不是我寫的,網(wǎng)上搜索所得,作者模擬了SGI STL的內(nèi)存池算法,我自己做了一些整理和注釋,向作者致敬.
另外,在我的機(jī)器上的測(cè)試結(jié)果為:
采用內(nèi)存池:
real 0m10.723s
user 0m10.710s
sys 0m0.000s
采用系統(tǒng)的malloc/free:
real 0m12.969s
user 0m12.950s
sys 0m0.000s
點(diǎn)擊
這里下載代碼.