簡介

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

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

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

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

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

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

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

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

回收內(nèi)存存儲(chǔ)

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

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

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

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

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

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

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

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

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

類設(shè)計(jì)

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

類的構(gòu)造函數(shù)中的參數(shù)用于決定內(nèi)存塊分配的位置。size參數(shù)控制固定內(nèi)存塊的大小。objects參數(shù)設(shè)置申請(qǐng)內(nèi)存塊的個(gè)數(shù)，其值為0表示從堆內(nèi)存中申請(qǐng)新內(nèi)存塊，非0表示使用內(nèi)存池方式（堆內(nèi)存池或者靜態(tài)內(nèi)存池）分配對(duì)象實(shí)例空間。memory參數(shù)是指向靜態(tài)內(nèi)存的指針。如果memory等于0并且objects非零，Allocator將從堆內(nèi)存中創(chuàng)建一個(gè)內(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<>模板類。模板的***個(gè)參數(shù)設(shè)置申請(qǐng)內(nèi)存對(duì)象類型，第二個(gè)參數(shù)設(shè)置申請(qǐng)對(duì)象的數(shù)量。

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

Deallocate()將內(nèi)存地址放入“棧”中。這個(gè)“棧”的實(shí)現(xiàn)方式類似于單項(xiàng)鏈表（“釋放列表”），但是只能添加、移除頭部的對(duì)象，其行為類似棧的特性。使用“棧”使得分配、釋放操作更為快速，因?yàn)椴恍枰湵肀闅v而只需要壓入和彈出操作。

void* memory1 = allocatorHeapBlocks.Allocate(100);

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

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

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

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

代碼的使用

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

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

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

操作符new函數(shù)調(diào)用Allocator創(chuàng)建類實(shí)例所需要的內(nèi)存空間。內(nèi)存分配后，根據(jù)定義，操作符new調(diào)用該類的構(gòu)造函數(shù)。重寫的new只修改了內(nèi)存的分配任務(wù)。構(gòu)造函數(shù)的調(diào)用由語言保證。刪除對(duì)象時(shí)，系統(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。這樣看上去通過基類的指針刪除對(duì)象不能達(dá)到刪除真實(shí)對(duì)象的目的。畢竟，調(diào)用基類指針的靜態(tài)函數(shù)只會(huì)調(diào)用基類的成員函數(shù)，而不是其真實(shí)類型的成員函數(shù)。然而，我們知道，調(diào)用操作符delete時(shí)首先調(diào)用析構(gòu)函數(shù)。修飾為virtual的析構(gòu)函數(shù)會(huì)實(shí)際調(diào)用子類的析構(gòu)函數(shù)。類的析構(gòu)函數(shù)執(zhí)行完后，子類的操作符delete函數(shù)被調(diào)用。因此實(shí)際上，由于虛析構(gòu)函數(shù)的調(diào)用，重寫的操作符delete會(huì)在子類中調(diào)用。所以，使用基類指針刪除對(duì)象時(shí)，基類對(duì)象的析構(gòu)函數(shù)必須聲明為virtual。否則，將會(huì)不能正確調(diào)用析構(gòu)函數(shù)和操作符delete。

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

IMPLEMENT_ALLOCATOR(MyClass, 0, 0)

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

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

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

Base* base = new Derived;
delete base;

運(yùn)行時(shí)

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

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

基準(zhǔn)測(cè)試

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

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

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

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

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

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

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

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

分配器決議

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

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

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

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

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

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

錯(cuò)誤處理

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

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

限制

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

移植問題

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

進(jìn)一步閱讀

請(qǐng)閱讀相關(guān)文章：使用快速固定大小分配器替換malloc/free來查看如何使用Allocator更為快速的替換C++運(yùn)行工具中的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
翻譯作者：碼農(nóng)網(wǎng) – 蘇文鵬