C++ 高并发内存池：基于基数树的性能优化与测试

我们将基数树替换了 SpanMap 原本的哈希表结构：

TCMalloc_PageMap2<32 - PAGE_SHIFT> _id_span_map;

同时部分接口也需要相应替换。以 set(key, value) 为例，在 NewSpan 函数中，我们需要将新的页 ID 映射更新到基数树中：

Span* PageCache::NewSpan(size_t k) {
    assert(k > 0);
    if (k > NPAGES - 1) { 
        // ... error handling
        _id_span_map.set(id, span);
        return span;
    }
    if (!_spanlists[k].Empty()) {
        Span* kspan = _spanlists[k].PopFront();
        for (size_t i = 0; i < kspan->_num; i++) 
            _id_span_map.set(kspan->_page_id + i, kspan);
        return kspan;
    }
    // ... logic continues
}

对于 get(key) 获取返回值，逻辑也类似。例如在 SpanMapFindObject 中：

Span* PageCache::SpanMapFindObject(void* ptr) {
    PAGE_ID id = ((PAGE_ID)ptr >> PAGE_SHIFT);
    Span* span = (Span*)_id_span_map.get(id);
    assert(span != nullptr);
    return span;
}

2. 性能测试

为了验证优化效果，我们编写了基准测试程序，对比标准库 malloc/free 与自定义内存池的并发性能。

// ntimes 一轮申请和释放内存的次数
// rounds 轮次
void BenchmarkMalloc(size_t ntimes, size_t nworks, size_t rounds) {
    std::vector<std::thread> vthread(nworks);
    std::atomic<size_t> malloc_costtime = 0;
    std::atomic<size_t> free_costtime = 0;
    for (size_t k = 0; k < nworks; ++k) {
        vthread[k] = std::thread([&]() {
            std::vector<void*> v;
            v.reserve(ntimes);
            for (size_t j = 0; j < rounds; ++j) {
                size_t begin1 = clock();
                for (size_t i = 0; i < ntimes; i++) {
                    v.push_back(malloc((16 + i) % 8192 + 1));
                }
                size_t end1 = clock();
                size_t begin2 = clock();
                for (size_t i = 0; i < ntimes; i++) {
                    free(v[i]);
                }
                size_t end2 = clock();
                v.clear();
                malloc_costtime += (end1 - begin1);
                free_costtime += (end2 - begin2);
            }
        });
    }
    for (auto& t : vthread) { t.join(); }
    printf("%zu 个线程并发执行%zu 轮次，每轮次 malloc %zu 次：花费：%zu ms\n", nworks, rounds, ntimes, malloc_costtime.load());
    printf("%zu 个线程并发执行%zu 轮次，每轮次 free %zu 次：花费：%zu ms\n", nworks, rounds, ntimes, free_costtime.load());
    printf("%zu 个线程并发 malloc&free %zu 次，总计花费：%zu ms\n", nworks, nworks * rounds * ntimes, malloc_costtime.load() + free_costtime.load());
}

void BenchmarkConcurrentMalloc(size_t ntimes, size_t nworks, size_t rounds) {
    std::vector<std::thread> vthread(nworks);
    std::atomic<size_t> malloc_costtime = 0;
    std::atomic<size_t> free_costtime = 0;
    for (size_t k = 0; k < nworks; ++k) {
        vthread[k] = std::thread([&]() {
            std::vector<void*> v;
            v.reserve(ntimes);
            for (size_t j = 0; j < rounds; ++j) {
                size_t begin1 = clock();
                for (size_t i = 0; i < ntimes; i++) {
                    v.push_back(ConcurrentAlloc((16 + i) % 8192 + 1));
                }
                size_t end1 = clock();
                size_t begin2 = clock();
                for (size_t i = 0; i < ntimes; i++) {
                    ConcurrentDealloc(v[i]);
                }
                size_t end2 = clock();
                v.clear();
                malloc_costtime += (end1 - begin1);
                free_costtime += (end2 - begin2);
            }
        });
    }
    for (auto& t : vthread) { t.join(); }
    printf("%zu 个线程并发执行%zu 轮次，每轮次 concurrent alloc %zu 次：花费：%zu ms\n", nworks, rounds, ntimes, malloc_costtime.load());
    printf("%zu 个线程并发执行%zu 轮次，每轮次 concurrent dealloc %zu 次：花费：%zu ms\n", nworks, rounds, ntimes, free_costtime.load());
    printf("%zu 个线程并发 concurrent alloc&dealloc %zu 次，总计花费：%zu ms\n", nworks, nworks * rounds * ntimes, malloc_costtime.load() + free_costtime.load());
}

int main() {
    size_t n = 10000;
    std::cout << "==========================================================" << std::endl;
    BenchmarkConcurrentMalloc(n, 4, 10);
    std::cout << std::endl << std::endl;
    BenchmarkMalloc(n, 4, 10);
    std::cout << "==========================================================" << std::endl;
    return 0;
}