动态

详情 返回 返回

unordered_map性能被吊打！我用基數樹讓內存池性能暴漲幾十倍的秘密 - 动态 详情

哈嘍，大家好，我是小康！

今天要和大家聊一個特別有意思的話題——基數樹。

説實話，我第一次聽到這個名詞的時候，內心是懵逼的。基數？樹？這玩意兒到底是啥？

直到有一天，我在研究TCMalloc內存池源碼的時候，發現了一個神奇的現象：為什麼Google的工程師不用std::unordered_map來做頁號映射，而要自己實現一個看起來很複雜的數據結構？

帶着這個疑問，我深入研究了一下，結果發現了一個寶藏——基數樹！

一個讓我震驚的性能對比

先來看個數據，直接震撼你的小心臟：

測試場景：100萬次查找操作
std::unordered_map：    40878微秒
基數樹：               714微秒
性能提升：             57.2521倍！

這還只是中等規模的測試，在大規模場景下，差距會更加誇張。

基數樹到底是個啥玩意兒？

好，現在我用最通俗的話給大家解釋一下基數樹。

簡單粗暴地説，基數樹就是一個超級大數組！

沒錯，就這麼簡單。

比如你要存儲鍵值對，傳統的做法是：

  • std::map：用紅黑樹，需要比較、旋轉，O(log n)時間
  • std::unordered_map：用哈希表，需要計算哈希、處理衝突，平均O(1)但有常數開銷

而基數樹呢？直接把鍵當作數組的下標！

// 傳統方式
unordered_map[123] = ptr;  // 需要計算hash(123)，可能還要處理衝突

// 基數樹方式
array[123] = ptr;          // 直接訪問！O(1)且常數極小

是不是超級簡單？

動手實現一個基數樹（一級）

talk is cheap，show me the code！

const uint32_t MAX_KEY = (1 << 20) - 1;

// ============ 基數樹實現 ============
template<int BITS = 20>  // 20位，支持100萬條目 800 0000
class SimpleRadixTree {
private:
    static const size_t SIZE = 1 << BITS;
    void** array_;
    
public:
    SimpleRadixTree() {
        array_ = new void*[SIZE];
        memset(array_, 0, SIZE * sizeof(void*));
        
        cout << "創建了支持 " << SIZE << " 條目的基數樹" << endl;
        cout << "理論內存: " << (SIZE * 8) / (1024) << " KB" << endl;
    }
    
    ~SimpleRadixTree() {
        delete[] array_;
    }
    
    // 設置鍵值對 - O(1)時間！
    void set(uint32_t key, void* value) {
        if (key >= SIZE) {
            cerr << "錯誤: 鍵 " << key << " 超出範圍 [0, " << (SIZE-1) << "]" << endl;
            return;
        }
        array_[key] = value;
    }
    
    // 獲取值 - O(1)時間！
    void* get(uint32_t key) {
        if (key >= SIZE) return nullptr;
        return array_[key];
    }
    
    // 刪除鍵
    void remove(uint32_t key) {
        if (key < SIZE) {
            array_[key] = nullptr;
        }
    }
    
    // 統計已使用的條目數
    size_t count_used() const {
        size_t count = 0;
        for (size_t i = 0; i < SIZE; ++i) {
            if (array_[i] != nullptr) {
                count++;
            }
        }
        return count;
    }
    
    // 獲取支持的最大鍵值
    uint32_t max_key() const {
        return SIZE - 1;
    }
};

就這麼幾行代碼，我們就實現了一個高性能的一級基數樹！

基數樹的核心：用空間換時間。

性能大PK：基數樹 VS unordered_map

我專門寫了個測試程序，在我的Ubuntu機器上跑了一下：

void performance_battle() {
    cout << "\n========== 性能大PK開始 ==========" << endl;
    
    const int TEST_COUNT = 1000000;
    
    // 準備測試數據
    vector<uint32_t> keys;
    cout << "準備 " << TEST_COUNT << " 個測試鍵..." << endl;
    for(int i = 0; i < TEST_COUNT; i++) {
        //keys.push_back(i * 7);  // 一些分散的鍵，避免連續訪問的緩存優勢
        keys.push_back(i);  
    }
    
    cout << "數據準備完成，開始測試..." << endl;
    
    // ========== 測試 unordered_map ==========
    cout << "\n測試 unordered_map..." << endl;
    unordered_map<uint32_t, void*> hashmap;
    auto start = chrono::high_resolution_clock::now();
    
    // 插入測試
    for(int i = 0; i < TEST_COUNT; i++) {
        hashmap[keys[i]] = reinterpret_cast<void*>(i + 1);
    }
    
    // 查找測試
    for(int i = 0; i < TEST_COUNT; i++) {
        volatile void* result = hashmap[keys[i]];
        (void)result; // 防止編譯器優化掉
    }
    
    auto end = chrono::high_resolution_clock::now();
    auto hashmap_time = chrono::duration_cast<chrono::microseconds>(end - start);
    
    // ========== 測試基數樹 ==========
    cout << "測試基數樹..." << endl;
    SimpleRadixTree<20> radix_tree;
    start = chrono::high_resolution_clock::now();
    
    // 插入測試
    for(int i = 0; i < TEST_COUNT; i++) {
        radix_tree.set(keys[i], reinterpret_cast<void*>(i + 1));
    }
    
    // 查找測試
    for(int i = 0; i < TEST_COUNT; i++) {
        volatile void* result = radix_tree.get(keys[i]);
        (void)result; // 防止編譯器優化掉
    }
    
    end = chrono::high_resolution_clock::now();
    auto radix_time = chrono::duration_cast<chrono::microseconds>(end - start);
    
    // ========== 輸出結果 ==========
    cout << "\n=== 性能大PK結果 ===" << endl;
    cout << "測試規模:       " << TEST_COUNT << " 次操作" << endl;
    cout << "unordered_map:  " << hashmap_time.count() << " 微秒" << endl;
    cout << "基數樹:         " << radix_time.count() << " 微秒" << endl;
    
    if (radix_time.count() > 0) {
        double speedup = (double)hashmap_time.count() / radix_time.count();
        cout << "性能提升:       " << speedup << " 倍" << endl;
        
        if (speedup > 5) {
            cout << "基數樹性能碾壓！" << endl;
        } else if (speedup > 2) {
            cout << " 基數樹明顯更快！" << endl;
        } else {
            cout << "性能相當" << endl;
        }
    }
    
    // 驗證結果正確性
    cout << "\n驗證結果正確性..." << endl;
    bool correct = true;
    for(int i = 0; i < 1000; i++) {  // 驗證前1000個結果
        void* hash_result = hashmap[keys[i]];
        void* radix_result = radix_tree.get(keys[i]);
        if (hash_result != radix_result) {
            cout << "結果不一致！鍵: " << keys[i] << endl;
            correct = false;
            break;
        }
    }
    
    if (correct) {
        cout << "結果驗證通過，兩種方法結果一致！" << endl;
    }
}

在我的機器上跑出來的結果：

=== 性能大PK結果 ===
測試規模:       1000000 次操作
unordered_map:  40878 微秒
基數樹:         714 微秒
性能提升:       57.2521 倍

50+倍的性能提升！ 這還只是中等規模的測試。

為什麼會有這麼大的差距？

  1. 基數樹：直接數組訪問，沒有任何額外計算
  2. unordered_map：需要計算哈希值、處理衝突、內存分散訪問

基數樹在內存池中的神奇應用

現在來看看基數樹的實際應用場景——內存池！

在內存池系統中，我們需要根據內存地址快速找到對應的內存塊信息（Span）。

傳統方式可能是這樣：

// 傳統內存池的頁號映射
unordered_map<PageID, Span*> page_to_span;

// 哈希查找，較慢
Span* find_span(void* ptr) {
    PageID page_id = (uintptr_t)ptr >> 12;  // 假設4KB頁面
    std::lock_guard<std::mutex> lock(map_mutex_);// 還要加鎖
    auto it = page_to_span.find(id);
    return (it != page_to_span.end()) ? it->second : nullptr;   
}

用基數樹優化後：

// 基數樹版本的頁號映射
SimpleRadixTree<28> page_map;  // 支持1TB地址空間

// 不需要加鎖
Span* find_span(void* ptr) {
    PageID page_id = (uintptr_t)ptr >> 12;
    return (Span*)page_map.get(page_id);    // 直接數組訪問，超快！
}

這就是為什麼TCMalloc、jemalloc這些高性能內存池都在用基數樹的原因！

一個完整的內存池應用示例

// ============ 內存池應用演示 ============
struct Span {
    uint32_t page_id;
    uint32_t num_pages;
    bool in_use;
    void* free_list;
    
    Span(uint32_t pid, uint32_t pages, bool used = true) 
        : page_id(pid), num_pages(pages), in_use(used), free_list(nullptr) {}
};

class MemoryPool {
private:
    SimpleRadixTree<24> page_map_;  // 24位，支持16M頁，相當於64GB地址空間
    vector<Span*> spans_;  // 保存所有Span，用於清理
    
public:
    ~MemoryPool() {
        for(auto* span : spans_) {
            delete span;
        }
    }
    
    // 註冊內存塊
    void register_span(Span* span) {
        spans_.push_back(span);
        
        // 為這個Span的每一頁都建立映射
        for(uint32_t i = 0; i < span->num_pages; i++) {
            uint32_t page_id = span->page_id + i;
            page_map_.set(page_id, span);
        }
        
        cout << "註冊Span: 起始頁號=" << span->page_id 
             << ", 頁數=" << span->num_pages << endl;
    }
    
    // 根據地址快速找到所屬的內存塊
    Span* addr_to_span(void* ptr) {
        // 假設頁面大小為4KB，即PAGE_SHIFT=12
        uint32_t page_id = (reinterpret_cast<uintptr_t>(ptr) >> 12) & 0xFFFFFF;  // 取低24位
        return reinterpret_cast<Span*>(page_map_.get(page_id));
    }
    
    // 根據頁號查找Span
    Span* page_to_span(uint32_t page_id) {
        return reinterpret_cast<Span*>(page_map_.get(page_id));
    }
    
    // 釋放內存時，快速定位到對應的Span
    bool free_memory(void* ptr) {
        Span* span = addr_to_span(ptr);  // O(1)時間找到Span！
        if(span && span->in_use) {
            cout << "找到地址 " << ptr << " 對應的Span: 頁號" << span->page_id << endl;
            return true;
        }
        return false;
    }

};

看到沒？有了基數樹，內存池的地址查找變成了O(1)操作，這對高併發場景下的內存分配性能提升是巨大的！

當然，這裏只是簡單展示一下基數樹的應用思路。實際的內存池項目要複雜得多，想學習完整實現的同學不妨看看： 三週肝出4000行代碼，我的內存池竟然讓malloc"破防"了！性能暴漲7.37倍背後的技術真相

什麼時候該用基數樹？

基數樹雖然牛逼，但也不是萬能的。什麼時候用呢？

適合用基數樹的場景：

  • 鍵的範圍相對固定且已知
  • 鍵分佈比較密集
  • 對查找性能要求極高
  • 內存充足的環境

不適合用基數樹的場景：

  • 鍵的範圍非常大且分佈稀疏
  • 內存嚴重受限的環境
  • 鍵是字符串等複雜類型

進階：多層基數樹

當鍵的範圍太大時（比如64位地址空間），1層基數樹就不夠用了。這時候我們可以用多層基數樹。

簡單來説，就是把一個超級大數組拆分成多個小數組的組合：

// 2層基數樹示意
template<int BITS = 36>  // 支持Linux 64位地址空間  
class PageMap2 {
private:
    // 位數分配：儘量均勻分配
    static const int LEAF_BITS = BITS / 2;        // 18位
    static const int ROOT_BITS = BITS - LEAF_BITS; // 18位
    static const size_t ROOT_SIZE = 1ULL << ROOT_BITS; 
    static const size_t LEAF_SIZE = 1ULL << LEAF_BITS;
    
    struct Leaf {
        void* values[LEAF_SIZE];
        
        Leaf() {
            memset(values, 0, sizeof(values));
        }
    };
    
    Leaf* root_[ROOT_SIZE];
    
public:
    PageMap2() {
        memset(root_, 0, sizeof(root_));
        cout << "二級基數樹初始化完成！" << endl;
        cout << "支持地址空間: " << (1ULL << BITS) << " 頁 ("
             << ((1ULL << BITS) * 4096) / (1024ULL*1024*1024*1024) << " TB)" << endl;
        cout << "固定內存開銷: " << sizeof(root_) / (1024*1024) << " MB" << endl;
    }
    
    ~PageMap2() {
        // 清理所有分配的葉子節點
        for(size_t i = 0; i < ROOT_SIZE; i++) {
            delete root_[i];
        }
    }
    
    // 獲取值 - 兩次數組訪問，仍然是O(1)！
    void* get(uint64_t key) {
        if(key >= (1ULL << BITS)) return nullptr;
        
        uint64_t i1 = key >> LEAF_BITS;      // 高位作為一級索引
        uint64_t i2 = key & (LEAF_SIZE - 1); // 低位作為二級索引
        
        if(root_[i1] == nullptr) return nullptr;
        return root_[i1]->values[i2];
    }
    
    // 設置值 - 按需分配葉子節點
    void set(uint64_t key, void* value) {
        if(key >= (1ULL << BITS)) return;
        
        uint64_t i1 = key >> LEAF_BITS;
        uint64_t i2 = key & (LEAF_SIZE - 1);
        
        // 按需分配葉子節點
        if(root_[i1] == nullptr) {
            root_[i1] = new Leaf();
            cout << "分配新的葉子節點: " << i1 << endl;
        }
        
        root_[i1]->values[i2] = value;
    }
};

這樣可以支持36位鍵空間（256TB地址），但內存是按需分配的，不會浪費。

在我最近帶領學員做的高性能內存池項目中，我們就採用了這種二級基數樹的設計思路，不過做了更多的工程優化。實際效果非常不錯，相比原來的unordered_map方案，性能提升了10倍以上。

感興趣的朋友可以看這篇文章： 三週肝出4000行代碼，我的內存池竟然讓malloc"破防"了！性能暴漲7.37倍背後的技術真相

我的使用心得

用了基數樹這麼久，我總結幾個心得：

  1. 不要被"樹"這個名字迷惑了，基數樹本質上就是數組
  2. 在高性能場景下，基數樹是神器，特別是內存池、路由表這些場景
  3. 多層基數樹是進階版本，1層夠用就別搞複雜

編譯運行試試看

想要自己試試的同學，把文章中的代碼整合一下，用這個命令編譯：

g++ -std=c++11 -O2 radix_tree_test.cpp -o test
./test

在我的Ubuntu 20.04上跑得飛快！

寫在最後

基數樹真的是一個被低估的數據結構。

在合適的場景下，它能帶來數倍甚至數十倍的性能提升。Google、Facebook這些大廠的底層庫都在大量使用基數樹，絕對不是沒有道理的。

下次如果你遇到需要快速鍵值查找的場景，特別是鍵範圍相對固定的情況，不妨試試基數樹。説不定會有意想不到的驚喜！

好了，今天就聊到這裏。如果你覺得這篇文章對你有幫助，記得點贊、收藏、關注三連哦！

有什麼問題歡迎在評論區討論，我看到會第一時間回覆的。

C++ 項目實戰課程

不過話説回來，這些底層性能優化技巧，光看理論是遠遠不夠的，必須在真實項目中摸爬滾打才能融會貫通。

這段時間我一直在帶學員做一些硬核的C++項目，從底層數據結構到高併發組件，每個項目都是企業級的真實場景。看到不少同學通過這些實戰項目，技術水平有了質的飛躍，面試時也更有底氣了。

C++硬核項目實戰：
手擼線程池才是C++程序員的硬實力！7天手把手帶你從0到1完整實現

三週肝出4000行代碼，我的內存池竟然讓malloc"破防"了！性能暴漲7.37倍背後的技術真相

手擼4200行MySQL連接池，8天帶你搞定後端核心組件！

終於有人把C++多線程下載工具講透了！7天手把手帶你寫出專業級工具

這些項目都會深入涉及多線程編程、併發優化、 高併發處理、系統級性能調優等企業級開發的核心技術，而且是在真實的項目環境中應用。不是紙上談兵，而是真刀真槍地寫代碼、調優化、解決實際問題。

感興趣的同學，趕緊加我vx：jkfwdkf，備註「項目實戰」！

c++
user avatar sherlocked93 头像 hlinleanring 头像 donnytab 头像 youqingyouyidedalianmao 头像 artificer 头像 liu_chen 头像 ishare 头像 aixiaodewulongcha_ehoerm 头像 goodcitizen 头像 duwenlong 头像 pcworld 头像
点赞 11 用户, 点赞了这篇动态!
点赞

Add a new 评论

Some HTML is okay.