如何設計內存池？

01-06

內存池的優點就是可以減少內存碎片，分配內存更快，可以避免內存泄露等優點。那我們如何去設計一個內存池呢？能不能給個你的大致思考過程或者步驟，比如，首先要設計一個內存分配節點（最小單元），再設計幾個內存分配器（函數），等等。不是太清晰。望大神指點。

一般工程里不推薦你寫，因為你費力寫一個出來99%可能性沒有內置的好，且內存出bug難調試

實在閑著蛋疼，你也可以當個玩具寫寫玩玩：

1. 實現教科書上的內存分配器：

做一個鏈表指向空閑內存，分配就是取出一塊來，改寫鏈表，返回，釋放就是放回到鏈表裡面，並做好歸併。注意做好標記和保護，避免二次釋放，還可以花點力氣在如何查找最適合大小的內存快的搜索上，減少內存碎片，有空你了還可以把鏈表換成夥伴演算法，寫著玩嘛。

2. 實現固定內存分配器：

即實現一個 FreeList，每個 FreeList 用於分配固定大小的內存塊，比如用於分配 32位元組對象的固定內存分配器，之類的。每個固定內存分配器裡面有兩個鏈表，OpenList 用於存儲未分配的空閑對象，CloseList用於存儲已分配的內存對象，那麼所謂的分配就是從 OpenList 中取出一個對象放到 CloseList 里並且返回給用戶，釋放又是從 CloseList 移回到 OpenList。分配時如果不夠，那麼就需要增長 OpenList：申請一個大一點的內存塊，切割成比如 64 個相同大小的對象添加到 OpenList中。這個固定內存分配器回收的時候，統一把先前向系統申請的內存塊全部還給系統。

3. 實現 FreeList 池：

在你實現了 FreeList的基礎上，按照不同對象大小（8位元組，16位元組，32，64，128，256，512，1K。。。64K），構造十多個固定內存分配器，分配內存時根據內存大小查表，決定到底由哪個分配器負責，分配後要在頭部的 header 處（ptr[-sizeof(char*)]處）寫上 cookie，表示又哪個分配器分配的，這樣釋放時候你才能正確歸還。如果大於64K，則直接用系統的 malloc作為分配，如此以浪費內存為代價你得到了一個分配時間近似O（1）的內存分配器，差不多實現了一個 memcached 的 slab 內存管理器了，但是先別得意。此 slab 非彼 slab（sunos/solaris/linux kernel 的 slab）。這說白了還是一個弱智的 freelist 無法歸還內存給操作系統，某個 FreeList 如果高峰期佔用了大量內存即使後面不用，也無法支援到其他內存不夠的 FreeList，所以我們做的這個和 memcached 類似的分配器其實是比較殘缺的，你還需要往下繼續優化。

4. 實現正統的 slab （非memcached的偽 slab）代替 FreeList：

這時候你需要閱讀一下 http://citeseer.ist.psu.edu/bonwick94slab.html 這篇論文了，現代內存分配技術的基礎，如何管理 slab 上的對象，如何進行地址管理，如何管理不同 slab 的生命周期，如何將內存回收給系統。然後開始實現一個類似的東西，文章上傳統的 slab 的各種基礎概念雖然今天沒有改變，但是所用到的數據結構和控制方法其實已經有很多更好的方法了，你可以邊實現邊思考下，實在不行還可以參考 kernel 源碼嘛。但是有很多事情應用程序做不了，有很多實現你是不能照搬的，比如頁面提供器，可以提供連續線性地址的頁面，再比如說 kernel 本身記錄著每個頁面對應的 slab，你查找 slab 時，系統其實是根據線性地址移位得到頁面編號，然後查表得到的，而你應用程序不可能這麼干，你還得做一些額外的體系來解決這些問題，還需要寫一些額外的 cookie 來做標記。做好內存收縮工作，內存不夠時先收縮所有分配器的 slab，再嘗試重新分配。再做好內存回收工作，多餘的內存，一段時間不使用可以還給操作系統。

5. 實現混合分配策略：

你實現了上面很多常見的演算法後，該具體閱讀各種內存分配器的代碼了，這些都是經過實踐檢驗的，比如 libc 的內存分配器，或者參考有自帶內存管理的各種開源項目，比如 python 源碼，做點實驗對比他們的優劣，然後根據分配對象的大小採用不同的分配策略，區別對待各種情況。試驗的差不多了就得引入多線程支持了，將你的鎖改小。注意很多系統層的線程安全策略你是沒法弄的，比如操作系統可以關中斷，短時間內禁止本cpu發生任務切換，這點應用程序就很麻煩了，還得用更小的鎖來代替。當鎖已經小到不能再小，也可以選擇引入 STM 來代替各種鏈表的鎖。

6. 實現 Per-CPU Cache：

現代內存分配器，在多核下的一個重要優化就是給多核增加 cache，為了進一步避免多線程鎖競爭，需要引入 Per-CPU Cache 了。分配內存先找到對應線程所在的cpu，從該cpu上對應的 cache 里分配，cache 不夠了就一次性從你底層的內存分配器里多分配幾個對象進來填充 cache，釋放時也是先放回 cache，cache裡面如果對象太多，就做一次收縮，把內存換個底層分配器，讓其他 cpu 的cache有機會利用。這樣針對很多短生命周期的頻繁的分配、釋放，其實都是在 cache 里完成的，沒有鎖競爭，同時cache分配邏輯簡單，速度更快。操作系統裡面的代碼經常是直接讀取當前的cpu是哪個，而應用層實現你可以用 thread local storage 來代替，目前這些東西在 crt的 malloc 里還暫時支持不到位（不排除未來版本會增加），可以更多參考 tc/jemalloc。

7. 實現地址著色:

現代內存分配器必須多考慮匯流排壓力，在很多機型上，如果內存訪問集中在某條 cache line相同的偏移上，會給匯流排帶來額外的負擔和壓力。比如你經常要分配一個 FILE 對象，而每個 FILE對象使用時會比較集中的訪問 int FILE::flag; 這個成員變數，如果你的頁面提供器提供的頁面地址是按照 4K對齊的，那麼很可能多個 FILE對象的 flag 成員所處的 cache line 偏移地址是相同的，大量訪問這些相同的偏移地址會給匯流排帶來很大負擔，這時候你需要給每個對象額外增加一些偏移，讓他們能夠均勻的分布在線性地址對應的cache line 偏移上，消減匯流排衝突的開銷。

8. 優化緩存競爭：

多核時代，很多單核時代的代碼都需要針對性的優化改寫，最基本的一條就是 cache 競爭，這是比前面鎖競爭更惡劣的情況：如果兩個cpu同時訪問相同的 cache-line 或者物理頁面，那麼 cpu 之間為了保證內存一致性會做很多的通信工作，比如那個cpu0需要用到這段內存，發現cpu1也在用，那麼需要通知cpu1，將cpu1 L1-L2緩存裡面的數據寫回該物理內存，並且釋放控制權，這時cpu0取得了控制權才能繼續操作，期間cpu0-cpu1之間的通信協議是比較複雜的，代價也是比較大的，cache競爭比鎖競爭惡劣不少。為了避免 cache 競爭，需要比先前Per-CPU cache 更徹底的 Per-CPU Page 機制來解決，直接讓不同的cpu使用不同的頁面進行二次分配，徹底避免 cache 競爭。具體應用層的做法也是利用線性地址來判斷所屬頁面（因為物理頁面映射到進程地址也是4k對齊的），同時繼續使用 thread local storage 或者用系統提供的 api 讀取當前屬於哪個 cpu 來實現。為了避免核太多每個核佔據大量的頁面帶來的不必要的浪費，你可以參考下 Linux 最新的 slub 內存分配演算法，但是 slub 也有未盡之處，好幾個 linux 發行版在實踐中發現 slub 還是存在一些問題的（非bug，而是機制），所以大部分發行版默認都是關閉 slub 的，雖然，你還是可以借鑒測試一下。

9. 調試和折騰：

繼續參考各種現代內存分配器，取長補短，然後給你的分配器添加一些便於調試的機制，方便診斷各種問題。在你借鑒了很多開源項目，自己也做了一些所謂的優化，折騰了那麼久以後，你或許以為你的分配器可以同各種開源分配器一戰了，測試效果好像也挺好的，先別急，繼續觀察內存利用率，向操作系統申請/歸還內存的頻率等一系列容易被人忽視的指標是否相同。同時更換你的測試用例，看看更多的情況下，是否結果還和先前一樣？這些都差不多的時候，你發現沒有個一兩年的大規模持續使用，你很難發現一些潛在的隱患和bug，可能你覺得沒問題的代碼，跑了兩年後都會繼續報bug，這很正常，多點耐心，興許第三年以後就比較穩定了呢？

有卯用呢？

十多年前 libc 還不成熟的情況下，為了程序長時間運行的穩定性，大部分程序員都必須針對自己的應用來實現針對特定情況的內存分配器。當年如果不自己管理內存，很多客戶端，如果計算密集頻繁分配，才開始可能沒什麼區別，但跑個幾個小時性能立馬就下降下來了；伺服器進程持續運行個10多天不重啟，速度也會越來越慢，碎片多了嘛。如今 libc 的 malloc 也進步了很多，這樣的情況比較少了，那你再做一個內存池的意義何在呢？

在你的玩具比較穩定的情況下，終於可以產生一些價值了，因為一些性能指標你無法兼得，標準的分配器往往提供了一個類似保守和中庸的做法，來針對大部分的情況，你可以做的第一步，就是打破這樣的平衡，讓你的分配器傾向於某些情況比如：

1. 現代計算機內存都很大，你是不是可以犧牲內存利用率為代價換取更高的內存歸還/重用的效率？同時換取更快的分配速度？或許你會發現，你可以比 libc 的 malloc 平均浪費 30%內存的代價換來兩倍以上的性能提升，在一些內存分配成為瓶頸的應用中起到積極的作用。

2. 比如你可以調整大小內存的比值，libc如果認為 8K以下是小內存，那麼你可以不那麼認為。

3. 比如如果你的系統就是一個單線程的東西，那麼你是否能提供開關，完全以單線程的模式進行運作，完全繞過各種鎖和針對多核進行的各種冗餘操作呢？

4. 比如你的機器內存有限，你應用需要耗費大量的內存，那麼你可以引入其他機制，以犧牲少量性能為代價，換取更好的內存回收效果和內存利用率。

5. 最近分配的對象盡量在線性地址上集中在一起，這樣緩存命中高，也不易發生缺頁。

6. 比如你程序裡面某些對象需要被跟蹤，你能否直接在分配器上實現對象跟蹤機制，跟蹤各種泄漏，越界問題？

7. 每個內存分配都在尋求最佳的公平，你在乎的公平是什麼？

。。。。。。

----

多讀書少「設計」……不要總想搞個大新聞……

最簡單的， $2^n$ 那種，五十年前提出來的：Buddy memory allocation
一點改進：Design of a General Purpose Memory Allocator for the 4.3BSD UNIX? Kernel [1988] http://docs.freebsd.org/44doc/papers/kernmalloc.pdf
如果對象大小固定：The Slab Allocator: An Object-Caching Kernel Memory Allocator [1994] https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a
……//距今尚有21年

如果你來問這個問題，那麼給你的唯一建議就是：不要自己寫一個內存池。

事實上，除非特別極端的應用場景或者特殊情況，不然，大多數人寫的內存池，綜合而言，都比不上默認的那套的性能---更何況寫這些內存池的人，起碼都不會跑上來問這個問題。

如果僅僅是想學習的話，直接看源碼好了：malloc看完了還可以看看tcmalloc。

Memory pool is a myth.

你列的那些優點是實際驗證過的還是道聽途說的？

內存池除了減少內存申請和釋放的開銷之外還有什麼提升性能或者方便之處？ - 陳碩的回答

除去十分特定場景，不要嘗試自己寫，真是費力不討好，我這裡有個場景，每個連接需要分配固定的4k的網路讀寫buffer，所以我寫了個玩具版的：

https://github.com/auxten/gko_pool/blob/master/src/memory.cpp

這個是獨立出來的項目

https://github.com/auxten/gkoAlloc

讓我想起了阿里今年的筆試題……

不要看我，我沒寫出來。

周圍的同事陸陸續續的回家了，周五的晚上，外面下起了小雨，心想找點事情做一下，等雨停了再回家吧，家裡還剩下一些前天晚上煮的骨頭湯，可以拿來下點麵條。

看了一下題主的描述，想起很久以前的我，一些問題想得很大，結果到頭來不是發現自己做不好，就是別人已經做得很好了。關於內存池我以前也嘗試過，正如幾位高票前輩所說的那樣，自己去寫往往不如直接用久經測試過的庫。

我以前容易把內存池和對象池弄混淆，內存管理不建議自己造輪子，但是對象的管理很多時候是需要自己來寫的，雖然有點偏題……這不是因為等雨停嘛，所以我就對象池這一點拿兩個具體的示例說一下，其中一個是C++實現的，另外一個是C實現的，都是網上的代碼，選擇這兩個的原因是，他們都足夠小，另外兩者在實現上都有讓我覺得巧妙的地方。

第一個C++版本的內存池來自於這裡： http://www.codeproject.com/Articles/746630/O-Object-Pool-in-Cplusplus

這個內存池的思路很簡單：每次分配一個node，一個node相當於一個小的對象池，這個小池子用完了，再分配一個尺寸大一倍的node，這些node是以鏈表的方式鏈接起來的。每次釋放的時候，我就把這些對象依次放到一個stack裡面。每次分配的時候，如果stack裡面有東西，我就把最上面那個拿出去用。

思路相當直觀。

巧妙的地方是這裡沒有顯式的stack存在。具體實現方式是這樣的，我用一個指針sp來指向stack的頂部，初始化的時候指針當然是NULL了。表示stack是空的。當第一次釋放的時候，把sp的值（也就是可用的下一個對象的地址）存入被釋放的對象區域，然後用sp指向這個剛被釋放的對象。分配的時候，在把sp指向的對象返回之前，取出sp指的對象內存區域的一個指針地址（也就是之前被釋放的一個對象的地址）賦給sp。這樣sp就指向下一個可用的對象了。

這裡存在的一個問題是：如果對象的尺寸小於指針的大小，那麼指針地址就存不下去……為了解決這個問題，在分配block的時候，會將實際的單位大小以指針的大小進行align。

相關的代碼如下：

這個C++對象池的實現很簡潔，一百行代碼左右。理解了上面我說的實現技巧，再看源代碼會很容易。

下面有一個更加簡單的C實現，來自這裡：klib/klist.h at master · attractivechaos/klib · GitHub

其簡潔也源於一些巧妙的實現手段。源文件裡面的代碼因為是宏實現的，有些難看，我這裡單獨拿出來寫了一點注釋便於理解，如下：

因為C實現本身就只有20多行，也不涉及到複雜的指針操作，就不做贅述了。相信看代碼就可以明白。Enjoy！

-------

雨還在下，但畢竟還是要回家的……他帶上帽子，消瘦的背影消失在了霧雨朦朧的夜色中……

如果你想了解一個基本的內存池設計，可以閱讀一下《Python源碼剖析》的第16章PYTHON的內存管理機制。類似資料很多，這個講得比較容易理解。然後你可以實現一個玩玩。但是不要糾結在工程中使用，工程里還是用nedmalloc之類的現成的東西吧。

題主想要的估計是Nginx的ngx_pool_t。

https://github.com/imiskolee/mempool

把nginx的內存池單獨拿出來用了。

目前在公司中在幾個平台上使用。

這種內存池的意義，主要是為了避免內存碎片和內存碎塊。而ngx_pool_t的前提是場景是web請求這種快速申請快速釋放，且流程很線性的系統。桌面應用估計不太適合這種內存分配方式。

如果是c的話，memcached 有個很簡單的內存池實現。

或許你自己寫了個你覺得還不錯的內存池實現，但這些在 jemalloc 這些有無數與時俱進新特性的 allocator 面前都弱爆啦。

如果用的是 java ，那麼內存池能減少不少 gc ，對於提高 sla 是有價值的。

最近看了 tcmalloc和 jemalloc的設計思路，題主可以看一下，非常不錯

樓主提的問題太大，是很難回答的，或者說，樓主需要的是一個，適用於各種情況的內存池，這個問題就成了操作系統級的問題或是編譯器的問題，那麼答案只能得到，你最好別做！或是換個你認為理想的操作系統！或是發明一個更好的輪子！

如果說改善內存碎片的狀況，那就要看情況了，懶辦法還是，用更好的庫，或是換種語言。

實際上，這是個隨手扔垃圾還是扔到垃圾袋再扔垃圾桶哪個更好的問題。

雖然大牛喜歡針對最廣泛的問題展開最宏偉的論述，可惜天朝現狀是，以手機為例，國內的，不經Google Play限制的Android的APP，內存管理極其糟，特別是BAT，天朝最強悍的三大公司首當其衝，比如微信，上來就要約300M內存，這完全與各位大牛們的高深回答相反，而這三大公司不大牛哪還有大牛呢，天朝大牛的牛X之大和軟體之爛讓人覺得驚駭莫名。以看雪論壇為例，最牛的莫過於幾個360的常駐代表，但大家知道的事實是，大牛公司的EXE並不怎麼樣，至少某訊的安全管理極其糟糕，憑藉著「你的網路可能有問題！」這類威嚇來推卸責任，扯遠了。

個人覺得要根據自己的具體情況來適當地規範內存的申請和釋放，比如建立鏈表管理廢棄的內存（先不釋放，用於重複使用），思路就是把垃圾放入袋裡，而不是隨處一扔幻想著有一個偉大的函數可以像媽媽一樣呵護你

我覺得樓上大多數回答者都忽略了一個問題，樓主想實現的可能確實有優化作用。

比如，一個http代理伺服器如果用malloc/free來管理內存可能會有很多次的系統調用，而用mmap來映射一塊大內存，內部實現一個簡單的api來操作這個大內存，這樣是否可以減少內存的分配釋放從而提升系統效率呢？

你說的是傳說中的操作系統作業？

如果寫著玩玩，韋的高票答案已經很好了。如果是工程上使用，一般來說除了針對特定場景可以考慮用freelist 外，其餘就用jemalloc就好，沒有必要自己發明