C++ 記憶體優化：二級間接索引記憶體池

設計目標

針對不確定總記憶體用量、頻繁分配/釋放、需隨機存取的場景，設計二級間接索引記憶體池：任意區塊僅需 3 次索引即可定位。所有參數（索引數、單元數、位元組大小）皆為 2 的冪次，利用位運算加速。

核心資料結構

class MemTable {
public:
    void CREATE(MemTableIn* in);
    void DEL();
    LPSTR NEW();                    // 分配 1 個 unit
    LPSTR NEW_CONTINUOUS(UINT n);   // 連續分配 n 個 unit
    UINT NEW(UINT n);               // 可碎片分配 n 個 unit，回傳起始索引
    LPSTR GET(UINT n);              // 取得第 n 個 unit 指標
    int get_total_unit_num();
    // ... 內部索引表、位圖、自由鏈表等
};

關鍵演算法

• ffs(x)：尋找最高位 1 的位置（等同 log2），用於計算各層級位移量。
• 二級索引表 pDouble_Indirect：LPSTR**，第一級索引指向第二級索引陣列，第二級指向實際資料區塊。
• 位圖 lpBitmap、自由指標 m_lpFirstFree 管理區塊內單元分配。
• 分配邏輯：優先使用當前區塊剩餘單元，耗盡則分配新二級索引與資料區塊。

程式碼片段（核心）

int ffs(int x) { // 尋找最高位 1
    int r = 1;
    if (!x) return 0;
    if (!(x & 0xffff)) { x >>= 16; r += 16; }
    if (!(x & 0xff))   { x >>= 8;  r += 8; }
    if (!(x & 0xf))    { x >>= 4;  r += 4; }
    if (!(x & 3))      { x >>= 2;  r += 2; }
    if (!(x & 1))      { x >>= 1;  r += 1; }
    return r;
}

LPSTR MemTable::NEW() {
    if (nFree[2] == 0) { // 當前區塊用完
        if (nFree[1] == 0) { // 二級索引用完
            if (nFree[0] == 0) return NULL; // 一級索引用完
            pIndirect = pDouble_Indirect[in.nIndexNum - nFree[0]] = new LPSTR[in.nIndexNum];
            memset(pIndirect, 0, in.nIndexNum * sizeof(LPSTR));
            nFree[1] = in.nIndexNum - 1;
            lpReturn = pIndirect[0] = new char[m_Vblkbytes];
            memset(lpReturn, 0, m_Vblkbytes);
            nFree[2] = in.nUnitPerIndex - 1;
            m_lpFirstFree = lpReturn + in.nUnitBytes;
            nFree[0]--;
        } else {
            lpReturn = pIndirect[in.nIndexNum - nFree[1]] = new char[m_Vblkbytes];
            memset(lpReturn, 0, m_Vblkbytes);
            nFree[1]--;
            nFree[2] = in.nUnitPerIndex - 1;
            m_lpFirstFree = lpReturn + in.nUnitBytes;
        }
    } else {
        lpReturn = m_lpFirstFree;
        nFree[2]--;
        m_lpFirstFree += in.nUnitBytes;
    }
    m_UnitTotalNum++;
    return lpReturn;
}

適用場景

• 高頻小物件分配（粒子系統、遊戲實體、網路封包）。
• 需 O(1) 隨機存取已分配物件（GET(index)）。
• 嵌入式/即時系統避免 heap 碎片與非確定性延遲。