原理在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
點擊
這里下載代碼.