比malloc還快的記憶體管理

其實就是自己預先分配一大塊記憶體然後自己管囉，由於malloc必須和系統核心打交道，又得維護許多執行時期的資訊，自然表現得非常緩慢，以下將介紹一種常用的自行管理記憶體的方法，稱為物件集區，許多腳本語言跟有大量收放記憶體需求的軟體都有自己的實做，我準備從Python中的obmalloc中抽出精華來介紹。

先從作業系統的角度看記憶體

作業系統認為記憶體是需要分配根管理的資源，你可能在相關課程有讀到過，那麼你應該會聯想到一個事實，那就是即便是作業系統也無法一次掌握所有記憶體，事實上作業系統會把記憶體分配成一個個分頁(Page)，按照標準一個分頁的大小是4096/Bytes，而不同的電腦一次能掌握的分頁數量也不同，假設你的電腦一次能掌握10個分頁，那就表示同一時間將有40960/Bytes的記憶體可以被使用，而當你想使用這些區域以外的記憶體時，作業系統就必須換掉幾個正在管理中的分頁，再換上你要的，這稱為置換，說了這麼多指是要說明置換需要靠作業系統的核心來處理，所以很麻煩很花時間，我們要想辦法避開。

因此我們應該一次分配N*4096/Bytes個記憶體做為大區塊，並只使用N-1個4096/Bytes的小區塊做為真正可用的記憶體空間，為啥呢？因為每一個Page都是從0x?????000，假設我們任意取連續N個Page大小的空間，必然會完整包含N-1個真正Page，而以Page當小區塊化分空間就不會經常越過Page界線引起置換囉。

FreeList---緊湊實用的資料結構

說到維護空間，其實空間跟數值也沒什麼不同，都只是一些數字，考慮每次需要的記憶體大小不同，串列似乎是個好選擇，只要在開頭附加該空間的實際大小，維護空間應該就不是問題對吧？才怪呢，假設可以申請任意大小個記憶體的話，已經可用的空間就需要線性時間才能找到足夠大小的記憶體啦，這時候你可能會想到排序，不過把時間耗損丟到釋放空間時才做，似乎也不是明智的選擇，你有沒有考慮過Hash？

是的Hash，可是Hash需要轉換函數，這應該只會讓事情更慢吧？理論上是沒錯的，但事實上改變點細節就行了，我們只能使用8的倍數個Bytes個空間，而且最多只能到256，如此一來只需要32個桶，轉換函數就是除8如何？你可能會覺得我發瘋了，既然最多只到256，那為什麼不以1為單位呢？假設我只要3個空間放不就浪費了5個？太浪費了！

冷靜想想你會發現，如果我真的一次最小發一個Byte，那麼在維護時我就必須附帶上另外8個Bytes(64位元系統)來告訴系統下一個可用空間在哪裡了，1~7/8的浪費對比1/8的浪費，勝負分曉了，因為假設一個基本的可用空間有8Bytes，那麼在分配出去之前，裡面可以存放下一個可用區域的位置！示範如下：


struct Memory_pool
    {
    uint8_t * free_blocks;
    uint16_t free_block_number;
    };
...
// 假設還有空間可用


    if ( *( (uint8_t **) pool->free_blocks ) ) // pool->free_blocks中存放下一個可用的位置的位置
        {
        pool->free_blocks = *( (uint8_t **) pool->free_blocks );
        }
    else // 如果為NULL表示可以直接從現在位置往後找
        {
        // pool_size表示這個pool專案分配的空間的大小
        pool->free_blocks =  pool->free_blocks + pool_size;
        *( (uint8_t **)pool->free_blocks ) = NULL;
        }


此靈活的結構稱為FreeList

結論

每次一個大塊記憶體時會浪費4096Bytes，每分配一次空間平均浪費3.5Bytes，在4096Bytes裡等分各種大小的空間零零總總會剩3千多Bytes，而速度至少會快3~4倍，申請&釋放空間的頻率越高，優勢會越來越明顯，這是由於分配時使用一次Hash根指標取值就能找到空間，而且釋放時只要一次Byte Mask就能找到所屬的Pool把空間還回去，把到這裡我才發現我忘了說階層大小的記憶體管理，看樣子我只好附上示範程式了。