c語言里malloc的最優實現方式是什麼？

01-09

http://www.cs.cornell.edu/courses/cs3410/2017sp/labs/lab12/intro-to-malloc.pdf
如ppt所示，常用實現方法有implicit list和explicit list兩種。implicit實現方法真的有ppt所說那麼不堪？

完美的辦法當然是針對你自己的程序的特徵來做一個malloc，可惜大部分人是沒有這種能力的，所以才要用這些不科學的profiling的方法來妄圖適配全球的程序。如果你手上有若干個互相矛盾的實現的話，可以通過收集客戶的隱私來選擇到底哪一個更好。

最優的實現當然是只分配不釋放了。

簡單的說：

直接用就好了，申請什麼。

負複雜一點說: 規劃好所有可能的內存使用。

聲明一個大數組，done.

曾經做過一個。

首先的問題是從系統中分配虛擬，無論是sbrk還是mmap，或者virttualAlloc，並沒有什麼太大區別，之後的問題是每次malloc時，把系統內存切割出來小塊返回。

如果malloc足夠大，那麼直接分配系統內存，比如glibc在大於128kb的時候調用mmap。

否則，從一個大塊中切割。

如果沒有free，那麼是很簡單的。。

問題在於free之後的內存如何被重複利用。

重複利用可以考慮用分組的方式，

比8,16,24,32 byte這樣的組，這樣就能解決free的內存碎片了。。

內存分配有演算法研究，設計不好的話會造成內存空洞，導致無法分出大塊連續的內存。

普通malloc是比較複雜的，不僅僅是分配內存的問題，還涉及操作系統相關的異常處理，清理緩存，虛擬內存管理等。

linux內核里有一種方法簡單易於實現，就是預先分配好64位元組，128位元組，256位元組，512位元組，1k位元組若干，再大就分page，分配內存時，找最小匹配。這樣的做法是分配效率非常高，釋放的時候不會導致碎片。

自己寫的話，原理上可以參考下這個。內存管理內幕

當然如果你的程序對內存的使用方式比較單一，不妨統一採用「預先分配，標記回收」的簡單方案。

3410課友好呀lol

讀過redis的源碼會發現它自己實現了一個zmalloc,允許使用google的tcmalloc和facebook的jemalloc,這兩種實現應該算比較優秀的。

我自己的嵌入式系統內核項目上的動態內存管理有兩個模塊一個是二叉樹管理的buddy 演算法內存分配用來給短時間高頻申請表和釋放內存的請求用的。好處是沒有外部碎片而且因為內存會在短時間內釋放出內部碎片化也不會太嚴重。另一個是普通的malloc 實現無所謂，用來分配給那些短期內不會釋放的內存請求。沒有內部碎片化，因為請求和釋放不頻繁地外部碎片不嚴重。

私以為針對業務定製jemalloc

試下memory pool

設計malloc有很多要考慮的地方

magic number ：萬一用戶突然腦殘 free 一片沒有被 malloc 過的內存，你該怎麼辦？是否需要magic number 保證只有被 malloc 過的內存才能 free

Singlely Linked or doublely：如果有doublely linked list，你可以很輕鬆的合併前後空的內存合併（merge holes）。

如下圖，當x被 free 了之後，你可以通過 doublely linked list 將前後兩片空白內存合併，合併成為一個 memory hole。也可以使用single Linked list，從頭開始搜索，來達到同樣的效果（省空間，但會更慢）

maloc size：對於現代的 malloc，小的 malloc 可以直接在現有的memory holes 搜索。大的 malloc 應該直接 sbrk() ，中等的 malloc 介於兩者之間。這裡面的有很多可以優化的地方。

事實上，現代的 malloc 已經非常複雜，如果題注真的有興趣，可以看看linux 是怎麼實現 malloc 的

malloc.c source code [glibc/malloc/malloc.c]

我建議你上piazza問一下。。。 Anne Bracy 有可能親自回答你。

當然是自己寫一個啦