分離式自由串列

想像一家五金行整理退回的螺絲，不是丟進一個你得翻找的大箱子，而是按尺寸分成許多小箱、各自貼標：一箱放小螺絲、一箱中、一箱大。顧客要某個尺寸時，你直接走到對的箱子，而不必把全部翻一遍。分離式自由串列（segregated free list）對記憶體就是這麼做：配置器不是用一條容納各種大小的自由串列，而是保有一個自由串列的陣列，每個尺寸類別一條，於是能幾乎瞬間找到所需大小的區塊。

具體地說，配置器定義一組 size class——例如 16、32、48、64、80……位元組，或是 2 的次方——並為每一個各保有一條獨立的自由串列（通常是以類別當索引的陣列）。要服務 malloc(40)，它把 40 向上湊到它的 size class（比如 48），直接走到那個類別的串列，把最前面那個空閒區塊取下。完全不必掃描大小不符的區塊。要釋放區塊時，它算出該區塊的 size class，把它推回那一條串列。因為某條串列上的每個區塊大小都相同（或落在同一個小範圍），在常見的小型配置情況下根本沒有適配搜尋：malloc 與 free 變成大約常數時間的串列取出與推入，而非線性走訪。

這正是為什麼分離式儲存是每個快速現代配置器的骨幹（jemalloc、tcmalloc、mimalloc 全都用 size-class 分離）。取捨很誠實：把 40 向上湊成 48，會在區塊內浪費那 8 個位元組——這就是內部碎片，速度的代價。這個想法還有兩種風味：簡單分離式儲存（simple segregated storage）從不切割也不合併（每個區域只服務一個 size class），用一些記憶體換取最高速度；分離適配（segregated fits）保有不同大小的區塊，仍可能切割較大的一塊，用一點速度換取更緊的記憶體利用。