C++ 記憶體優化實戰：二級間接索引模式記憶體池實現

在不確定總記憶體佔用、頻繁 new 分配並以鏈表索引的場景下，隨機定位極難。本文介紹一種二級間接索引記憶體池：以兩層索引表對記憶體進行大塊劃分，任意塊僅需 3 次索引即可定位。設計要求：索引數量、每索引塊分配單元數、單元位元組長度均為 2 的整數次冪（為位運算效率）。

核心資料結構（節選）

class MemTable {
public:
    MemTable(void);
    ~MemTable(void);
    void CREATE(MemTableIn *in_m);
    void DEL();
    LPSTR NEW();                          // 分配一個 unit
    LPSTR NEW_CONTINUEOUS(UINT n);        // 連續分配 n 個 unit
    UINT NEW(UINT n);                     // 可碎片方式分配 n 個 unit
    LPSTR GET(UINT n);                    // 獲取第 n 個分配的指標
    int get_totle_unitnum();

public:
    MemTableIn in;
    LPSTR **pDouble_Indirect;   // 二級索引表
    LPSTR lpBitmap;             // 位圖
    LPSTR *pIndirect;           // 一級索引表
    LPSTR m_lpFirstFree;        // 首個空閒單元指標
    int nFree[3];               // [0]二級索引空閒 [1]一級索引空閒 [2]塊空閒索引號
    INT32 m_EndBlkUseredUnits;
    int m_Vblkbytes;            // 每塊位元組數
    UINT m_UnitTotalNum;        // 已分配總單元數
    // 位運算優化用的 log2 預計算欄位...
    UINT m_index2ID, m_index1ID, m_UnitID;
};

關鍵演算法解析

1. 位掃描函數 ffs：快速計算 log2

int ffs(int x) { // 找最高位 1，返回 2 的冪次
    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;
}

用於初始化時將「單元數、索引數、單元大小」轉為位移量，避免運行時除法/取模。

2. 初始化 CREATE：建立二級索引骨架

void MemTable::CREATE(MemTableIn *in_m) {
    memset(&in, 0, sizeof(in));
    in = *in_m;
    m_UnitTotalNum = 0;
    nFree[0] = nFree[1] = nFree[2] = 0;

    m_Vblkbytes = in.nUnitBytes * in.nUnitPerIndex;
    m_log2Runits   = ffs(in.nUnitPerIndex) - 1;
    m_log2Rindexs  = ffs(in.nIndexNum) - 1;
    m_log2UnitBytes = ffs(in.nUnitBytes) - 1;

    m_log2Lindexs = sizeof(UINT)*8 - m_log2Rindexs;
    m_log2Lunits  = sizeof(UINT)*8 - m_log2Runits;

    // 分配二級索引表指標陣列
    pDouble_Indirect = new LPSTR*[in.nIndexNum];
    memset(pDouble_Indirect, 0, in.nIndexNum * sizeof(LPSTR));
    nFree[0] = in.nIndexNum;
}

3. 分配邏輯 NEW()：三級遞補策略

• Level 0：二級索引表項耗盡 → 返回 NULL（達上限）。
• Level 1：一級索引表項耗盡 → 分配新一級索引表（new LPSTR[in.nIndexNum]），掛載到二級索引下。
• Level 2：當前塊單元耗盡 → 分配新塊（new char[m_Vblkbytes]），掛載到一級索引下，重置塊內空閒計數。
• 快速路徑：塊內仍有空閒 → 直接從 m_lpFirstFree 取單元，指標後移 in.nUnitBytes。

全程僅涉及指標運算與位移，極高效。

4. 連續分配 NEW_CONTINUEOUS 與 碎片分配 NEW(n)

• NEW_CONTINUEOUS：若當前塊剩餘 ≥ n，直接切分；否則保留剩餘、另起新塊滿足需求。
• NEW(n)：循環呼叫 NEW() n 次，返回首單元索引號。

5. O(1) 隨機存取 GET(n)：純位運算定址

LPSTR MemTable::GET(UINT n) {
    if (n >= m_UnitTotalNum) return NULL;
    m_UnitID   = (n << m_log2Lunits) >> m_log2Lunits;          // 塊內偏移
    m_index1ID = n >> m_log2Runits;                            // 一級索引
    m_index2ID = m_index1ID >> m_log2Rindexs;                  // 二級索引
    m_index1ID = (m_index1ID << m_log2Lindexs) >> m_log2Lindexs; // 一級索引在二級內偏移
    return pDouble_Indirect[m_index2ID][m_index1ID] + (m_UnitID << m_log2UnitBytes);
}

三次解引用（二級→一級→塊基址）+ 位移，無循環、無分支，真正 O(1)。

6. 釋放 ~MemTable：遞歸釋放所有塊與索引表

雙重循環遍歷二級、一級索引，逐個 delete[] 塊記憶體與一級索引表，最後釋放二級索引表指標陣列。

適用場景與優缺點

本文出自「張宇(數據恢復)」部落格，轉載請保留出處：原文連結