分配/釋放大量小物體的策略

我正在嘗試使用某些緩存算法，這在某種程度上具有挑戰性。基本上，它需要分配很多小對象（雙數組，1到256個元素），對象可以通過映射值map[key] = array訪問。初始化數組的時間可能相當長，一般超過10萬cpu週期。分配/釋放大量小物體的策略

我的意思是總計大約是千兆字節。物體可能需要根據需要彈出/推動，通常在隨機的地方，一次一個物體。一個對象的生命週期通常很長，幾分鐘或更長，但是，對象在編程期間可能會多次分配/釋放。

什麼是避免內存碎片的好策略，同時仍然保持合理的分配釋放速度？

我使用的是C++，所以我可以使用new和malloc。謝謝。

我知道網站上有類似的問題，Efficiently allocating many short-lived small objects，有些不同，線程安全對我來說不是直接的問題。

我的開發平臺是Intel Xeon，linux操作系統。理想情況下，我想在PPC linux上工作，但它對我來說不是最重要的。

來源

2010-03-13 Anycorn

什麼是平臺？我的意思是，操作系統，CPU架構，編譯器等，這些可能會大大影響答案。 – 2010-03-13 18:51:10

創建開槽分配：

分配器與內存的許多頁，每一頁大小相等（512K，256K，規模應該調整爲您的使用）的創建。

對象第一次詢問這個分配器的內存時，它分配一個頁面。分配頁面包括從空閒列表中刪除它（不搜索，所有頁面大小相同）並設置將在此頁面上分配的對象的大小。通常這個大小是通過獲取請求的大小並將其四捨五入到最接近的2來計算的。隨後的相同大小的分配只需要一點點指針數學並增加頁面上的對象數量。

由於插槽大小完全相同，可以在後續分配時重新填充，因此可以防止碎片。效率得以保持（在某些情況下得到改進），因爲每個分配都沒有memheader（當分配量很小時，一旦分配變大，分配器開始浪費幾乎50％的可用內存，這會造成很大的差異）。

分配和解除分配都可以在固定時間內執行（不會搜索空閒列表中的正確時隙）。關於解除分配的唯一棘手的部分是，您通常不希望在分配之前使用memheader，因此您必須自己計算頁面和索引。這是星期六，我沒有喝過咖啡，所以我對此沒有任何好的建議，但從解除分配的地址中找出來很容易。

編輯：這個答案有點囉嗦。像往常一樣boost有你的背影。

來源

2010-03-13 19:09:06

而Boost在池庫中實現了這一點。 – GManNickG 2010-03-13 19:21:07

如果您確實知道數組的最大大小，則可以使用自定義分配器。你將不得不自己編寫分配器類。它應該做的是一次分配一大塊內存並將其轉換爲鏈表。每次需要創建對象實例時，都會從列表中刪除尾部。每次需要釋放對象時，都會向列表中添加一個條目。

編輯：這裏是從Bjarne的Stroustrup的的C++編程語言的樣本，第三版：

class Pool 
{ 
private: 
    struct Link 
    { Link * next; }; 

    struct Chunk 
    { 
    enum {size = 8*1024-16}; 

    Chunk * next; 
    char mem[size]; 
    }; 

private: 
    Chunk * chunks; 
    const unsigned int esize; 
    Link * head; 

private: 
    Pool (const Pool &) { }  // copy protection 
    void operator = (Pool &) { } // copy protection 

public: 
    // sz is the size of elements 
    Pool(unsigned int sz) 
    : esize(sz < sizeof(Link*) ? sizeof(Link*) : sz), 
     head(0), chunks(0) 
    { } 

    ~Pool() 
    { 
    Chunk * n = chunks; 

    while(n) 
    { 
     Chunk * p = n; 
     n = n->next; 
     delete p; 
    } 
    } 


public: 

    // allocate one element 
    void * alloc() 
    { 
    if(head == 0) 
     grow(); 

    Link * p = head; 
    head = p->next; 

    return p; 
    } 

    // put an element back into the pool 
    void free(void * b) 
    { 
    Link * p = static_cast<Link*>(b); 
    p->next = head; //put b back as first element 
    head = p; 
    } 

private: 
    // make pool larger 
    void grow() 
    { 
    Chunk* n = new Chunk; 
    n->next = chunks; 
    chunks = n; 

    const int nelem = Chunk::size/esize; 
    char * start = n->mem; 
    char * last = &start [ (nelem - 1) * esize ]; 

    for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize 
     reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize); 

    reinterpret_cast<Link *>(last)->next = 0; 
    head = reinterpret_cast<Link *>(start); 
    } 
};

來源

2010-03-13 18:51:35 Kerido

這個答案有點含糊，但聽起來像是告訴他要重新實現已經在OS內存分配器中的「自由列表」。除非他的名單實際上是一個更智能的數據結構，否則他仍然會遇到主要的內存碎片減速。 – 2010-03-13 18:55:27

@ALevy：這不能分片，因爲所有的塊都是相同的大小。 – 2010-03-13 19:37:33

@ALevy：因爲我建議分配單一大小的元素，所以不會出現碎片。大小應該選擇足以存儲@aaa提到的數組。關於速度，它比調用OS內置分配例程要快。如果Chunks是一個內存頁面的大小並且用@DanO提到的頁面分配例程分配的話，它可以更快。關於「模糊性」，太糟糕了，你已經低估了。 – Kerido 2010-03-13 19:44:55

如果你能預測的分配對象的大小提前時間，你可能會是最好的去與一個線性分配的內存塊和您自己的自定義分配器（如@Kerido建議）。爲此，我想補充一點，最有效的方法是在分配內置零和交換位置，而不用擔心重新分區和壓縮數組（在分配之間留下死區），因此您不必處理索引更新和索引保養。

如果您可以提前對對象進行分區（即，您知道有非固定大小的元素，但是組很容易）將它們分成桶，並將大塊內存預先分配到每個桶中，並將這些項交換爲適當的桶。如果您的對象可以在其整個生命週期中更改大小，並且可能會非常棘手，那麼請仔細考慮此方法。

來源

2010-03-13 18:57:31 GrayWizardx

桶的想法聽起來不錯 – Anycorn 2010-03-13 18:59:13

分配/釋放大量小物體的策略

回答

相關問題