一種高效的C++固定內存塊分配器

簡介

自定義固定內存塊分配器用于解決兩種類型的內存問題。第一，全局堆內存的分配和釋放非常慢而且是不確定的。你不能確定內存管理需要消耗多長時間。第二，降低由堆內存碎片（對于執行關鍵操作的系統尤為重要）造成的內存分配失敗的可能性。

即使不是執行關鍵操作的系統，一些嵌入式系統也需要被設計成需要運行數周甚至數年而不重啟。取決于內存分配的模式和堆內存的實現方式，長時間的使用堆內存可能導致堆內存錯誤。

典型的解決方案是預先靜態聲明所有對象的內存，從而擺脫動態申請內存。然而，由于對象即使沒有被使用，也已經存在并占據一部分內存，靜態分配內存的方式會浪費內存存儲。此外，使用動態內存分配方式實現的系統提供更為自然的設計框架，而不像靜態內存分配需要事先分配所有對象。

固定內存塊分配器并不是一種新的方法。人們已經設計過多種自定義內存分配器很長時間了。這里，我提供的是我在很多項目中成功使用的，一種簡單的C++內存分配器的實現。

這種分配器的實現具有如下特點：

• 比全局堆內存速度快
• 消除堆內存碎片錯誤
• 不需要額外的內存存儲（除了需要幾個字節的靜態內存）
• 易于使用
• 代碼量很小

這里將提供一個申請、釋放內存的，包含上面所提到特點的簡單類。

回收內存存儲

內存管理模式的基本哲學是在對象內存分配時能夠回收內存。一旦在內存中創建了一個對象，它所占用的內存就不能被重新分配。同時，內存要能夠回收，允許相同類型的對象重用這部分內存。我實現了一個名為Allocator的類來展示這些技巧。

當應用程序使用Allocator類進行刪除時，對象占用的內存空間被釋放以備重用，但卻不會立即釋放給內存管理器，這些內存保留在就一個稱之為“釋放列表”的鏈表中，并再次分配給相同類型的對象。對每個內存分配的請求，Allocaor類首先檢查“釋放列表”中是否存在待釋放的內存。只有“釋放列表”中沒有可用的內存空間時才會分配新的內存。根據所需的Allocator類的行為，內存存儲以三種操作模式使用全局堆內存或者靜態內存池。

• 1.堆內存
• 2.堆內存池
• 3.靜態內存池

堆內存 vs. 內存池

Allocator類在“釋放列表”為空時，能夠從堆內存或者內存池中申請新內存。如果使用內存池，你必須事先確定好對象的數量。確保內存池足夠容納所有需要使用的對象。另一方面，使用堆內存沒有數量大小的限制——可以構造內存允許的盡可能多的對象。

堆內存模式在全局堆內存上為對象分配內存。釋放操作將這塊內存放入“釋放了列表”以備重用。當“釋放列表”為空時，需要在堆內存上創建新內存。這種方式提供了動態內存的分配和釋放，優點是內存塊可以在運行時動態增加，缺點是內存塊創建期間是不確定的，可能創建失敗。

堆內存池模式從全局堆內存創建一個內存池。當Allocator類對象創建時，使用new操作符創建內存池。然后使用內存池中的內存塊進行內存分配。

靜態內存池模式使用從靜態內存中分配的內存池。靜態內存池由使用者進行分配而不是由Allocator對象進行創建。

堆內存池模式和靜態內存池模式提供了內存操作的連續使用，因為內存分配器不需要分配單獨的內存塊。這樣分配內存的過程是十分快速且具有確定性的。

類設計

類的接口很簡單。Allocate()返回指向內存塊的指針，Deallocate()釋放內存以備重用。構造函數需要設置對象的大小，并且如果使用內存池，需要分配內存池空間。

類的構造函數中的參數用于決定內存塊分配的位置。size參數控制固定內存塊的大小。objects參數設置申請內存塊的個數，其值為0表示從堆內存中申請新內存塊，非0表示使用內存池方式（堆內存池或者靜態內存池）分配對象實例空間。memory參數是指向靜態內存的指針。如果memory等于0并且objects非零，Allocator將從堆內存中創建一個內存池。靜態內存池內存大小必須是size*object字節。name參數為內存分配器命名，用于收集分配器使用信息。

class Allocator {
public:
    Allocator(size_t size, UINT objects=0, CHAR* memory=NULL, const CHAR* name=NULL);
...

下面的例子展示三種分配器模式中的構造函數是如何賦值的。

// Heap blocks mode with unlimited 100 byte blocks
Allocator allocatorHeapBlocks(100);

// Heap pool mode with 20, 100 byte blocks
Allocator allocatorHeapPool(100, 20);
// Static pool mode with 20, 100 byte blocks
char staticMemoryPool[100  20];
Allocator allocatorStaticPool(100, 20, staticMemoryPool);</code></pre> 
  
為了簡化靜態內存池方法，提供AllocatorPool<>模板類。模板的第一個參數設置申請內存對象類型，第二個參數設置申請對象的數量。
 
  
// Static pool mode with 20 MyClass sized blocks 
AllocatorPool<MyClass, 20> allocatorStaticPool2;
 
  
Deallocate()將內存地址放入“棧”中。這個“棧”的實現方式類似于單項鏈表（“釋放列表”），但是只能添加、移除頭部的對象，其行為類似棧的特性。使用“棧”使得分配、釋放操作更為快速，因為不需要全鏈表遍歷而只需要壓入和彈出操作。
 
  
void memory1 = allocatorHeapBlocks.Allocate(100);</code></pre> 
  
這樣便在不增加額外存儲的情況下，將內存塊鏈接在“釋放列表”中。例如，當我們使用全局operate new時，首先申請內存，然后調用構造函數。delete的過程與此相反，首先調用析構函數，然后釋放掉內存。調用完析構函數后，在內存釋放給堆之前，這塊內存不再被原有的對象使用，而是放到“釋放列表”中以備重用。由于Allocator類需要保存已經釋放的內存塊，在使用delete操作符時，我們將“釋放列表”中的下一個指針指向這個被delete的對象內存地址。當應用程序再次使用這塊內存時，指針被覆寫為對象的地址。通過這種方法，就不需要預先實例化內存空間。
 
  
使用釋放對象的內存來將內存塊連接在一起意味著對象的內存空間需要足夠容納一個指針占用內存空間的大小。構造函數初始化列表中的代碼保證了最小內存塊大小不會小于指針占用內存塊的大小。
 
  
類的析構函數通過釋放堆內存池或者遍歷“釋放列表”并逐個釋放內存塊來實現內存的釋放。由于Allocator類對象常被用作是static的，那么Allocator對象的釋放是在程序結束時。對于大多數嵌入式設備，應用只在人們拔斷電源時才會結束。因此，對于這種嵌入式設備，析構函數的作用就顯無所謂了。
 
  
如果使用堆內存塊模式，除非所有分配的內存被鏈接在“釋放列表”，應用結束時分配的內存塊不能被釋放。因此，所有對象應該在程序結束時被“刪除”（指放入“釋放列表”）。這似乎是內存泄漏，也帶來了一個有趣的問題。Allocator應該跟蹤正在使用和已經釋放的內存塊嗎？答案是否定的。以為一旦一塊內存通過指針被應用所使用，那么應用程序有責任在程序結束前通過調用Deallocate()返回該內存塊指針給Allocator。這樣的話，我么只需要跟蹤釋放的內存塊。
 
  
代碼的使用
 
  
Allocator易于使用，因此創建宏來自動在客戶端類中實現接口。宏提供一個靜態類型的Allocator實例和兩個成員函數：操作符new和操作符delete。通過重寫new和delete操作符，Allocator截取并處理所有的客戶端類的內存分配行為。
 
  
DECLARE_ALLOCATOR宏提供頭文件接口，并且應該在類定義時將其包含在內，如下面這樣：
 
  
#include "Allocator.h"
class MyClass
{
    DECLARE_ALLOCATOR
    // remaining class definition
};
 
  
操作符new函數調用Allocator創建類實例所需要的內存空間。內存分配后，根據定義，操作符new調用該類的構造函數。重寫的new只修改了內存的分配任務。構造函數的調用由語言保證。刪除對象時，系統首先調用析構函數，然后調用執行操作符delete函數。操作符delete使用Deallocate()函數將內存塊加入到“釋放列表”中。
 
  
盡管沒有明確聲明，操作符delete是靜態函數（靜態函數才能調用靜態成員）。因此它不能被聲明為virtual。這樣看上去通過基類的指針刪除對象不能達到刪除真實對象的目的。畢竟，調用基類指針的靜態函數只會調用基類的成員函數，而不是其真實類型的成員函數。然而，我們知道，調用操作符delete時首先調用析構函數。修飾為virtual的析構函數會實際調用子類的析構函數。類的析構函數執行完后，子類的操作符delete函數被調用。因此實際上，由于虛析構函數的調用，重寫的操作符delete會在子類中調用。所以，使用基類指針刪除對象時，基類對象的析構函數必須聲明為virtual。否則，將會不能正確調用析構函數和操作符delete。
 
  
IMPLEMENT_ALLOCATOR宏是接口的源文件實現部分，并應該放置于源文件中。
 
  
IMPLEMENT_ALLOCATOR(MyClass, 0, 0)
 
  
使用上述宏后，可以如下面一樣創建并銷毀類的實例，同事循環使用釋放的內存空間。
 
  
MyClass* myClass = new MyClass();
delete myClass;
 
  
Allocator類支持單繼承和多繼承。例如，Derived類繼承Base類，如下代碼是正確的。
 
  
Base* base = new Derived;
delete base;
 
  
運行時
 
  
運行時，Allocator初始化時“釋放列表”中沒有可重用的內存塊。因此，第一次調用Allocate()將從內存池或者堆中獲取內存空間。隨著程序的執行，系統不斷使用對象會造成分配器的波動。并且只有當釋放列表無法提供內存時，新內存才會被申請和創建。最終，系統使用對象的實例會固定，因此每次內存分配將會使用已經存在的內存空間二不是再從內存池或者堆中申請。
 
  
與使用內存管理器分配所有對象內存相比，Allocator分配器更加高效。內存分配時，內存指針僅僅是從“釋放列表”中彈出，速度非常快。內存釋放時也僅僅是將內存指針放入到“釋放列表”當中，速度也十分快。
 
  
基準測試
 
  
在Windows PC上使用Allocator和全局堆內存的對比性能測試顯示出Allocator的高性能。測試分配和釋放20000個4096和2048大小的內存塊來測試分配和釋放內存的速度。測試的算法詳見附件中的代碼。
 
  
 
   
 
    
 
     
Allocator
 
     
Mode
 
     
Run
 
     
Benchmark Time (mS)
 
    
 
    
 
     
Global Heap
 
     
Debug Heap
 
     
1
 
     
1640
 
    
 
    
 
     
Global Heap
 
     
Debug Heap
 
     
2
 
     
1864
 
    
 
    
 
     
Global Heap
 
     
Debug Heap
 
     
3
 
     
1855
 
    
 
    
 
     
Global Heap
 
     
Release Heap
 
     
1
 
     
55
 
    
 
    
 
     
Global Heap
 
     
Release Heap
 
     
2
 
     
47
 
    
 
    
 
     
Global Heap
 
     
Release Heap
 
     
3
 
     
47
 
    
 
    
 
     
Allocator
 
     
Static Pool
 
     
1
 
     
19
 
    
 
    
 
     
Allocator
 
     
Static Pool
 
     
2
 
     
7
 
    
 
    
 
     
Allocator
 
     
Static Pool
 
     
3
 
     
7
 
    
 
    
 
     
Allocator
 
     
Heap Blocks
 
     
1
 
     
30
 
    
 
    
 
     
Allocator
 
     
Heap Blocks
 
     
2
 
     
7
 
    
 
    
 
     
Allocator
 
     
Heap Blocks
 
     
3
 
     
7
 
    
 
   
 
  
 
  
使用調試模式執行時，Windows使用調試堆內存。調試堆內存添加額外的安全檢查降低了性能。發布堆內存性能更好，因為不使用安全檢查。通過在Visual Studio工程選項中，設置【調試】-【環境】中_NO_DEBUG_HEAP=1來禁止調試內存模式。
 
  
全局調試堆內存模式需要平均1.8秒，是最慢的。釋放對內存模式50毫秒左右，稍快。基準測試的場景非常簡單，實際情況下，不同大小的內存塊和隨機的申請、釋放可能產生不同的結果。然而，最簡單的也最能說明問題。內存管理器比Allocator內存分配器慢，并且很大程度上依賴于平臺的實現能力。
 
  
內存分配器Allocator使用靜態內存模式不依賴于堆內存的分配。一旦“釋放列表”中含有內存塊后，其執行時間大約為7毫秒。第一次耗時19毫秒用于將內存池中的內存防止到Allocator分配器中管理。
 
  
Aloocator使用堆內存模式時，當“釋放列表”中有可重用的內存后，其速度與靜態內存模式一樣快。堆內存模式依賴于全局堆來獲取內存塊，但是循環利用“釋放列表”中的內存。第一次需要申請堆內存，耗時30毫秒。由于重用“釋放列表”中的內存，之后的申請僅需要7毫秒。
 
  
上面的基準測試結果表示，Allocator內存分配器更加高效，擁有7倍于Windows全局發布堆內存模式的速度。
 
  
對于嵌入式系統，我使用Keil在ARM STM32F4 CPU（168Hz）上運行相同測試。由于資源限制，我將最大內存塊數量降低到500，單個內存塊大小降低到32和16字節。下面是結果：
 
  
 
   
 
    
 
     
Allocator
 
     
Mode
 
     
Run
 
     
Benchmark Time (mS)
 
    
 
    
 
     
Global Heap
 
     
Release
 
     
1
 
     
11.6
 
    
 
    
 
     
Global Heap
 
     
Release
 
     
2
 
     
11.6
 
    
 
    
 
     
Global Heap
 
     
Release
 
     
3
 
     
11.6
 
    
 
    
 
     
Allocator
 
     
Static Pool
 
     
1
 
     
0.85
 
    
 
    
 
     
Allocator
 
     
Static Pool
 
     
2
 
     
0.79
 
    
 
    
 
     
Allocator
 
     
Static Pool
 
     
3
 
     
0.79
 
    
 
    
 
     
Allocator
 
     
Heap Blocks
 
     
1
 
     
1.19
 
    
 
    
 
     
Allocator
 
     
Heap Blocks
 
     
2
 
     
0.79
 
    
 
    
 
     
Allocator
 
     
Heap Blocks
 
     
3
 
     
0.79
 
    
 
   
 
  
 
  
基于ARM的基準測試顯示，使用Allocator分配器的類性能快15倍。這個結果會讓Keil堆內存的表現相形見絀。基準測試分配500個16字節大小的內存塊進行測試。每個16字節大小的內存刪除后申請500個32字節大小的內存塊。全局堆內存耗時11.6毫秒，而且，在內存碎片化后，內存管理器可能會在沒有安全檢查的情況下耗時更大。
 
  
分配器決議
 
  
第一個決定是你是否需要使用分配器。如果你的項目不關心執行的速度和是否需要容錯，那么你可能不需要自定義的分配器，全局堆分配管理器足夠用了。
 
  
另一方面，如果你需要考慮執行速度和容錯管理，分配器會起到作用。你需要根據項目的需要選擇分配器的模式。重要任務系統的設計可能強制要求使用全局堆內存。而動態分配內存可能更高效，設計更優雅。這種情況下，你可以在調試開發時使用堆內存模式獲取內存使用參數，然后發布時切換到靜態內存池模式避免內存分配帶來的性能消耗。一些編譯時的宏可用于模式的切換。
 
  
另外，堆內存模式可能對應用更適合。該模式利用堆來獲取新內存，同時阻止了堆碎片錯誤。當“釋放列表”鏈接足夠的內存塊后更能加快內存的分配效率。
 
  
在源代碼中沒有實現的涉及多線程的問題不在本文的討論范圍內。運行系統一會后，可以方便地使用GetlockCount函數和GetName函數獲取內存塊數量和名稱。這些度量參數提供關于內存分配的信息。盡量多申請點內存，以便給分配盤一些彈性來避免內存耗盡。
 
  
調試內存泄漏
 
  
調試內存泄漏非常困難，原因是堆內存就像一個黑盒，對于分配對象的類型和大小是不可見的。使用Allocator，由于Allocator跟蹤記錄內存塊的總數，內存泄漏檢查變得簡單一點。對每個分配器實例重復輸出（例如輸出到終端）GetBlockCount和GetName并比對它們的不同能讓我們更好的了解分配器對內存的分配。
 
  
錯誤處理
 
  
C++中使用new_handler函數處理內存分配錯誤。如果內存管理器在申請內存時發生錯誤，用戶的錯誤處理函數就會被調用。通過將用戶的錯誤處理函數地址復制給new_handler，內存管理器就能調用用戶自定義的錯誤處理程序。為了讓Allocator類的錯誤處理機制與內存管理器保持一致，分配器也通過new_handler調用錯誤處理函數，集中處理所有的內存分配錯誤。
 
  
static void out_of_memory() {
    // new-handler function called by Allocator when pool is out of memory
    assert(0);
}

int _tmain(int argc, _TCHAR* argv[]) {
    std::set_new_handler(out_of_memory);
...</code></pre> 
  
限制
 
  
分配器類不支持數組對象的內存分配。為每一個對象創建分開的內存是無法保證的，因為new的多次調用不保證內存塊的連續，但這又是數組所需要的。因此Allocator只支持固定大小內存塊的分配，對象數組不支持。
 
  
移植問題
 
  
Allocator在靜態內存池耗盡時調用new_handle指向的函數，這對于某些系統不合適。假設new_handle函數沒返回，例如無盡的循環或者斷言，調用這個函數不起任何作用。使用固定內存池時這無濟于事。
 
  
 
 
  
 
 
  
來自：http://developer.51cto.com/art/201701/528438.htm