簡介

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

[[182779]]

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

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

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

這種分配器的實現(xiàn)具有如下特點：

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

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

閱讀完此文后，請同時閱讀Replace malloc/free with a Fast Fixed Block Memory Allocator，查看如何使用分配器Allocator替代CRT（C/C++ Runtime Library）。

回收內(nèi)存存儲

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

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

• 1.堆內(nèi)存
• 2.堆內(nèi)存池
• 3.靜態(tài)內(nèi)存池

堆內(nèi)存 vs. 內(nèi)存池

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

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

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

靜態(tài)內(nèi)存池模式使用從靜態(tài)內(nèi)存中分配的內(nèi)存池。靜態(tài)內(nèi)存池由使用者進行分配而不是由Allocator對象進行創(chuàng)建。

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

類設計

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

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

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

下面的例子展示三種分配器模式中的構(gòu)造函數(shù)是如何賦值的。

// 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);

為了簡化靜態(tài)內(nèi)存池方法，提供AllocatorPool<>模板類。模板的***個參數(shù)設置申請內(nèi)存對象類型，第二個參數(shù)設置申請對象的數(shù)量。

// Static pool mode with 20 MyClass sized blocks 
AllocatorPool<MyClass, 20> allocatorStaticPool2;

Deallocate()將內(nèi)存地址放入“棧”中。這個“棧”的實現(xiàn)方式類似于單項鏈表（“釋放列表”），但是只能添加、移除頭部的對象，其行為類似棧的特性。使用“棧”使得分配、釋放操作更為快速，因為不需要全鏈表遍歷而只需要壓入和彈出操作。

void* memory1 = allocatorHeapBlocks.Allocate(100);

這樣便在不增加額外存儲的情況下，將內(nèi)存塊鏈接在“釋放列表”中。例如，當我們使用全局operate new時，首先申請內(nèi)存，然后調(diào)用構(gòu)造函數(shù)。delete的過程與此相反，首先調(diào)用析構(gòu)函數(shù)，然后釋放掉內(nèi)存。調(diào)用完析構(gòu)函數(shù)后，在內(nèi)存釋放給堆之前，這塊內(nèi)存不再被原有的對象使用，而是放到“釋放列表”中以備重用。由于Allocator類需要保存已經(jīng)釋放的內(nèi)存塊，在使用delete操作符時，我們將“釋放列表”中的下一個指針指向這個被delete的對象內(nèi)存地址。當應用程序再次使用這塊內(nèi)存時，指針被覆寫為對象的地址。通過這種方法，就不需要預先實例化內(nèi)存空間。

使用釋放對象的內(nèi)存來將內(nèi)存塊連接在一起意味著對象的內(nèi)存空間需要足夠容納一個指針占用內(nèi)存空間的大小。構(gòu)造函數(shù)初始化列表中的代碼保證了最小內(nèi)存塊大小不會小于指針占用內(nèi)存塊的大小。

類的析構(gòu)函數(shù)通過釋放堆內(nèi)存池或者遍歷“釋放列表”并逐個釋放內(nèi)存塊來實現(xiàn)內(nèi)存的釋放。由于Allocator類對象常被用作是static的，那么Allocator對象的釋放是在程序結(jié)束時。對于大多數(shù)嵌入式設備，應用只在人們拔斷電源時才會結(jié)束。因此，對于這種嵌入式設備，析構(gòu)函數(shù)的作用就顯無所謂了。

如果使用堆內(nèi)存塊模式，除非所有分配的內(nèi)存被鏈接在“釋放列表”，應用結(jié)束時分配的內(nèi)存塊不能被釋放。因此，所有對象應該在程序結(jié)束時被“刪除”（指放入“釋放列表”）。這似乎是內(nèi)存泄漏，也帶來了一個有趣的問題。Allocator應該跟蹤正在使用和已經(jīng)釋放的內(nèi)存塊嗎？答案是否定的。以為一旦一塊內(nèi)存通過指針被應用所使用，那么應用程序有責任在程序結(jié)束前通過調(diào)用Deallocate()返回該內(nèi)存塊指針給Allocator。這樣的話，我么只需要跟蹤釋放的內(nèi)存塊。

代碼的使用

Allocator易于使用，因此創(chuàng)建宏來自動在客戶端類中實現(xiàn)接口。宏提供一個靜態(tài)類型的Allocator實例和兩個成員函數(shù)：操作符new和操作符delete。通過重寫new和delete操作符，Allocator截取并處理所有的客戶端類的內(nèi)存分配行為。

DECLARE_ALLOCATOR宏提供頭文件接口，并且應該在類定義時將其包含在內(nèi)，如下面這樣：

#include "Allocator.h"
class MyClass
{
    DECLARE_ALLOCATOR
    // remaining class definition
};

操作符new函數(shù)調(diào)用Allocator創(chuàng)建類實例所需要的內(nèi)存空間。內(nèi)存分配后，根據(jù)定義，操作符new調(diào)用該類的構(gòu)造函數(shù)。重寫的new只修改了內(nèi)存的分配任務。構(gòu)造函數(shù)的調(diào)用由語言保證。刪除對象時，系統(tǒng)首先調(diào)用析構(gòu)函數(shù)，然后調(diào)用執(zhí)行操作符delete函數(shù)。操作符delete使用Deallocate()函數(shù)將內(nèi)存塊加入到“釋放列表”中。

盡管沒有明確聲明，操作符delete是靜態(tài)函數(shù)（靜態(tài)函數(shù)才能調(diào)用靜態(tài)成員）。因此它不能被聲明為virtual。這樣看上去通過基類的指針刪除對象不能達到刪除真實對象的目的。畢竟，調(diào)用基類指針的靜態(tài)函數(shù)只會調(diào)用基類的成員函數(shù)，而不是其真實類型的成員函數(shù)。然而，我們知道，調(diào)用操作符delete時首先調(diào)用析構(gòu)函數(shù)。修飾為virtual的析構(gòu)函數(shù)會實際調(diào)用子類的析構(gòu)函數(shù)。類的析構(gòu)函數(shù)執(zhí)行完后，子類的操作符delete函數(shù)被調(diào)用。因此實際上，由于虛析構(gòu)函數(shù)的調(diào)用，重寫的操作符delete會在子類中調(diào)用。所以，使用基類指針刪除對象時，基類對象的析構(gòu)函數(shù)必須聲明為virtual。否則，將會不能正確調(diào)用析構(gòu)函數(shù)和操作符delete。

IMPLEMENT_ALLOCATOR宏是接口的源文件實現(xiàn)部分，并應該放置于源文件中。

IMPLEMENT_ALLOCATOR(MyClass, 0, 0)

使用上述宏后，可以如下面一樣創(chuàng)建并銷毀類的實例，同事循環(huán)使用釋放的內(nèi)存空間。

MyClass* myClass = new MyClass();
delete myClass;

Allocator類支持單繼承和多繼承。例如，Derived類繼承Base類，如下代碼是正確的。

Base* base = new Derived;
delete base;

運行時

運行時，Allocator初始化時“釋放列表”中沒有可重用的內(nèi)存塊。因此，***次調(diào)用Allocate()將從內(nèi)存池或者堆中獲取內(nèi)存空間。隨著程序的執(zhí)行，系統(tǒng)不斷使用對象會造成分配器的波動。并且只有當釋放列表無法提供內(nèi)存時，新內(nèi)存才會被申請和創(chuàng)建。最終，系統(tǒng)使用對象的實例會固定，因此每次內(nèi)存分配將會使用已經(jīng)存在的內(nèi)存空間二不是再從內(nèi)存池或者堆中申請。

與使用內(nèi)存管理器分配所有對象內(nèi)存相比，Allocator分配器更加高效。內(nèi)存分配時，內(nèi)存指針僅僅是從“釋放列表”中彈出，速度非?？?。內(nèi)存釋放時也僅僅是將內(nèi)存指針放入到“釋放列表”當中，速度也十分快。

基準測試

在Windows PC上使用Allocator和全局堆內(nèi)存的對比性能測試顯示出Allocator的高性能。測試分配和釋放20000個4096和2048大小的內(nèi)存塊來測試分配和釋放內(nèi)存的速度。測試的算法詳見附件中的代碼。

使用調(diào)試模式執(zhí)行時，Windows使用調(diào)試堆內(nèi)存。調(diào)試堆內(nèi)存添加額外的安全檢查降低了性能。發(fā)布堆內(nèi)存性能更好，因為不使用安全檢查。通過在Visual Studio工程選項中，設置【調(diào)試】-【環(huán)境】中_NO_DEBUG_HEAP=1來禁止調(diào)試內(nèi)存模式。

全局調(diào)試堆內(nèi)存模式需要平均1.8秒，是最慢的。釋放對內(nèi)存模式50毫秒左右，稍快。基準測試的場景非常簡單，實際情況下，不同大小的內(nèi)存塊和隨機的申請、釋放可能產(chǎn)生不同的結(jié)果。然而，最簡單的也最能說明問題。內(nèi)存管理器比Allocator內(nèi)存分配器慢，并且很大程度上依賴于平臺的實現(xiàn)能力。

內(nèi)存分配器Allocator使用靜態(tài)內(nèi)存模式不依賴于堆內(nèi)存的分配。一旦“釋放列表”中含有內(nèi)存塊后，其執(zhí)行時間大約為7毫秒。***次耗時19毫秒用于將內(nèi)存池中的內(nèi)存防止到Allocator分配器中管理。

Aloocator使用堆內(nèi)存模式時，當“釋放列表”中有可重用的內(nèi)存后，其速度與靜態(tài)內(nèi)存模式一樣快。堆內(nèi)存模式依賴于全局堆來獲取內(nèi)存塊，但是循環(huán)利用“釋放列表”中的內(nèi)存。***次需要申請堆內(nèi)存，耗時30毫秒。由于重用“釋放列表”中的內(nèi)存，之后的申請僅需要7毫秒。

上面的基準測試結(jié)果表示，Allocator內(nèi)存分配器更加高效，擁有7倍于Windows全局發(fā)布堆內(nèi)存模式的速度。

對于嵌入式系統(tǒng)，我使用Keil在ARM STM32F4 CPU（168Hz）上運行相同測試。由于資源限制，我將***內(nèi)存塊數(shù)量降低到500，單個內(nèi)存塊大小降低到32和16字節(jié)。下面是結(jié)果：

基于ARM的基準測試顯示，使用Allocator分配器的類性能快15倍。這個結(jié)果會讓Keil堆內(nèi)存的表現(xiàn)相形見絀。基準測試分配500個16字節(jié)大小的內(nèi)存塊進行測試。每個16字節(jié)大小的內(nèi)存刪除后申請500個32字節(jié)大小的內(nèi)存塊。全局堆內(nèi)存耗時11.6毫秒，而且，在內(nèi)存碎片化后，內(nèi)存管理器可能會在沒有安全檢查的情況下耗時更大。

分配器決議

***個決定是你是否需要使用分配器。如果你的項目不關心執(zhí)行的速度和是否需要容錯，那么你可能不需要自定義的分配器，全局堆分配管理器足夠用了。

另一方面，如果你需要考慮執(zhí)行速度和容錯管理，分配器會起到作用。你需要根據(jù)項目的需要選擇分配器的模式。重要任務系統(tǒng)的設計可能強制要求使用全局堆內(nèi)存。而動態(tài)分配內(nèi)存可能更高效，設計更優(yōu)雅。這種情況下，你可以在調(diào)試開發(fā)時使用堆內(nèi)存模式獲取內(nèi)存使用參數(shù)，然后發(fā)布時切換到靜態(tài)內(nèi)存池模式避免內(nèi)存分配帶來的性能消耗。一些編譯時的宏可用于模式的切換。

另外，堆內(nèi)存模式可能對應用更適合。該模式利用堆來獲取新內(nèi)存，同時阻止了堆碎片錯誤。當“釋放列表”鏈接足夠的內(nèi)存塊后更能加快內(nèi)存的分配效率。

在源代碼中沒有實現(xiàn)的涉及多線程的問題不在本文的討論范圍內(nèi)。運行系統(tǒng)一會后，可以方便地使用GetlockCount函數(shù)和GetName函數(shù)獲取內(nèi)存塊數(shù)量和名稱。這些度量參數(shù)提供關于內(nèi)存分配的信息。盡量多申請點內(nèi)存，以便給分配盤一些彈性來避免內(nèi)存耗盡。

調(diào)試內(nèi)存泄漏

調(diào)試內(nèi)存泄漏非常困難，原因是堆內(nèi)存就像一個黑盒，對于分配對象的類型和大小是不可見的。使用Allocator，由于Allocator跟蹤記錄內(nèi)存塊的總數(shù)，內(nèi)存泄漏檢查變得簡單一點。對每個分配器實例重復輸出（例如輸出到終端）GetBlockCount和GetName并比對它們的不同能讓我們更好的了解分配器對內(nèi)存的分配。

錯誤處理

C++中使用new_handler函數(shù)處理內(nèi)存分配錯誤。如果內(nèi)存管理器在申請內(nèi)存時發(fā)生錯誤，用戶的錯誤處理函數(shù)就會被調(diào)用。通過將用戶的錯誤處理函數(shù)地址復制給new_handler，內(nèi)存管理器就能調(diào)用用戶自定義的錯誤處理程序。為了讓Allocator類的錯誤處理機制與內(nèi)存管理器保持一致，分配器也通過new_handler調(diào)用錯誤處理函數(shù)，集中處理所有的內(nèi)存分配錯誤。

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);
...

限制

分配器類不支持數(shù)組對象的內(nèi)存分配。為每一個對象創(chuàng)建分開的內(nèi)存是無法保證的，因為new的多次調(diào)用不保證內(nèi)存塊的連續(xù)，但這又是數(shù)組所需要的。因此Allocator只支持固定大小內(nèi)存塊的分配，對象數(shù)組不支持。

移植問題

Allocator在靜態(tài)內(nèi)存池耗盡時調(diào)用new_handle指向的函數(shù)，這對于某些系統(tǒng)不合適。假設new_handle函數(shù)沒返回，例如無盡的循環(huán)或者斷言，調(diào)用這個函數(shù)不起任何作用。使用固定內(nèi)存池時這無濟于事。

進一步閱讀

請閱讀相關文章：使用快速固定大小分配器替換malloc/free來查看如何使用Allocator更為快速的替換C++運行工具中的malloc和free函數(shù)。

下載源碼：Download Allocator.zip – 5.4 KB

譯文鏈接：http://www.codeceo.com/article/efficient-cpp-memory-allocator.html
英文原文：An Efficient C++ Fixed Block Memory Allocator