memory pool的基本實作技巧

memory pool是實現客制化的allocator的常見手法，尤其是對快速的alloc/free有很高要求的環境。之所以可以有較快速的alloc/free，是因為memory pool的特性 - 每個pool中的基本block的大小是一樣的，而alloc時，所要求的memory也都是一個block。怎麼利用這個特性來實作快速的alloc/free呢？以Linux kernel為例，我們可以看到：

static void add_element(mempool_t *pool, void *element)
{
        BUG_ON(pool->curr_nr >= pool->min_nr);
        pool->elements[pool->curr_nr++] = element;
}

static void *remove_element(mempool_t *pool)
{
        BUG_ON(pool->curr_nr <= 0);
        return pool->elements[--pool->curr_nr];
}

pool->elments[]是在使用者呼叫mempool_create(...)時所動態建立，存放的是一組void *，指向實際可被使用的memory block。當呼叫mempool_alloc(...)時，經過一些檢查與處理，就會呼叫到remove_element(...)，回傳指到的memory block的位址，然後將下一次要給出的block位址由pool->curr_nr去索引。很簡單又快速的便完成alloc，free則是類似的反向動作而已。

太簡單了吧？你這麼想著。沒錯，但有人寫出類似如下的實作（當然，是簡化的版本，不過意思到了 :P）：

static struct block *remove_element(mempool *pool)
{
    struct block *blk= NULL;
    int search_from = search_start;

    while(pool[search_start].allocated == 1) {
        if(search_start == MAX_POOL-1)
            search_start = 0;
        else
            search_start++;
        if(search_from == search_start)
            break;
    }

    if(pool[search_start].allocated == 0) {
        pool[search_start].allocated=1;
        blk=&pool[search_start];

        if(search_start == MAX_POOL-1)
            search_start = 0;
        else
            search_start++;
    }

     return blk;

}

嗯...為什麼會變成這麼冗長又沒效率呢（linear search）？因為在實作時，作者沒有注意到，pool裡的block handle應該與實際的block分開。所以在建pool時，就以block作為pool的基本單位，在alloc時就直接回傳block的位址，造成當free的順序是隨機的時候，pool裡的block的使用狀況就不一樣，為了找出閒置的block就多加了一個status欄位，然後用linear search的方式去查找。

嘿，這個是實際的產品（賣了不少錢）的程式碼喔～寫這段code的工程師也都是令人信賴的好手呦～這段code也是處於重要的執行路徑上呦～從這邊學到的一課就是 - 思考優秀軟體的每一個小細節（ex: Linux kernel），並且讓有效且優雅的小技巧變成自身的習慣，這樣才能減少產生意外的效能瓶頸（這個例子還包括了可讀性的降低）。