兩種碎裂化，仔細命名
在第 1 篇你把碎裂化當成單一反派來認識。要控制它，你得把它拆成兩種不同的形態，因為它們往相反方向拉扯，你無法同時打贏兩者。內部碎裂化是你交出去的某塊區塊內部的浪費：請求 24 位元組，拿到一塊 32 位元組的區塊，於是 8 位元組付了費卻無法使用。外部碎裂化則是區塊之間的浪費：堆積總計握有大量閒置位元組，但它們散落成一個個小孔洞，於是沒有任何單一連續的區段大到足以應付下一個大請求。malloc() 可能在數百萬位元組閒置時回傳 NULL。
這份張力很精確，值得記在腦中。若你每個請求都從一塊大小恰好的區塊去服務，內部浪費是零——但你最後會得到散落各處、數不清的不同大小，堆積便在外部碎裂。反之，若你把每個請求都向上取整到少數幾個固定的桶大小（本篇所環繞的那一步），外部碎裂化幾乎消失，因為被釋放的區塊彼此可互換——但每塊區塊現在都帶著一點內部的鬆餘。真實的配置器並不消除碎裂化；它們選擇要把它花在哪裡，以一份受控、有上限的內部浪費，去交換那種更陰險得多的外部碎裂變得可管理。
對齊：硬體堅持的偏移量
在大小級距說得通之前，你需要對齊，這是一個不來自配置器、而來自 CPU 與底下 ABI 的約束。對齊為 A 的型別必須住在 A 的倍數位址上。在典型的 64 位元機器上，一個 int 想要 4 位元組對齊的位址，一個指標或 double 想要 8，而 malloc() 必須滿足的安全預設值，是最大標準型別的對齊——通常是 16 位元組——這樣不論你把結果轉型成哪種型別，它都落在合法之處。這就是為什麼 malloc() 從不回傳奇數位址：低位元永遠是零。
硬體為什麼在意？一次未對齊的存取可能要付出額外代價：CPU 也許得發出兩次記憶體交易再把碎片縫合起來；而在某些架構上，未對齊的載入不是慢，而是非法的——它會觸發陷阱（trap）。C 標準也同意：透過未對齊指標讀取一個物件是未定義行為，意思是最佳化器可以自由假設它永遠不會發生，於是這個臭蟲可能在 -O0 跑得好好的，卻在 -O2 默默地被錯誤編譯。這正是你先前遇過的、未定義行為那份誠實的危險：不是「視平台而定」，而是「編譯器被允許假裝未對齊的情況不可能發生」。
因為所需的對齊永遠是 2 的次方，向上取整就是一個便宜的位元技巧，而不是除法。要把大小 n 向上取整到 A 的倍數（A 為 2 的次方），配置器計算 (n + A - 1) & ~(A - 1)：加上 A-1 把你推過下一道邊界，再用 ~(A - 1) 把低位元遮掉，便把你貼回那道邊界上。讓配置器在第 1 篇得以偷走區塊低位元來存旗標的那個恆等式——每個對齊過的大小其低位元皆為零——正是讓對齊取整變成單一一次 AND 的那個恆等式。當你真的需要比 malloc() 給的更強的對齊（譬如 64 位元組的快取列），C 給你 alignas 與 alignof，而這種刻意請求多於預設值的做法稱為過度對齊（over-alignment）。
round n up to a power-of-two alignment A:
aligned = (n + A - 1) & ~(A - 1)
example, A = 16 (so A - 1 = 0x0F, ~(A-1) = ...0xF0):
n = 24 -> (24 + 15) & ~15 = 39 & 0xFFFFFFF0 = 32
n = 32 -> (32 + 15) & ~15 = 47 & 0xFFFFFFF0 = 32
n = 33 -> (33 + 15) & ~15 = 48 & 0xFFFFFFF0 = 48大小級距：用少數幾個桶取代每一種大小
現在來到核心觀念。配置器不去追蹤每一種可能大小的區塊，而是把每個請求向上取整到一組小而固定的大小級距——譬如 16、32、48、64、80、96……位元組——而且只交出這些恰好大小的區塊。一個 malloc(24) 與一個 malloc(30) 都會變成一塊 32 位元組的區塊。回報極大：因為某個級距內的每塊區塊都一模一樣，一塊被釋放的 32 位元組區塊和其它每一塊都可互換，於是配置器永遠不需要搜尋恰當大小的區塊——它只要拉出那個級距串列的頭即可。第 1 篇那次 O(n) 的閒置串列走訪，便塌縮成 O(1)。
這就是分離式閒置串列：不是一條串列，而是一個串列的陣列，以大小級距為索引。malloc(n) 把 n 向上取整，直接索引進陣列，從那條串列彈出第一塊區塊；free(p) 從區塊標頭讀出它的大小級距，再把它推回對應的串列。級距之內沒有掃描、也沒有放置策略要苦惱——依建構方式，每塊區塊都恰好合身。也請留意：大小級距使切割與合併幾乎變得不必要：你不去把大區塊切小，因為你早已有一條恰當大小區塊的串列；你也不去合併，因為一個級距裡的所有區塊大小相同。第 1 篇那套帳本工作變得戲劇性地簡單。
代價當然是內部碎裂化，而級距的間距正是設定它的那個旋鈕。若級距以 2 的次方跳（16、32、64、128），取整在最壞情況下可能浪費近乎半塊——一個 malloc(65) 會落進 128 的級距。真實的配置器採用更細的排程：小尺寸以線性間距排列（16、32、48、64），使浪費至多一步，只在大尺寸處才放寬間距，因為那裡幾個百分比的開銷可以忽略。第 5 篇會剖析的 tcmalloc 用了大約 80 到 90 個大小級距，調得讓每個物件的最壞情況內部浪費有上限——往往封頂在約 12.5%。整個設計是一份刻意、量化過的取捨：用一份有上限的內部浪費細屑，換來 O(1) 的速度與近乎零的外部碎裂化。
放置、爆量與大小級距的極限
大小級距並不廢除放置策略——它把放置策略搬了位置。級距之內選擇很瑣碎（任何區塊都合身），但上方冒出兩個新的放置問題。第一，一條新的級距串列從哪裡取得它的區塊？配置器會從更大的區段——一個分頁或一個跨距（span）——成批切出它們，於是一次系統呼叫就一口氣產出許多同樣大小的區塊。第二，一個幾乎空了的跨距何時該還給作業系統？回收得太積極會反覆顛簸；太懶散又會把記憶體洩漏回程式的尖峰用量。這些才是現代配置器真正的放置決策，而且它們講的是分頁的跨距，不是個別位元組。
大小級距還引入一個值得誠實命名的失敗模式：爆量（blowup）。因為一個級距的區塊無法滿足另一個級距的請求，在 32 級距釋放的記憶體就閒置在那裡，無法被一波 64 級距的請求再利用，即使那些位元組就在眼前。一支配置大小會在不同階段變動的程式——先是數百萬個小節點，接著數百萬個較大的——可能持有遠多於其存活集的記憶體，因為每個級距各自囤積自己被釋放的區塊。這是分離式配置器的特徵弱點，正是它治好的外部碎裂化的鏡像，也是一個量測真實工作負載很要緊的地方。
- 把請求向上取整。加上標頭／對齊的開銷，再用一次遮罩貼到最近的大小級距：這一步同時對齊了區塊、也選定了它的級距。
- 用索引，別搜尋。把級距編號當成索引，指進分離式閒置串列的陣列，不必走訪就直接跳到正確的那條串列。
- 彈出或補貨。若那條串列非空，就以 O(1) 彈出它的頭；若它空了，就從一個較大的跨距切出一批同樣大小的新區塊，串接上去。
- 釋放時依級距推回。從區塊的中介資料讀出它的級距，再把它推到那個級距串列的前端——級距之內不需合併，也不需邊界標記。
這條路接下來通往何處：依執行緒、依節點
大小級距為單一執行緒解決了速度與外部碎裂化，但它把下一個問題擺得正正方方。那些分離式串列是共享狀態，而真實程式會同時從許多執行緒配置。若每次 malloc() 與 free() 都得鎖住同一條依級距的串列，那把鎖就變成一條佇列，你的 O(1) 配置器便在爭用下卡住。標準的解藥——第 5 篇會把它講具體——是執行緒區域快取：給每個執行緒自己一小組依級距的閒置串列，不必任何鎖就能服務，只在某執行緒的快取見底或溢出時，才去碰共享的中央串列。如此一來，大多數配置除了執行緒區域記憶體以外什麼都不碰。
執行緒快取之所以要緊，還有一個更微妙、且連回對齊與大小級距的理由：偽共享（false sharing）。兩個執行緒去碰兩個剛好落在同一條 64 位元組快取列裡的不同物件，會讓那條快取列在它們的核心之間來回彈跳，即使那兩個物件在邏輯上從不重疊，效能也被它扼殺。大小級距的佈局與依執行緒的競技場（arena）有助於此，方法是把每個執行緒的物件群聚在它自己的快取列上。在大型機器上還有一道軸：記憶體在物理上接在特定的 CPU 插槽上，而碰另一個插槽的記憶體比較慢，所以一個正經的配置器會做NUMA 感知的放置——把一個執行緒的配置留在離跑它的核心最近的那個記憶體節點上。
退一步，看清整級的形狀。第 1 篇給了你閒置串列與它 O(n) 的弱點；本篇把請求取整進少數幾個對齊過的大小級距，讓常見情況變成 O(1)，並以受控的內部浪費去交換外部碎裂化的消失。剩下的是大規模下的並行與回收——那些依執行緒的快取、中央堆積、跨距管理，以及把教科書配置器和 jemalloc、tcmalloc、mimalloc 區分開來的細心調校。你現在握有那些正式配置器賴以建構的每一個基本元件；第 5 篇只是展示它們如何把這些元件組裝起來。