位圖固定大小記憶體分配器設計：極致節省小物件開銷的實現詳解

動機：通用分配器對小物件的開銷

new/malloc 每次分配需存儲塊大小、狀態等元數據（通常 8-16 字節），並對齊到 8/16 字節。對 12 字節雙向鏈表節點，實際佔用 24 字節，**開銷 100%**。嵌入式/高併發場景不可接受。

設計目標

• 專用於固定大小小物件（如鏈表節點、樹節點）。
• 元數據開銷極小：每塊 1 字節索引 + 每 Chunk 8 字節位圖。
• 線程安全（互斥鎖保護）。
• 符合 STL Allocator 概念（single_object_allocator 封裝）。

核心資料結構

// Chunk: 64 塊 + 1 個位圖 (uint64_t)
struct Chunk {
    uint64_t map;          // 位圖：1=空閒, 0=已用
    Object objects[64];    // 緊湊排布
};
// Object: 1 字節索引 + 用戶數據
union Object { uint8_t idx; char pad[1]; };

Chunk 總大小：8 + 64 * (BlockSize + 1) 字節。僅保留一個部分使用的 Chunk 快取，其余滿/空 Chunk 即時歸還 OS。

關鍵演算法

分配

1. 若有快取 Chunk 且位圖非 0：find_fbit(map) 找首個 1 位 → mark_bit(map, idx) 置 0 → 返回物件指標。
2. 否則 chunk_alloc() 向 OS 申請新 Chunk，初始化位圖全 1，遞歸分配。

釋放

1. 由物件指標倒推：Object* obj = ptr - 1; idx = obj->idx; 2. Chunk* chk = (Chunk*)((char*)obj - idx * blk_sz) - 1; 3. clear_bit(chk->map, idx) 置 1。 4. 若 chk->map == FULL (all 1) 且非快取 Chunk → free(chk) 歸還 OS。

位圖操作：尋找首個 1 (LSB)

• x86 GCC：內聯彙編 bsf (Bit Scan Forward) 指令，極快。
• 通用：De Bruijn 序列乘法查表法（lsb_64_table），O(1) 無分支。

完整實現節選

class bitmap_fixed_size_allocator : public default_mutex {
    using size_type = uint64_t;
    using index_type = uint8_t;
    static Chunk* cached_chunk; // 單快取 Chunk
    size_type blk_sz; // 含索引的塊大小
    size_type sz_lmt; // 閾值：超過此大小直接 malloc

    void* allocate() {
        if (blk_sz > sz_lmt) return malloc(blk_sz - sizeof(Object));
        Chunk* c = cached_chunk;
        if (!c || c->map == 0) return chunk_alloc(); // 滿或無快取
        return get_free_block(c);
    }
    void deallocate(void* p) { /* 反向計算 chunk/idx, 置位, 檢查全空歸還 */ }
    // ... 位圖操作、chunk_alloc、find_fbit 等 ...
};

STL Allocator 封裝

template<typename T>
class single_object_allocator {
    static bitmap_fixed_size_allocator bm;
public:
    using value_type = T;
    T* allocate(size_t n) { 
        if (n != 1) throw; // 僅支援單個物件
        return static_cast<T*>(bm.allocate()); 
    }
    void deallocate(T* p, size_t n) { 
        if (n != 1) { bm.clear(); throw; } 
        bm.deallocate(p); 
    }
    // construct/destroy/max_size/rebind 等標準介面...
};

效能與記憶體對比

局限與適用場景

• 僅支援等大物件，不可用於 std::list 等標準容器（需修改 allocate 接受 size_t）。
• 非 NUMA 感知，多核爭用鎖可能成為瓶頸（可改 Thread-Local Cache）。
• 適用於：高頻小物件池（網路封包、遊戲實體、編譯器 AST 節點、嵌入式記憶體池）。

總結

位圖固定大小分配器以 **1 字節/塊** 的極致元數據開銷，配合 **64 塊/Chunk** 的緊湊佈局與 **LSB 位掃描**，實現了接近理論下限的小物件記憶體管理。理解其設計權衡（開銷 vs 通用性、快取策略 vs 碎片），可指導自定義記憶體池開發。