引言

C/C++語言的內(nèi)存管理經(jīng)歷了幾次變革，但至今仍未能趨于成熟。這幾次變革主要包括：

1.         從malloc/free到new/delete。這場變革是OOP技術(shù)興起的產(chǎn)物。C++是強(qiáng)類型語言，new/delete的主要成果也就是加強(qiáng)了類型觀念，減少了強(qiáng)制類型轉(zhuǎn)換的需求。但是從內(nèi)存管理角度看，這個(gè)變革并沒有多少的突破性。

2.         從new/delete 到內(nèi)存配置器（allocator）。自從STL被納入C++標(biāo)準(zhǔn)庫后，C++世界產(chǎn)生了巨大的變化。而從內(nèi)存管理角度來看，allocator的引入也 是C++內(nèi)存管理一個(gè)突破。留意一下你就可以發(fā)現(xiàn)，整個(gè)STL所有組件的內(nèi)存均從allocator分配。也就是說，STL并不推薦使用 new/delete進(jìn)行內(nèi)存管理，而是推薦使用allocator。

然而，STL的allocator并沒有導(dǎo)致C++語言在內(nèi)存管理上發(fā)生巨大的變化。除了STL本身外，并沒有多少人使用allocator，甚至 是意識(shí)到allocator的重要性。所以C++程序員在使用STL的同時(shí)，依舊在使用new/delete進(jìn)行煩瑣的內(nèi)存分配/釋放過程。

究其原因，主要有二。一是allocator的引入，STL設(shè)計(jì)者主要可能還是出于將內(nèi)存管理從容器的實(shí)現(xiàn)獨(dú)立出來的設(shè)計(jì)理念作用，讓STL使用者 在內(nèi)存管理算法上有選擇的余地。設(shè)計(jì)者本身都可能也沒有意識(shí)到allocator的重要性。二是allocator本身也只是側(cè)重于關(guān)注效率上，而沒有側(cè) 重于C++語言使用者對(duì)內(nèi)存管理觀念的變革上。

總之，在我看來，STL的引入allocator，是一件了不起的事情。但是這場變革被忽視了，沒有得到貫徹。當(dāng)然，這也與STL的allocator本身的缺陷有關(guān)。

本文要討論的，正是如何貫徹STL的allocator思想，對(duì)其進(jìn)行適當(dāng)?shù)母倪M(jìn)，以期在C++內(nèi)存管理觀念上產(chǎn)生變革性的突破，徹底淘汰傳統(tǒng)的new/delete內(nèi)存管理方法[1]。

垃圾回收器

幾乎所有目前流行的垃圾回收器，均傾向于將使用者當(dāng)作一個(gè)傻瓜，期望能夠讓使用者在完全不理解內(nèi)存管理的情況下，可以很好的使用 它。應(yīng)該說這它們基本上都也做到了（雖然使用者有時(shí)也有這樣那樣的煩惱，但總體來說情況確實(shí)得到了很大程度的改善）。然而這一設(shè)計(jì)理念我并不十分認(rèn)同。

首先，可以在一個(gè)提供垃圾回收器的語言中自如的工作，沒有被垃圾回收器所困擾，本身已經(jīng)是很了不起的事情，他們絕對(duì)是非常聰明的 人，而不是傻瓜。他們理解垃圾回收器的工作原理，選擇它并且讓它為他們工作，只是因?yàn)檫€有更重要的事情等著他們?nèi)プ?。必要的時(shí)候，他們需要有辦法控制垃圾 回收器，使它按照他們的意愿工作。因此，垃圾回收器的設(shè)計(jì)要點(diǎn)在于把使用者從煩瑣的內(nèi)存管理中解脫出來，使得他們可以將全部精力投入到本身的業(yè)務(wù)邏輯上， 而不是讓垃圾回收器看起來更傻瓜式。

其次，使用一個(gè)全自動(dòng)的垃圾回收器，在內(nèi)存回收的時(shí)機(jī)不明確的情況下，垃圾回收器的工作過程有很大的不確定性，這給使用者帶來煩 惱。例如C#在調(diào)用非管制代碼（如調(diào)用Win32 api）時(shí)，這些問題變得突出。一個(gè)不小心，就有可能出現(xiàn)Win32 api還在使用一塊內(nèi)存，而垃圾回收器已經(jīng)把它回收了的情形。在小心翼翼的避開這些陷阱時(shí)，這種感覺其實(shí)與C/C++程序員遺憾語言沒有垃圾回收器的感覺 有點(diǎn)類似。

因此，最理想的情況，是內(nèi)存管理器提供垃圾回收的能力，但是它也只是提供這個(gè)能力而已，至于什么時(shí)候進(jìn)行垃圾回收，完全可以由用戶自己控制。另外，用戶也可以強(qiáng)制釋放一塊內(nèi)存，而不是完全被動(dòng)的等待垃圾回收過程決策何時(shí)回收該內(nèi)存。對(duì)于客戶來說，他有權(quán)掌控一切，只是如果萬一他確實(shí)疏忽了，垃圾回收器能夠?yàn)樗o(hù)航。

將垃圾回收器引入C++，有沒有這種可能呢？我認(rèn)為，如果我們試圖提供一個(gè)全自動(dòng)的垃圾回收器，這相當(dāng)困難。我們看到以Microsoft之能，仍然無法把這件事做好[2]?；蛟S，我們需要改變一下觀念：一個(gè)半自動(dòng)的垃圾回收器，也許就可能可以和C++融洽相處了呢？

初識(shí)allocator

allacator中文稱為“內(nèi)存配置器”，通常它是一個(gè)類，負(fù)責(zé)提供內(nèi)存管理（可能包含內(nèi)存分配、釋放、自動(dòng)回收等能力）相關(guān)的服務(wù)。例如，我們通過C提供的malloc/free即刻提供一個(gè)allocator實(shí)作出來：

class SimpleAlloc
{
public:
    //注意這里提供的參數(shù)fnDestroy，它是為那些具備垃圾回收能力的allocator需要提供。
void* Alloc(size_t cb, FnDestructor fnDestroy = NULL)
    {
        return malloc(cb);
    }
 
    //注意這里有看似多余的參數(shù)cb，這完全是為了和后續(xù)提供的allocator規(guī)格一致的需要。
    void Free(void* data, size_t cb)
    {
        free(data);
    }
};

有了allocator，我們可以申請(qǐng)內(nèi)存了，但是我們還不能用它創(chuàng)建一個(gè)C++對(duì)象。為了方便創(chuàng)建C++對(duì)象，我們提供了輔助的New操作，原型大體如下：

template <class Type, class AllocType>
Type* New(AllocType& alloc);                    // 類似于new Type
 
template <class Type, class ArgType1, class AllocType>
Type* New(ArgType1 arg1, AllocType& alloc); // 類似于new Type(arg1)
 
template <class Type, class AllocType>
Type* NewArray(size_t count, AllocType& alloc);// 類似于new Type[count]

有了這些輔助函數(shù)，我們就可以創(chuàng)建對(duì)象了。使用樣例：

SimpleAlloc alloc;
int* intArray = NewArray<int>(count, alloc);
MyClass* obj = New<MyClass>(alloc);
MyClass* objWithArg = New<MyClass>(arg1, alloc);
MyClass* objArray = NewArray<MyClass>(count, alloc);

這里我們雖然使用SimpleAlloc創(chuàng)建對(duì)象，但是需要提醒的是，這些New操作對(duì)所有的allocator有效。如果你關(guān)心New函數(shù)的代碼，先不急，下面我們馬上就可以看到了。但是首先我們要繼續(xù)討論一下allocator。

allocator引起的觀念變化

接觸allocator，你可以體會(huì)到了它與C++傳統(tǒng)的new/delete觀念的不同。這主要有以下幾點(diǎn)：

1.         每 個(gè)類（或者算法）本身，均有最合適它的內(nèi)存管理機(jī)制，并不是向C++傳統(tǒng)的做法那樣，使用一個(gè)全局的new/delete。也許你會(huì)說，C++不也允許一 個(gè)類定義自己的new和delete嗎？是的，C++的確支持類定義自己的new/delete，但注意，它的理念和allocator完全不同。我不認(rèn) 為它是C++的一個(gè)優(yōu)秀之作，相反，它起到了誤導(dǎo)作用。

因?yàn)椋瑳Q定一個(gè)類對(duì)象怎么去new出來，并不是取決于該類本身，而相反是取決于使用該類的人。一個(gè)類不需要關(guān)心自身被如何創(chuàng)造出來，更不能假定。它 需要關(guān)心的是它自己的類成員如何被創(chuàng)建出來，它的算法（你可以把類看做一個(gè)算法集合）涉及到的所有組件如何被創(chuàng)建出來。而這，才是allocator帶來 的觀念。

讓各種各樣的allocator創(chuàng)建同一個(gè)類的不同實(shí)例，這些實(shí)例甚至可能在一起工作，相互協(xié)作。從STL的角度講，這完全是最正常不過的事情了。

2.         重 要的是由allocator創(chuàng)建管理對(duì)象，避免在你的代碼中使用new/delete。如果可能，你可以如STL那樣，將allocator作為模板參 數(shù)，不綁定具體的某個(gè)內(nèi)存管理器。但是，如果你的算法依賴了某個(gè)allocator的實(shí)現(xiàn)特有的功能，這也并不要緊。你的目的不是要做到 allocator的可替換，不是嗎？重要的是使用了這個(gè)allocator了，它給你在內(nèi)存管理上帶來了益處。

但是，應(yīng)該看到，STL實(shí)作的各種allocator，目前來看除了最簡單使用malloc/free實(shí)現(xiàn)的外，主要就是基于 mempool技術(shù)。而該技術(shù)的目標(biāo)，不是讓內(nèi)存使用者更加方便有效地進(jìn)行內(nèi)存管理，而更多的是關(guān)注于內(nèi)存分配的時(shí)間性能。為了讓C++程序員從內(nèi)存管理 中解脫出來，我們需要實(shí)作新的alloctor，需要新的突破！

新視角：具垃圾回收能力的Allocator

對(duì)，我設(shè)想的一個(gè)做法是，貫徹STL的allocator觀念，并且提供具備特定的內(nèi)存管理能力（例如垃圾回收）的各種 allocator。讓C++社區(qū)廣泛接受allocator觀念，并且從中受益。C++程序員是時(shí)候拋棄傳統(tǒng)的new/delete，讓他們退出歷史舞 臺(tái)了。

我接下來會(huì)實(shí)作兩個(gè)具體的allocator（均屬原創(chuàng)）。相信它們會(huì)讓你耳目一新，讓你不禁想到：哦，原來在C++中，我還可以這樣進(jìn)行內(nèi)存管理。

當(dāng)然，我最大的希望就是，這兩個(gè)allocator能夠起到拋磚引玉的作用，讓大家也清楚地意識(shí)到allocator的重要性，可以出現(xiàn)更多的具備各種能力的allocator，解脫C++程序員一直以來的苦難（可能是最大苦難[3]）。

這兩個(gè)allocator均具備一定程度的垃圾回收能力。只是觀念上各有各的側(cè)重。我們接下來會(huì)分為兩個(gè)專題專門對(duì)它們進(jìn)行闡述。

輔助的New過程

我們終于可以開始討論前文提到的New函數(shù)的實(shí)現(xiàn)上了。以不帶參數(shù)的New為例，它的代碼如下，可能并沒有你想象的那么復(fù)雜：

#include <new>
 
template <class Type, class AllocType>
inline Type* New(AllocType& alloc)
{
    void* obj = alloc.Alloc(sizeof(Type), DestructorTraits<Type>::Destruct);
    return new(obj) Type;
}

其中DestructorTraits是一個(gè)根據(jù)類型Type萃取[4]析構(gòu)函數(shù)的萃取器。它看起來是這樣的：

template <class Type>
struct DestructorTraits
{
    static void Destruct(void* pThis)
    {
        ((Type*)pThis)->~Type();
    }
};

這樣，你就可以通過以下代碼new出對(duì)象了：

MyClassA* obj = New<MyClassA>(alloc);
MyClassB* obj = New<MyClassB>(alloc);

特別提醒：這里New函數(shù)在VC++ 6.0下編譯通過，但是產(chǎn)生的執(zhí)行代碼存在嚴(yán)重bug。如果你只New一類對(duì)象，沒有問題，但在New了多種對(duì)象后，似乎VC++對(duì)MyClassA、 MyClassB 兩者混淆起來了。為了支持VC++ 6.0，你需要對(duì)這里的New做出調(diào)整（關(guān)于這一點(diǎn)，詳細(xì)請(qǐng)參考：VC++ 6.0小技巧）。

COM技術(shù)[5]與內(nèi)存管理

已經(jīng)準(zhǔn)備結(jié)束這篇短文的時(shí)候，忽然想到了長久以來使用COM技術(shù)形成的一些感想，這些想法恰恰與內(nèi)存管理緊密相關(guān)。故此想就這個(gè)問題陳述一下。

從COM的IUnknown接口看，它主要關(guān)注兩個(gè)問題：一個(gè)是QueryInterface，一個(gè)是引用計(jì)數(shù) （AddRef/Release）。COM組件很講究信息的屏蔽，使用者對(duì)組件的認(rèn)識(shí)有限，這就給組件升級(jí)、擴(kuò)充功能提供了可能。 QueryInterface是一個(gè)很好的概念，需要發(fā)揚(yáng)光大。

COM的引用計(jì)數(shù)則關(guān)注的是組件的生命期維護(hù)問題。換句話說，就是組件如何銷毀的問題。誠然，組件對(duì)象的銷毀問題，是內(nèi)存管理的 關(guān)鍵。無論是COM的引用計(jì)數(shù)，還是垃圾回收技術(shù)，均是要解決對(duì)象的銷毀問題。只是兩者的側(cè)重點(diǎn)不太一樣，COM引用計(jì)數(shù)更關(guān)注“確保組件不會(huì)被提前銷毀 了，確保組件訪問的安全性”，而垃圾回收器則關(guān)注“不管怎樣確保組件最終被銷毀，沒有內(nèi)存泄漏”。

在COM中，確保組件訪問的安全性（避免非法訪問），這個(gè)觀點(diǎn)太重要了，以至于它甚至不惜加重程序員的內(nèi)存管理負(fù)擔(dān)。所以，在 COM程序中，出現(xiàn)內(nèi)存泄漏太正常了，而且一旦泄漏通常就是大片大片內(nèi)存的漏。更加要命的是，你甚至不能有一個(gè)很簡單有效的方法確認(rèn)這個(gè)泄漏是由于哪段代 碼引起。因?yàn)榻M件所有的客戶都是平等的，任何一個(gè)客戶代碼存在問題均將導(dǎo)致內(nèi)存的泄漏。

剛開始接觸COM技術(shù)的時(shí)候，我對(duì)引用計(jì)數(shù)持的是比較正面的態(tài)度。但是隨著部門逐步加大COM技術(shù)的使用力度后，四五年下來，我漸漸開始迷惑起來。一切并不如想象的那樣。這個(gè)引用計(jì)數(shù)的背后，需要我們付出多少額外的代價(jià)！

而這個(gè)迷惑、思索，可能就是本文以及后續(xù)相關(guān)內(nèi)容的成因吧。

C++內(nèi)存管理變革(2)：最袖珍的垃圾回收器

· 版權(quán)聲明 ·

概述

C/C++最被人詬病的，可能是沒有一個(gè)內(nèi)存垃圾回收器（確切是說沒有一個(gè)標(biāo)準(zhǔn)的垃圾回收器）。本文討論的內(nèi)容要點(diǎn)是，在C/C++中實(shí)現(xiàn)一個(gè)最袖珍的、功能受限的垃圾回收器。這個(gè)垃圾回收器區(qū)別于其他垃圾回收器的主要特征是：

1.         袖珍但具實(shí)用性。整個(gè)垃圾回收器代碼行數(shù)100行左右（不含空白行），相當(dāng)小巧。相對(duì)而言，它的功能也受到一定的限制。但是它在很多關(guān)鍵的場合恰恰非常有用。該垃圾回收器以實(shí)用作為首要目標(biāo)，已經(jīng)成為我和身邊一些同事編程的重要工具?！?/p>

2.         高性能。區(qū)別于其他垃圾回收器的是這個(gè)袖珍的垃圾回收器非但不會(huì)導(dǎo)致性能的下降，反而提高了程序的時(shí)間性能（分配的速度加快）和空間性能（所占內(nèi)存空間比正常的malloc/new少）。而這也是實(shí)用的重要指標(biāo)。

本文算法并不復(fù)雜。技術(shù)上的東西，很多點(diǎn)明了就沒有什么了，也許重要的意義是在于其首創(chuàng)性。其實(shí)，boost[1]提供的pool組件也在試圖提供類似功能的自動(dòng)內(nèi)存回收能力。但是實(shí)現(xiàn)相對(duì)復(fù)雜且低效（基于經(jīng)典的mempool技術(shù)[2]）。

現(xiàn)在，你也許急著想看看，這個(gè)垃圾回收器長什么樣了。閑話少敘，那就讓我們就開始一步步把謎底揭開吧。

思路

理解該垃圾回收器的關(guān)鍵點(diǎn)在于，是在于理解它的目標(biāo)：為一個(gè)復(fù)雜的局部過程（算法）提供自動(dòng)內(nèi)存回收的能力?！?/p>

所謂局部過程（算法），是指那些算法復(fù)雜性較高，但在程序運(yùn)行期所占的時(shí)間又比較短暫的過程[3]。 例如：搜索引擎的搜索過程、讀盤/存盤過程、顯示（繪制）過程等等。通常這些過程可能需要申請(qǐng)很多內(nèi)存，而且內(nèi)存分配操作的入口點(diǎn)很多（就是調(diào)用new的 地方很多），如果每調(diào)用一次new就要考慮應(yīng)該在什么地方delete就徒然浪費(fèi)我們寶貴的腦力，使得我們無法把全力精力集中在算法本身的設(shè)計(jì)上。也許就 是在這種情形下，C/C++程序員特別羨慕那些具備垃圾回收器的語言。相對(duì)而言，如果算法復(fù)雜性不高的話，我們的程序員完全有能力控制好 new/delete的匹配關(guān)系。并且，這種“一切皆在我掌控之中”的感覺給了我們安全感[4]和滿足感?！?/p>

因此，這個(gè)垃圾回收器的重心并不是要提供一個(gè)理論上功能完備的內(nèi)存自動(dòng)回收機(jī)制。它只是針對(duì)復(fù)雜性較高的局部過程（算法），為他 們提供最實(shí)效的內(nèi)存管理手段。從局部過程的一開始，你就只管去申請(qǐng)、使用內(nèi)存，等到整個(gè)算法完成之后，這個(gè)過程申請(qǐng)的大部分內(nèi)存（需要作為算法結(jié)果保留的 例外），無論它是在算法的那個(gè)步驟申請(qǐng)的，均在這個(gè)結(jié)束點(diǎn)上由垃圾回收器自動(dòng)銷毀。我們畫個(gè)示意圖：

圖 1

規(guī)格

我們將該垃圾回收器命名為AutoFreeAlloc。它的接口很簡單，僅涉及兩個(gè)概念：Alloc、Clear。

typedef void (*FnDestructor)(void* pThis);
 
class AutoFreeAlloc
{
public:
    ~AutoFreeAlloc();                           // 析構(gòu)函數(shù)。自動(dòng)調(diào)用Clear釋放內(nèi)存
    void* Alloc(size_t cb);                     // 類似于malloc(cb)
    void* Alloc(size_t cb, FnDestructor fn);    // 申請(qǐng)內(nèi)存并指定析構(gòu)函數(shù)
    void Clear();                               // 析構(gòu)并釋放所有分配的對(duì)象
};

為了方便，提供輔助的New操作（上一篇中已經(jīng)簡單介紹實(shí)現(xiàn)了），大體如下：

template <class Type, class AllocType>
Type* New(AllocType& alloc);                    // 類似于new Type
 
template <class Type, class ArgType1, class AllocType>
Type* New(ArgType1 arg1, AllocType& alloc); // 類似于new Type(arg1)
 
template <class Type, class AllocType>
Type* NewArray(size_t count, AllocType& alloc);// 類似于new Type[count]

使用樣例：

AutoFreeAlloc alloc;
 
int* intArray = (int*)alloc.Alloc(sizeof(int)*count);
int* intArray2 = NewArray<int>(count, alloc);
 
MyClass* obj = New<MyClass>(alloc);
MyClass* objWithArg = New<MyClass>(arg1, alloc);
MyClass* objArray = NewArray<MyClass>(count, alloc);
 
alloc.Clear();
 
// …
// 現(xiàn)在，不能再訪問intArray, obj, objWithArg, objArray等數(shù)據(jù)了。

內(nèi)存管理機(jī)制

class AutoFreeAlloc
{
public:
    enum { BlockSize = 2048 };
private:
    struct _MemBlock
    {
        _MemBlock* pPrev;
        char buffer[BlockSize];
    };
    enum { HeaderSize = sizeof(_MemBlock) - BlockSize };
    
    char* m_begin;
    char* m_end;
};

AutoFreeAlloc類與內(nèi)存管理相關(guān)的變量只有兩個(gè)：m_begin、m_end。單從變量定義來看，基本上很難看明白。但是有了下面這張示意圖就容易理解多了：

圖 2

整個(gè)AutoFreeAlloc申請(qǐng)的內(nèi)存，通過_MemBlock構(gòu)成鏈表。只要獲得了鏈表的頭，就可以遍歷整個(gè)內(nèi)存鏈，釋放所有申請(qǐng)的內(nèi)存了。而鏈表的頭(圖中標(biāo)為_ChainHeader)，可以通過m_begin計(jì)算得到：

_MemBlock* AutoFreeAlloc::_ChainHeader() const
{
    return (_MemBlock*)(m_begin - HeaderSize);
}

為了使得_ChainHeader初始值為null，構(gòu)造函數(shù)我們這樣寫：

AutoFreeAlloc::AutoFreeAlloc()
{
    m_begin = m_end = (char*)HeaderSize;
}

★         下面我們考慮內(nèi)存分配過程。Alloc過程主要會(huì)有三種情況，具體代碼為：

void* AutoFreeAlloc::Alloc(size_t cb)
{
    if (m_end – m_begin < cb)
    {
        if (cb >= BlockSize)
        {
                _MemBlock* pHeader = _ChainHeader();
                _MemBlock* pNew = (_MemBlock*)m_alloc.allocate(HeaderSize + cb);
                if (pHeader)
                {
                 pNew->pPrev = pHeader->pPrev;
    　             pHeader->pPrev = pNew;
                }
                else
                {
        　         m_end = m_begin = pNew->buffer;
            　     pNew->pPrev = NULL;
                }
                return pNew->buffer;        }
        else
        {
            _MemBlock* pNew = (_MemBlock*)malloc(sizeof(_MemBlock));
            pNew->pPrev = _ChainHeader();
            m_begin = pNew->buffer;
            m_end = m_begin + BlockSize;
        }
    }
    return m_end -= cb;
}

1.         最簡單的情況，是當(dāng)前_MemBlock還有足夠的自由內(nèi)存(free memory)，即：
    m_end – m_begin >= cb
此時(shí)，只需要將m_end前移cb字節(jié)就可以了。我們畫個(gè)示意圖如下：

圖 3　

2.         在當(dāng)前的_MemBlock的自由內(nèi)存（free memory）不足的情況下，我們就需要申請(qǐng)一個(gè)新的_MemBlock以供使用[5]。申請(qǐng)新的_MemBlock，我們又會(huì)遇到兩種情況：

a)         申請(qǐng)的字節(jié)數(shù)（即cb）小于一個(gè)_MemBlock所能夠提供的內(nèi)存（即BlockSize）。
這種情況下，我們只需要將該_MemBlock作為新的當(dāng)前_MemBlock掛到鏈表中，剩下的工作就和情形1完全類似。示意圖如下：

圖 4

b)        而在內(nèi)存申請(qǐng)的字節(jié)數(shù)（即cb）大于或等于一個(gè)Block的字節(jié)數(shù)時(shí)，我們需要申請(qǐng)可使用內(nèi)存超過正常長度（BlockSize）的_MemBlock。這個(gè)新生成的_MemBlock全部內(nèi)存被用戶申請(qǐng)。故此，我們只需要修改_ChainHeader的pPrev指針，改為指向這一塊新申請(qǐng)的_MemBlock即可。m_begin、m_end保持不變（當(dāng)前的_MemBlock還是當(dāng)前的_MemBlock）。如圖：

圖 5

★         下面我們考慮內(nèi)存釋放（Clear）過程。這個(gè)過程就是遍歷_MemBlock釋放所有的_MemBlock的過程，非常簡單。代碼如下：

void AutoFreeAlloc::Clear()
{
    _MemBlock* pHeader = _ChainHeader();
    while (pHeader)
    {
        _MemBlock* pTemp = pHeader->pPrev;
        free(pHeader);
        pHeader = pTemp;
    }
    m_begin = m_end = (char*)HeaderSize;
}

自動(dòng)析構(gòu)過程

我們知道，C++以及其他面向?qū)ο笳Z言為對(duì)象引入了構(gòu)造、析構(gòu)過程。這是一個(gè)了不起的發(fā)明。因?yàn)橹挥羞@樣，才能夠保證對(duì)象從一開始產(chǎn)生以來（剛new出來），到對(duì)象銷毀這整個(gè)過程，它的數(shù)據(jù)都處于完備狀態(tài)，是自洽的。

我們知道，C++以及其他面向?qū)ο笳Z言為對(duì)象引入了構(gòu)造、析構(gòu)過程。這是一個(gè)了不起的發(fā)明。因?yàn)橹挥羞@樣，才能夠保證對(duì)象從一開始產(chǎn)生以來（剛new出來），到對(duì)象銷毀這整個(gè)過程，它的數(shù)據(jù)都處于完備狀態(tài)，是自洽的。

由于垃圾回收器負(fù)責(zé)對(duì)象的回收，它自然不止需要關(guān)注對(duì)象申請(qǐng)的內(nèi)存的釋放，同時(shí)也需要保證，在對(duì)象銷毀之前它的析構(gòu)過程被調(diào)用。上文我們?yōu)榱岁P(guān)注內(nèi)存管理過程，把自動(dòng)析構(gòu)過程需要的代碼均去除了。為了支持自動(dòng)析構(gòu)，AutoFreeAlloc類增加了以下成員：

class AutoFreeAlloc
{
    struct _DestroyNode
{
        _DestroyNode* pPrev;
        FnDestructor fnDestroy;
    };
    _DestroyNode* m_destroyChain;
};

如果一個(gè)類存在析構(gòu)，則它需要在Alloc內(nèi)存的同時(shí)指定析構(gòu)函數(shù)。代碼如下：

void* AutoFreeAlloc::Alloc(size_t cb, FnDestructor fn)
{
    _DestroyNode* pNode = (_DestroyNode*)Alloc(sizeof(_DestroyNode) + cb);
    pNode->fnDestroy = fn;
    pNode->pPrev = m_destroyChain;
    m_destroyChain = pNode;
    return pNode + 1;
}

只要通過該Alloc函數(shù)申請(qǐng)的內(nèi)存，我們在Clear中就可以調(diào)用相應(yīng)的析構(gòu)。當(dāng)然，Clear函數(shù)需要補(bǔ)充自動(dòng)析構(gòu)相關(guān)的代碼：

void AutoFreeAlloc::Clear()
{
    while (m_destroyChain)
    {
        m_destroyChain->fnDestroy(m_destroyChain + 1);
        m_destroyChain = m_destroyChain->pPrev;
    }
    // 以下是原先正常的內(nèi)存釋放過程…
}

時(shí)間性能分析

void* AutoFreeAlloc::Alloc(size_t cb);

OOP技術(shù)帶來一個(gè)內(nèi)存上的問題是，對(duì)象粒度越來越細(xì)了，對(duì)象基本上都是小對(duì)象。這就對(duì)內(nèi)存管理的性能提出了很高的要求?！?/p>

如果我們以對(duì)象大小平均為32字節(jié)計(jì)算的話，每2048/32 = 64操作中，只有一次操作滿足m_end – m_begin < cb的條件。也就是說，在通常情況（63/64 = 98.4%的概率）下，Alloc操作只需要一個(gè)減法操作就完成內(nèi)存分配。

我說這是世界上最快速的內(nèi)存分配算法，也許你對(duì)此仍然抱有懷疑態(tài)度。但是可以肯定的一點(diǎn)是，要突破它的性能極限我覺得已經(jīng)很難很難了?！?/p>

void AutoFreeAlloc::Clear();

一般內(nèi)存管理器通常一次內(nèi)存分配操作就需調(diào)用相應(yīng)的一次Free操作。但是AutoFreeAlloc不針對(duì)每一個(gè)Alloc進(jìn)行釋放，而是針對(duì)每一個(gè)_MemBlock。仍假設(shè)對(duì)象平均大小為32字節(jié)的話，也就是相當(dāng)于把64次Alloc操作合并，為其提供一次相應(yīng)的Free過程。

★         結(jié)論：AutoFreeAlloc在時(shí)間上的性能，大約比普通的malloc/free的快64倍。

空間性能分析

我們知道，一般內(nèi)存管理器為了將用戶申請(qǐng)的內(nèi)存塊管理起來，除了用戶需要的cb字節(jié)內(nèi)存外，通常額外還提供一個(gè)內(nèi)存塊的頭結(jié)構(gòu)，通過這個(gè)頭結(jié)構(gòu)將內(nèi)存串連成為一個(gè)鏈表。一般來講，這個(gè)頭結(jié)構(gòu)至少有兩項(xiàng)（可能還不止），示意如下：

struct MemHeader
{
    MemHeader* pPrev;
    size_t cb;
};

仍然假設(shè)平均Alloc一次的內(nèi)存為32字節(jié)。則一次malloc分配過程，就會(huì)浪費(fèi)8/32 = 25%的內(nèi)存。并且由于大量的小對(duì)象存在，整個(gè)內(nèi)存中的碎片（指那些自由但無法被使用的內(nèi)存）將特別嚴(yán)重。

而AutoFreeAlloc的Alloc沒有如何額外開銷。整個(gè)AutoFreeAlloc，只有在將_MemBlock串為鏈表的有一個(gè)額外的 pPrev指針，加上_MemBlock是malloc出來的，有額外的8字節(jié)開銷?？傆?jì)浪費(fèi)(4+8)/2048 = 0.6%的內(nèi)存，幾乎可以忽略不計(jì)?！?/p>

后記

AutoFreeAlloc于2004-5-21開發(fā)，只有100行的代碼量。但是，這個(gè)組件獲得了空前的成功，它的應(yīng)用范圍逐步擴(kuò)大，超過了我最初實(shí)現(xiàn)這個(gè)組件時(shí)的預(yù)計(jì)。

我漸漸冷靜下來，考慮這其中蘊(yùn)涵的道理。我逐步領(lǐng)會(huì)到了，它的成功之處，不是它在時(shí)間、空間性能的高效，而是在于它幫助C++程序員解決了最大的難題——內(nèi)存管理。雖然，這個(gè)解決方案并不是完整的。

AutoFreeAlloc是一個(gè)切入點(diǎn)，從它身上，讓我明白了C++的new/delete的不合理；STL引入的allocator是一個(gè)切入點(diǎn)，從它身上，讓我明白了內(nèi)存管理有很強(qiáng)的區(qū)域性，在不同的區(qū)域（局部過程）中對(duì)allocator的需求卻又不盡相同。

我們前文也提到了一個(gè)例子：一個(gè)文檔打開，編輯，直到文檔被最終關(guān)閉，這個(gè)完成算不算局部過程呢？在AutoFreeAlloc解決的問題域來看，顯然我們無法認(rèn)為它是一個(gè)局部過程。但是，從其他allocator角度來講，是否就有可能把它作為一個(gè)局部過程了呢？

正是考慮到AutoFreeAlloc的缺陷，我們需要一個(gè)功能更強(qiáng)的垃圾回收器。這就是我們下一次需要討論的組件了。

最后，仍然需要明確的一點(diǎn)時(shí)。我們很難也不需要實(shí)現(xiàn)一個(gè)象Java、C#那樣的垃圾回收器。提供一個(gè)具備特定的內(nèi)存管理能力的allocator才是正道。

[1] 請(qǐng)參考boost官方網(wǎng)站http://www./。

[2] mempool技術(shù)是一個(gè)很成熟的內(nèi)存管理技術(shù)，被sgi-stl、boost等C++庫實(shí)現(xiàn)者采用。

[3] 真正是否要把一個(gè)過程定義為局部過程，完全取決于設(shè)計(jì)者本身。例如，一個(gè)文檔打開，編輯，直到文檔被最終關(guān)閉，這個(gè)完成算不算局部過程呢？在大部分情況下我們認(rèn)為它不是一個(gè)局部過程，但是下回我們將專門討論是否有可能，以及應(yīng)該如何將它作為一個(gè)局部過程。

[4] 那些提供了垃圾回收器的語言的使用者，顯然也有應(yīng)用了垃圾回收器的煩惱。例如C#在調(diào)用非管制代碼（如調(diào)用Win32 api）時(shí)，這些問題變得突出，一個(gè)疏忽就留下潛在隱患。這與C/C++程序員遺憾語言沒有垃圾回收器的感覺類似。

[5] 當(dāng)前的_MemBlock的自由內(nèi)存很可能還是有的，但是不足cb字節(jié)。此時(shí)我們說這里有內(nèi)存碎片（memory piece）：這些碎片盡管沒有人使用，但是我們把它棄而不用。

附加說明：

本文所描述的AutoFreeAlloc組件，完整代碼可在WINX庫中找到。你也可以通過以下鏈接在線瀏覽：

AutoFreeAlloc完整源代碼

另外， 這篇文章寫的時(shí)間較早，其規(guī)格雖然與現(xiàn)在的AutoFreeAlloc一樣，但成員函數(shù)名改了：

    Alloc -> allocate
    Clear -> clear

之所以這樣，是因?yàn)锳utoFreeAlloc被納入stdext庫（這個(gè)庫可獨(dú)立于winx界面庫，是winx界面庫的基礎(chǔ)）。stdext庫的命名風(fēng)格盡量與STL的命名習(xí)慣一致。

相關(guān)文章：《C++內(nèi)存管理變革》

C++內(nèi)存管理變革(3)：另類內(nèi)存管理

· 版權(quán)聲明 ·

最簡單的C++/Java程序

最簡單的Java程序:

class Program
{
   public static void main()
   {
       new int;
   }
}

對(duì)應(yīng)的C++程序:

void main()
{
   new int;
}

我想沒有一個(gè)Java程序員會(huì)認(rèn)為上面的Java代碼存在問題。但是所有嚴(yán)謹(jǐn)?shù)腃++程序員則馬上指出：上面這個(gè)C++程序有問題，它存在內(nèi)存泄漏。但是我今天想和大家交流的一個(gè)觀念是：這個(gè)C++程序沒有什么問題。

DocX程序的內(nèi)存管理

DocX是我開發(fā)的一個(gè)文檔撰寫工具。這里有關(guān)于它的一些介紹。在這一小節(jié)里，我要談?wù)勎以贒ocX中嘗試的另類內(nèi)存管理方法。 

DocX的總體流程是：

1. 讀入一個(gè)C++源代碼（或頭）文件（.h/.c/.hpp/.cpp等），分析其中的注釋，提取并生成xml文檔。
2. 通過xslt變換，將xml文檔轉(zhuǎn)換為htm。
3. 分析源代碼中的所有include指令，取得相應(yīng)的頭文件路徑，如果某個(gè)頭文件沒有分析過，跳到1反復(fù)這些步驟。
4. 最后所有生成的htm打包生成chm文件。

一開始，我象Java/C#程序員做的那樣，我的代碼中所有的new均不考慮delete。當(dāng)然，它一直運(yùn)作得很好，直到有一天我的文檔累計(jì)到了一定程度后。正如我們預(yù)見的那樣，DocX程序運(yùn)行崩潰了。

那么，怎么辦呢？找到所有需要delete的地方，補(bǔ)上delete？

這其實(shí)并不需要。在前面，我給大家介紹了AutoFreeAlloc（參見《C++內(nèi)存管理變革(2)：最袖珍的垃圾回收器》），也許有人在嘀咕，這樣一個(gè)內(nèi)存分配器到底有何作用?！?wbr>—那么，現(xiàn)在你馬上可以看到它的典型用法之一了：

對(duì)于我們的DocX崩潰后，我只是做了以下改動(dòng)：

1. 加一個(gè)全局變量：std::AutoFreeAlloc alloc;
2. 所有的new Type(arg1, arg2, …, argn)，改為STD_NEW(alloc, Type)(arg1, arg2, …, argn);
3. 所有的new Type[n]，改為STD_NEW_ARRAY(alloc, Type, n);
4. 每處理完一個(gè)源代碼文件時(shí)，調(diào)用一次alloc.clear();

搞定，自此之后，DocX再也沒有內(nèi)存泄漏，也不再有遇到內(nèi)存不足而崩潰的情形。

只讀DOM模型（或允許少量修改）的建立

在《文本分析的三種典型設(shè)計(jì)模式》一文中我推薦大家使用DOM模型去進(jìn)行文件操作。并且通常情況下，這個(gè)DOM模型是只讀DOM模型（或允許少量修改）。 

對(duì)于只讀DOM模型，使用AutoFreeAlloc是極其方便的。整個(gè)DOM樹涉及的內(nèi)存統(tǒng)一由同一個(gè)AutoFreeAlloc實(shí)例進(jìn)行分配。大體如下：

class Document;
class ObjectA
{
private:
    Document* m_doc;
    SubObject* m_c;
 
public:
    ObjectA(Document* doc) : m_doc(doc) {
        m_c = STD_NEW(doc->alloc, SubObject);
    }
 
    SubObject* getC() {
        return m_c;
    }
};
 
class Document
{
public:
    AutoFreeAlloc alloc;
 
private:
    ObjectA* m_a;
    ObjectB* m_b;
 
public:
    ObjectA* getA() {
        if (m_a == NULL)
            m_a = STD_NEW(alloc, ObjectA)(this);
        return m_a;
    }
};

通過這種方式創(chuàng)建的DOM模型，只要你刪除了Document對(duì)象，整個(gè)DOM樹自然就被刪除了。你根本不需要擔(dān)心其中有任何內(nèi)存泄漏的可能。

另類內(nèi)存管理的觀念

通過以上內(nèi)容，我試圖向大家闡述的一個(gè)觀點(diǎn)是：

• 有了AutoFreeAlloc后，C++程序員也可以象GC語言的程序員一樣大膽new而不需要顧忌什么時(shí)候delete。

展開來講，可以有以下結(jié)論：

• 如果你程序的空間復(fù)雜度為O(1)，那么只new不delete是沒有問題的。
• 如果你程序的空間復(fù)雜度為O(n)，并且是簡單的n*O(1)，那么可以用AutoFreeAlloc簡化內(nèi)存管理。
• 如果你程序的空間復(fù)雜度為O(t)，其中t是程序運(yùn)行時(shí)間，并且你不能確定程序執(zhí)行的總時(shí)間，那么AutoFreeAlloc并不直接適合你。比較典型的例子是Word、Excel等文檔編輯類的程序。

用AutoFreeAlloc實(shí)現(xiàn)通用型的GC

AutoFreeAlloc對(duì)內(nèi)存管理的環(huán)境進(jìn)行了簡化，這種簡化環(huán)境是常見的。在此環(huán)境下，C++程序員獲得了無可比擬的性能優(yōu)勢。當(dāng)然，在一般情形下，AutoFreeAlloc并不適用。

那么，一個(gè)通用的半自動(dòng)GC環(huán)境在C++是否可能？《C++內(nèi)存管理變革》系列的核心就是要告訴你：當(dāng)然可以。并且，我們推薦C++程序員使用半自動(dòng)的GC，而不是Java/C# 中的那種GC。

通用的半自動(dòng)GC環(huán)境可以有很多種建立方式。這里我們簡單聊一下如何使用AutoFreeAlloc去建立。

我們知道，使用AutoFreeAlloc，將導(dǎo)致程序隨著時(shí)間推移，逐步地吃掉可用的內(nèi)存。假設(shè)現(xiàn)在已經(jīng)到達(dá)我們設(shè)置的臨界點(diǎn)，我們需要開始 gc。整個(gè)過程和Java等語言的gc其實(shí)完全類似：通過一個(gè)根對(duì)象（Object* root），獲得所有活動(dòng)著的對(duì)象（Active Objects），將它們復(fù)制到一個(gè)新的AutoFreeAlloc中：

Object* gc(AutoFreeAlloc& oldAlloc, Object* root, AutoFreeAlloc& newAlloc)
{
    Object* root2 = root->clone(newAlloc);
    oldAlloc.clear();
    return root2;
}

如果C++象Java/C#那樣有足夠豐富的元信息，那么Object::clone過程就可以象Java/C# 等語言那樣自動(dòng)完成。這些元信息對(duì)于GC過程的用處無非在于，我們可以遍歷整個(gè)活動(dòng)對(duì)象的集合，然后把這些活動(dòng)對(duì)象復(fù)制一份。沒有復(fù)制過來的對(duì)象自然而然 就被丟棄了。

GC的原理就是這么簡單。沒有元信息也沒關(guān)系，只要我們要求每個(gè)由GC托管的對(duì)象支持clone函數(shù)，一切就ok了。對(duì)于一個(gè)復(fù)雜程序，要求每個(gè)對(duì) 象提供clone函數(shù)不見得是什么過分的要求，clone函數(shù)也不只有g(shù)c過程才需要，很多對(duì)象在設(shè)計(jì)上天然就需要clone。

補(bǔ)充說明

關(guān)于全局AutoFreeAlloc變量

我個(gè)人非常不推薦使用全局變量（除非是常量：不一定用const修飾，指的是經(jīng)過一定初始化步驟后就不在修改的變量）。上面只是對(duì)于小型的單線程程序偷懶才這樣做。

關(guān)于用AutoFreeAlloc實(shí)現(xiàn)通用型的GC

請(qǐng)注意我沒有討論過于細(xì)節(jié)的東西。如果你決定選擇這種做法，請(qǐng)仔細(xì)推敲細(xì)節(jié)?？梢灶A(yù)見的一些細(xì)節(jié)有：

• AutoFreeAlloc與線程模型（ThreadModel）。AutoFreeAlloc關(guān)注點(diǎn)在于快，它通常不涉及跨線程問題。但是如果要作為通用型的GC，這一點(diǎn)不能不考慮。為了性能，推薦每個(gè)線程獨(dú)立管理內(nèi)存，而不要使用互斥體。
• 性能優(yōu)化?？梢钥紤]象Java的GC那樣，使用兩個(gè)AutoFreeAlloc，把對(duì)象劃分為年輕代和年老代。

C++內(nèi)存管理變革(4): boost::object_pool

許式偉 (版權(quán)聲明)
2007-4-21

這篇文章拖的有點(diǎn)久了。NeutralEvil 在3個(gè)月之前就在催促我繼續(xù)寫了。只是出于WinxGui完整性的考慮，我一直在刻意優(yōu)先去補(bǔ)充其它方面的文章，而不是讓人去誤會(huì)WinxGui是一個(gè)內(nèi)存管理庫了。:)

言歸正傳。我們在內(nèi)存池(MemPool)技術(shù)詳解已經(jīng)介紹了boost::pool組件。從內(nèi)存管理觀念的變革來看，這是是一個(gè)傳統(tǒng)的MemPool組件，盡管也有一定的改進(jìn)（但只是性能上的改進(jìn)）。但boost::object_pool不同，它與我在C++內(nèi)存管理變革強(qiáng)調(diào)的觀念非常吻合。可以認(rèn)為，boost::object_pool是一種不通用的gc allocator組件。

我已經(jīng)多次提出gc allocator的概念。這里仍然需要強(qiáng)調(diào)一下，所謂gc allocator，是指具垃圾回收能力的allocator。C++內(nèi)存管理變革(1) 中我們引入了這個(gè)概念，但是沒有明確gc allocator一詞。

boost::object_pool內(nèi)存管理觀念

boost::object_pool的了不起之處在于，這是C++從庫的層次上頭一次承認(rèn)，程序員在內(nèi)存管理上是會(huì)犯錯(cuò)誤的，由程序員來確保內(nèi)存不泄漏是困難的。boost::object_pool允許你忘記釋放內(nèi)存。我們來看一個(gè)例子：

如果boost::object_pool只是一個(gè)普通的allocator，那么這段代碼顯然存在問題，因?yàn)閛bj1的析構(gòu)函數(shù)沒有執(zhí)行，申請(qǐng)的內(nèi)存也沒有釋放。

但是這段代碼是完全正常的。是的，obj1的析構(gòu)確實(shí)執(zhí)行了，所申請(qǐng)內(nèi)存也被釋放了。這就是說，boost::object_pool既支持你手工釋放內(nèi)存（通過主動(dòng)調(diào)用object_pool::destroy），也支持內(nèi)存的自動(dòng)回收（通過object_pool::~object_pool析構(gòu)的執(zhí)行）。這正符合gc allocator的規(guī)格。

注：內(nèi)存管理更好的說法是對(duì)象管理。內(nèi)存的申請(qǐng)和釋放更確切的說是對(duì)象的創(chuàng)建和銷毀。但是這里我們不刻意區(qū)分這兩者的差異。

boost::object_pool與AutoFreeAlloc

我們知道，AutoFreeAlloc不支持手工釋放，而只能等到AutoFreeAlloc對(duì)象析構(gòu)的時(shí)候一次性全部釋放內(nèi)存。那么，是否可以認(rèn)為boost::object_pool是否比AutoFreeAlloc更加完備呢？

其實(shí)不然。boost::object_pool與AutoFreeAlloc都不是完整意義上的gc allocator。AutoFreeAlloc因?yàn)樗荒芤淮涡葬尫?，故此僅僅適用特定的用況。然而盡管AutoFreeAlloc不是普適的，但它是通用型的gc allocator。而boost::object_pool只能管理一種對(duì)象，并不是通用型的allocator，局限性其實(shí)更強(qiáng)。

boost::object_pool的實(shí)現(xiàn)細(xì)節(jié)

大家對(duì)boost::object_pool應(yīng)該已經(jīng)有了一個(gè)總體的把握。現(xiàn)在，讓我們深入到object_pool的實(shí)現(xiàn)細(xì)節(jié)中去。

在內(nèi)存池(MemPool)技術(shù)詳解中，我們介紹boost::pool組件時(shí)，特意提醒大家留意pool::ordered_malloc/ordered_free函數(shù)。事實(shí)上，boost::object_pool的malloc/construct, free/destroy函數(shù)調(diào)用了pool::ordered_malloc, ordered_free函數(shù)，而不是pool::malloc, free函數(shù)。

讓我們解釋下為什么。

其實(shí)這其中的關(guān)鍵，在于object_pool要支持手工釋放內(nèi)存和自動(dòng)回收內(nèi)存（并自動(dòng)執(zhí)行析構(gòu)函數(shù)）兩種模式。如果沒有自動(dòng)析構(gòu)，那么普通的MemPool就足夠了，也就不需要ordered_free。既然有自動(dòng)回收，同時(shí)又存在手工釋放，那么就需要區(qū)分內(nèi)存塊（MemBlock）中哪些結(jié)點(diǎn)（Node）是自由內(nèi)存結(jié)點(diǎn)（FreeNode），哪些結(jié)點(diǎn)是已經(jīng)使用的。對(duì)于哪些已經(jīng)是自由內(nèi)存的結(jié)點(diǎn)，顯然不能再調(diào)用對(duì)象的析構(gòu)函數(shù)。

我們來看看object_pool::~object_pool函數(shù)的實(shí)現(xiàn)：

這段代碼不難理解，object_pool遍歷所有申請(qǐng)的內(nèi)存塊（MemBlock），并遍歷其中所有結(jié)點(diǎn)（Node），如果該結(jié)點(diǎn)不出現(xiàn)在自由內(nèi)存結(jié)點(diǎn)（FreeNode）的列表（FreeNodeList）中，那么，它就是用戶未主動(dòng)釋放的結(jié)點(diǎn)，需要進(jìn)行相應(yīng)的析構(gòu)操作。

現(xiàn)在你明白了，ordered_malloc是為了讓MemBlockList中的MemBlock有序，ordered_free是 為了讓FreeNodeList中的所有FreeNode有序。而MemBlockList, FreeNodeList有序，是為了更快地檢測Node是自由的還是被使用的（這實(shí)際上是一個(gè)集合求交的流程，建議你看看std:: set_intersection，它定義在STL的<algorithm>中）。

C++內(nèi)存管理變革-系列文章 

• C++內(nèi)存管理變革
• C++內(nèi)存管理變革(2)：最袖珍的垃圾回收器
• C++內(nèi)存管理變革(3)：另類內(nèi)存管理
• 再論C++之垃圾回收（GC）

點(diǎn)擊這里查看更多內(nèi)存管理相關(guān)文章。