無分區內存管理器？

有人想過如何編寫一個完全沒有分支的內存管理器（使用C++）？我已經編寫了一個池，一個堆棧，一個隊列和一個鏈表（從池中分配），但我想知道編寫一個免分支的內存管理器有多合理。無分區內存管理器？

這都是爲了幫助構建一個真正可重用的框架，用於實現可靠的併發，有序CPU和緩存友好的開發。

編輯：無分支我的意思是沒有做直接或間接函數調用，也沒有使用ifs。我一直在想，我可能會實現一些首先將所需大小更改爲零的錯誤調用，但實際上並沒有比這更多。我覺得這不是不可能的，但是這個練習的另一個方面就是在所謂的「不友好」的處理器上對它進行分析，看看它是否值得這樣努力以避免分支。

來源

2010-03-22 Richard Fabian

你是什麼意思的「分支」？ – 2010-03-22 10:23:08

@Neil，我想，這是分裂控制流的東西（例如'if'運算符）。 – 2010-03-22 10:30:48

如果分支意味着「如果」，那麼答案是否定的。 @OP：請你澄清一下，如果這確實是你的意思？ – 2010-03-22 11:10:52

雖然我不認爲這是一個好主意，一個解決辦法是有各種日誌的預分配桶大小，愚蠢的僞代碼：

class Allocator { 

    void* malloc(size_t size) { 
     int bucket = log2(size + sizeof(int)); 
     int* pointer = reinterpret_cast<int*>(m_buckets[bucket].back()); 
     m_buckets[bucket].pop_back(); 
     *pointer = bucket; //Store which bucket this was allocated from 
     return pointer + 1; //Dont overwrite header 
    } 

    void free(void* pointer) { 
     int* temp = reinterpret_cast<int*>(pointer) - 1; 
     m_buckets[*temp].push_back(temp); 
    } 

    vector< vector<void*> > m_buckets; 
};

（當然，你也用一個簡單的數組+計數器替換std::vector）。

編輯：爲了使這個強大的（即處理桶是空的情況），你將不得不添加某種形式的分支。

EDIT2：這裏有一個小網點log2功能：

//returns the smallest x such that value <= (1 << x) 
int 
log2(int value) { 
    union Foo { 
     int x; 
     float y; 
    } foo; 
    foo.y = value - 1; 
    return ((foo.x & (0xFF << 23)) >> 23) - 126; //Extract exponent (base 2) of floating point number 
}

這爲分配< 33554432字節正確的結果。如果你需要更大的分配，你將不得不切換到雙打。

這裏是一個link浮點數如何表示在內存中。

來源

2010-03-22 11:13:03

Log2可能需要依賴於平臺的實現才能無分支。在x86上，您可能需要對參數進行BSR指令。 – 2010-03-22 11:33:19

@Jasper：這裏有一些代碼聲稱是無分區clz - 我假設沒有測試它的工作原理：http://stackoverflow.com/questions/2255177/finding-the-exponent-of-n-2x-using-按位操作 - 對數 - 在基-2-的/ 2255282＃2255282。從簡單的瀏覽，它似乎返回0輸入0，所以你可能想要一個分支覆蓋0情況，或大於一半的範圍的情況。正如你所說，雖然，實現可能提供更快的CPU操作。 – 2010-03-22 11:44:45

@Jasper @Steve看我的編輯。 – 2010-03-22 12:24:38

我知道創建一個真正的無分配分配器的唯一方法是預先保存所有可能使用的內存。否則總是會有一些隱藏的代碼在某處，以查看我們是否超出了某個當前容量，無論它是否處於向量中的隱藏push_back，以檢查該大小是否超過用於實現該容量的容量或類似內容。

下面是一個固定分配的例子，它有一個完全無分支malloc和free方法。

class FixedAlloc 
{ 
public: 
    FixedAlloc(int element_size, int num_reserve) 
    { 
     element_size = max(element_size, sizeof(Chunk)); 
     mem = new char[num_reserve * element_size]; 

     char* ptr = mem; 
     free_chunk = reinterpret_cast<Chunk*>(ptr); 
     free_chunk->next = 0; 

     Chunk* last_chunk = free_chunk; 
     for (int j=1; j < num_reserve; ++j) 
     { 
      ptr += element_size; 
      Chunk* chunk = reinterpret_cast<Chunk*>(ptr); 
      chunk->next = 0; 
      last_chunk->next = chunk; 
      last_chunk = chunk; 
     } 
    } 

    ~FixedAlloc() 
    { 
     delete[] mem; 
    } 

    void* malloc() 
    { 
     assert(free_chunk && free_chunk->next && "Reserve memory exhausted!"); 
     Chunk* chunk = free_chunk; 
     free_chunk = free_chunk->next; 
     return chunk->mem; 
    } 

    void free(void* mem) 
    { 
     Chunk* chunk = static_cast<Chunk*>(mem); 
     chunk->next = free_chunk; 
     free_chunk = chunk; 
    } 

private: 
    union Chunk 
    { 
     Chunk* next; 
     char mem[1]; 
    }; 
    char* mem; 
    Chunk* free_chunk; 
};

因爲它是完全的無網點，它只是如果你嘗試分配更多的內存比最初保留出現segfaults。它也有試圖釋放空指針的未定義行爲。爲了更簡單的例子，我也避免了對齊。

來源

2015-05-01 09:09:30

無分區內存管理器？

回答

相關問題