C++ 內存管理變革（二）：打造最袖珍的垃圾回收器

前言

C/C++ 最常被詬病的缺點，莫過於缺乏標準的內存垃圾回收機制。本文將探討如何在 C/C++ 中實現一個極其精簡、功能受限但極具實用價值的垃圾回收器 —— AutoFreeAlloc。它的核心特點在於：

• 袖珍且實用： 核心代碼僅約 100 行（不含空行），極其輕量。雖然功能有所限制，但在許多關鍵場景下卻異常好用，已成為筆者及同事日常開發的得力工具。
• 高性能： 不同於傳統垃圾回收器帶來的性能損耗，AutoFreeAlloc 不僅不拖慢程序，反而顯著提升了時間性能（分配速度更快）和空間性能（內存佔用比 malloc/new 更少）。

演算法本身並不複雜，技術關鍵一經點破便豁然開朗，其價值或許在於首創性。Boost 庫中的 pool 組件雖也嘗試提供類似的自動內存回收能力，但實現相對複雜且效率較低（基於經典的 mempool 技術）。

核心思路：針對「局部過程」的自動內存管理

理解 AutoFreeAlloc 的關鍵在於明確其目標：為複雜的局部過程（演算法）提供自動內存回收能力。

所謂「局部過程」，指那些演算法複雜度高、但運行時間較短暫的過程，例如：搜尋引擎的查詢過程、讀寫盤過程、繪圖渲染過程等。這類過程通常需要大量申請內存，且分配入口分散（到處調用 new），若逐一考慮 delete 位置，極大消耗腦力，分散了對核心演算法設計的精力。這正是 C/C++ 程式設計師最羨慕擁有 GC 語言的時刻。反之，若演算法不複雜，程式設計師完全能駕馭 new/delete 的配對，且「一切盡在掌握」能帶來安全感與成就感。

因此，AutoFreeAlloc 並不追求理論上功能完備的通用 GC，而是專注於高複雜度的局部過程，提供最務實的內存管理手段：從過程開始，只管申請、使用內存；待演算法結束，該過程申請的絕大多數內存（保留作為結果的例外），無論在哪個步驟申請，均在結束點由垃圾回收器自動銷毀。示意圖如下：

圖 1：局部過程內存自動回收示意

接口規格：極簡的 Alloc 與 Clear

AutoFreeAlloc 僅暴露兩個核心概念：Alloc（分配）與 Clear（清理）。

typedef void (*FnDestructor)(void* pThis);

class AutoFreeAlloc {
public:
    ~AutoFreeAlloc();           // 析構函數，自動調用 Clear 釋放內存
    void* Alloc(size_t cb);     // 類似 malloc(cb)
    void* Alloc(size_t cb, FnDestructor fn); // 申請內存並指定析構函數
    void Clear();               // 析構並釋放所有分配的對象
};

為便於使用，另提供輔助的 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]

使用範例：

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

// ... 演算法邏輯 ...

// 此處無需手動 delete，alloc 析構或 Clear 會自動回收所有內存
// 現在，不能再訪問 intArray, obj, objWithArg, objArray 等數據了。

內存管理機制：基於記憶體塊鏈表

AutoFreeAlloc 的內存管理變量只有兩個：m_begin、m_end。單看變量定義難以理解，結合示意圖即清晰：

圖 2：_MemBlock 鏈表結構

所有申請的內存通過 _MemBlock 串成鏈表。鏈表頭（_ChainHeader）可由 m_begin 計算得出：

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

為使鏈表頭初始為 null，構造函數寫法如下：

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

分配過程三種情況

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. 當前塊剩餘空間足夠（最常見，約 98.4%）： 僅需將 m_end 前移 cb 位元組。
   
   圖 3：當前塊足夠時的分配
2. 當前塊不足，且申請大小 < BlockSize： 申請新 _MemBlock 掛入鏈表，作為新的當前塊，後續同情況 1。
   
   圖 4：申請新塊並切換當前塊
3. 申請大小 >= BlockSize： 申請超大 _MemBlock，直接掛入鏈表頭，m_begin/m_end 不變（當前塊不變）。
   
   圖 5：大塊直接掛入鏈表頭

釋放過程：遍歷鏈表釋放

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

自動析構支持

C++ 的構造/析構機制保證了對象生命週期內數據的自洽性。垃圾回收器除釋放內存外，必須確保對象銷毀前調用析構函數。為此增加成員：

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

需析構的對象在分配時指定析構函數：

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; // 返回用戶數據區指針
}

Clear 中補充析構調用：

void AutoFreeAlloc::Clear() {
    while (m_destroyChain) {
        m_destroyChain->fnDestroy(m_destroyChain + 1);
        m_destroyChain = m_destroyChain->pPrev;
    }
    // 接著釋放內存塊鏈表...
}

性能分析：時間與空間的雙重優勢

時間性能：快約 64 倍

假設對象平均 32 位元組，每 2048/32 = 64 次分配中，僅 1 次需申請新塊（滿足 m_end - m_begin < cb）。因此 98.4% 的情況下，Alloc 僅需一次減法運算。Clear 則按塊釋放，相當於將 64 次 Alloc 合併為 1 次 Free。綜合來看，AutoFreeAlloc 時間性能約為普通 malloc/free 的 64 倍。

空間性能：浪費僅 0.6%

傳統分配器為管理每個塊需額外頭部結構（如指針+大小），假設平均 32 位元組，額外開銷 8 位元組，浪費 25%，且產生大量碎片。AutoFreeAlloc 僅在鏈表節點有一個 pPrev 指針，加上 malloc 自身 8 位元組開銷，總浪費 (4+8)/2048 = 0.6%，幾乎可忽略。

後記與反思

AutoFreeAlloc 於 2004 年開發，僅 100 行代碼，卻獲得空前成功，應用範圍遠超預期。其成功不在於極致性能，而在於解決了 C++ 程式設計師最大的痛點 —— 內存管理，雖方案不完整。

它啟示了 C++ new/delete 的不合理；STL allocator 則揭示了內存管理的強區域性 —— 不同局部過程對分配器需求不同。例如文檔編輯過程在 AutoFreeAlloc 視角非局部過程，但換個 allocator 角度或可視為局部過程？

正是針對 AutoFreeAlloc 的缺陷，我們需要更強大的垃圾回收器，那將是下一篇討論的主題。最終結論：我們無需也難以實現如 Java/C# 的通用 GC，提供具備特定內存管理能力的 allocator 才是正道。

完整源碼可見 WINX 庫：https://sourceforge.net/projects/winx。註：後來納入 stdext 庫，函數名改為 allocate/clear 以符合 STL 風格。