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