關於改進分配器算法實現的建議

Question

我有一個Visual Studio 2008 C++應用程序，我正在使用標準容器的自定義分配器，以使它們的內存來自內存映射文件而不是堆。這個分配器用於4種不同的用例：

1. 104字節的固定尺寸的結構std::vector< SomeType, MyAllocator<SomeType> > foo;
2. 200字節的固定尺寸結構
3. 304字節的固定尺寸結構
4. n字節串std::basic_string< char, std::char_traits<char>, MyAllocator<char> > strn;

我需要能夠爲其中每一個分配大致32MB的總計。

分配程序使用指向分配大小的指針跟蹤內存使用情況。每個超級塊代表4MB的內存。

有一個std::vector<SuperBlock>這些萬一一個超級塊沒有足夠的空間。

用於分配的算法是這樣的：

1. 對於每個超級塊：是否有空間在超級塊的結束？把分配放在那裏。 （快）
2. 如果不是，則在每個超級塊內搜索足夠大小的空白空間並將其分配到那裏。 （慢）
3. 還沒什麼？分配另一個超級塊，並將分配放在新超級塊的開始處。

不幸的是，步驟2在一段時間後會變得非常慢。隨着對象的拷貝和臨時變量的銷燬，我得到了很多碎片。這會導致在內存結構中進行大量的深層搜索。由於我的內存數量有限（請參閱下面的註釋），因此存在碎片問題。

有人可以提出改進此算法以加快此過程嗎？我是否需要兩個獨立的算法（1個用於固定大小的分配，另一個用於字符串分配器）？

注意：對於那些需要一個原因：我在Windows Mobile中使用此算法，其中有一個32MB的進程槽限制堆。所以，通常std::allocator不會削減它。我需要將分配放在1GB的大內存區域中，以獲得足夠的空間，這就是它的功能。

Answer 1

對於固定大小的對象，可以創建一個固定大小的分配器。基本上，你分配塊，分區到適當大小的子塊，並創建一個鏈接列表與結果。如果存在可用內存（僅從列表中移除第一個元素並返回一個指向它的指針），則從這樣的塊分配O（1），就像釋放（將該塊添加到空閒列表）一樣。在分配過程中，如果列表爲空，請抓取新的超級塊，分區並將所有塊添加到列表中。

對於可變大小的列表，可以通過僅分配已知大小的塊將其簡化爲固定大小的塊：32字節，64字節，128字節，512字節。您將不得不分析內存使用情況，以提供不同的存儲桶，以免浪費太多內存。對於大型對象，您可以回到動態大小分配模式，這種模式會很慢，但希望大型對象的數量有限。

Answer 2

你可以有一個單獨的內存分配池爲你分配的每個不同的固定大小的類型？這樣就不會有任何碎片，因爲分配的對象將始終在n字節邊界上對齊。當然，這對於可變長度的字符串沒有幫助。

在Alexandrescu的Modern C++ design中有一個小對象分配的例子，它說明了這個原理，可能會給你一些想法。

Answer 3

對於固定大小，您可以輕鬆地使用小內存分配器類型的分配器，您可以在其中分配一個分成固定大小塊的大塊。然後在分配/釋放時創建指向可用塊的指針矢量和彈出/推送。這非常快。

對於可變長度的項目，這很難：您必須處理搜索可用的連續空間或使用其他方法。您可能會考慮維護按塊大小排列的所有空閒節點的另一個映射，以便您可以降低映射的下限，並且如果下一個可用節點只有5％太大，則返回它，而不是嘗試查找確切大小的可用可用空間。

Answer 4

對於可變大小的項目，我的傾向是，如果可行的話，避免持有直接指向數據的指針，而是保持句柄。每個句柄都是超級塊的索引，並且是超級塊內的項目的索引。每個超級塊將有一個自上而下分配的項目列表和自下而上分配的項目。每個項目的分配之前都會有其長度，以及它所代表的項目的指數;使用索引的一位來指示項目是否被「固定」。

如果項目符合最後一個分配項目，則只需分配它即可。如果它會擊中固定項目，則將下一個分配標記移到固定項目之後，找到下一個更高的固定項目，然後再次嘗試分配。如果項目與項目列表相沖突，但是有足夠的可用空間，請壓縮塊的內容（如果一個或多個項目被固定，最好使用另一個超級塊，如果有的話）。根據使用模式，可能需要首先簡化自上次收集後添加的內容;如果這樣不能提供足夠的空間，那麼就要壓縮一切。

當然，如果只有幾個離散大小的項目，您可以使用簡單的固定大小塊分配器。

Answer 5

我同意蒂姆 - 使用內存池來避免碎片。

但是，您可以通過在向量中存儲指針而不是對象來避免某些流失，可能是ptr_vector？

Answer 6

基於Tim的回答，我會親自使用類似於BiBOP的東西。

基本思想很簡單：使用固定大小的池。

有一些改進。

首先，池的大小通常是固定的。這取決於你的分配例程，通常如果你知道你在使用malloc時一次至少4KB的操作系統，那麼你使用這個值。對於內存映射文件，您可能會增加此功能。

固定大小的池的優點是它很好地消除了碎片。所有頁面的大小相同，您可以輕鬆地將空白的256字節頁面回收到128字節頁面中。

大型對象仍然存在一些碎片，這些碎片通常在系統之外分配。但是它很低，特別是如果你將大對象放入頁面大小的倍數時，這樣內存將很容易回收。

二，如何處理泳池？使用鏈接列表。

這些頁面通常是無類型的（由他們自己），因此您有一個頁面的自由列表，用於準備新頁面並放置「回收」頁面。

對於每個大小類別，您都有一個「已佔用」頁面的列表，其中分配了內存。對於每個頁面你保持：

• 分配大小（本頁）
• 分配的對象（檢查空）的數量
• 一個指向第一個無細胞
• 指針上一頁和下一頁（可能指向列表的「頭」）

每個空閒單元本身都是一個指向下一個空閒單元的指針（或索引，具體取決於您的大小）。

的給定大小的「佔領」頁的列表只是管理：

• 上刪除：如果您清空頁面，然後從列表中刪除，並將其推入回收的網頁，否則，更新此頁面的免費單元列表（注：查找當前頁面的開始通常是對地址的簡單模運算）
• 插入時：只要您從頭開始搜索，只要找到非完整頁面，將它移到列表的前面（如果它還沒有）並插入您的物品

這種方案實際上是高性能的記憶方式，只有一個頁面保留索引。

對於多線程/多進程應用程序，您需要添加同步（通常爲每頁一個互斥鎖），以防萬一您可以從Google的tcmalloc中獲得靈感（嘗試找到另一個頁面而不是阻止，請使用線程本地緩存以記住您上次使用哪個頁面）。

話雖如此，你有沒有試過Boost.Interprocess？它提供了分配器。