本项目实现了一个高效的多层级并发内存池，借鉴了 TCMalloc 的设计思想，通过三级缓存架构减少锁竞争，提升多线程环境下的内存分配性能。
| 特性 | 描述 |
|---|---|
| 三级缓存 | ThreadCache → CentralCache → PageCache |
| 基数树优化 | 使用三层基数树替代 std::map，提升页号查找效率， O(log n) → O(1) |
| 零锁分配 | 线程本地缓存无锁操作，减少锁竞争 |
| 内存合并 | 释放时自动合并相邻空闲页 |
| 对象池 | 使用 ObjectPool 管理 Span 对象的创建与销毁 |
| 任务窃取 | ThreadCache 可从其他线程窃取空闲对象，减少中心缓存访问 |
| 异常处理 | 分配失败处理、构造异常安全、调试模式检测 |
| 动态扩容 | 按需向系统申请内存，支持水位线策略回收 |
- 减少锁竞争：每个线程拥有独立的 ThreadCache，分配时无需加锁
- 批量操作：ThreadCache 与 CentralCache 之间采用批量分配/释放
- 高效映射：基数树 O(1) 时间复杂度查找页号对应的 Span
- 内存复用：空闲内存块快速复用，减少系统调用
# 编译核心文件
g++ -c source_file/PageCache.cpp source_file/CentralCache.cpp \
source_file/ThreadCache.cpp source_file/ConcurrentAlloc.cpp \
-I header_file
# 编译测试文件
g++ -c source_file/finalTest.cpp -I header_file -o finalTest.o
# 链接
g++ PageCache.o CentralCache.o ThreadCache.o ConcurrentAlloc.o \
finalTest.o -static -g -o finalTest.exe
# 运行
./finalTest.exe==========================================================
4个线程并发执行1轮次，每轮次concurrent alloc 10000次: 花费：300 ms
4个线程并发执行1轮次，每轮次concurrent dealloc 10000次: 花费：20 ms
4个线程并发concurrent alloc&dealloc 40000次，总计花费：320 ms
4个线程并发执行1轮次，每轮次malloc 10000次: 花费：1728 ms
4个线程并发执行1轮次，每轮次free 10000次: 花费：3919 ms
4个线程并发malloc&free 40000次，总计花费：5647 ms
4个线程并发执行1轮次，每轮次创建10000个小vector(std::allocator): 花费：2901 ms
4个线程并发执行1轮次，每轮次销毁10000个小vector(std::allocator): 花费：731 ms
4个线程并发创建&销毁40000个小vector(std::allocator)，总计花费：3632 ms
4个线程并发执行1轮次，每轮次创建10000个小vector(ConcurrentAllocator): 花费：28 ms
4个线程并发执行1轮次，每轮次销毁10000个小vector(ConcurrentAllocator): 花费：25 ms
4个线程并发创建&销毁40000个小vector(ConcurrentAllocator)，总计花费：53 ms
==========================================================
ConcurrentMemoryPoolOptimize/
├── header_file/ # 头文件目录
│ ├── Common.h # 公共定义（Span, FreeList, SpanList, StealQueue）
│ ├── ObjectPool.h # 对象池实现
│ ├── ThreadCache.h # 线程缓存（含任务窃取）
│ ├── CentralCache.h # 中央缓存
│ ├── PageCache.h # 页面缓存（含动态扩容）
│ ├── ConcurrentAlloc.h # 对外接口
│ ├── ConcurrentAllocator.h # C++标准分配器接口
│ └── TCMalloc_PageMap3.h # 基数树实现
├── source_file/ # 源文件目录
│ ├── ThreadCache.cpp # 线程缓存实现
│ ├── CentralCache.cpp # 中央缓存实现
│ ├── PageCache.cpp # 页面缓存实现
│ ├── ConcurrentAlloc.cpp # 对外接口实现
│ └── finalTest.cpp # 性能测试
┌─────────────────────────────────────────────────────────────┐
│ 用户层 │
│ ConcurrentAlloc / ConcurrentFree │
└─────────────────────────┬───────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────┐
│ ThreadCache (线程本地) │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ FreeList[0] FreeList[1] ... FreeList[127] │ │
│ │ (8B) (16B) ... (1024B) │ │
│ └─────────────────────────────────────────────────────┘ │
│ - 每个线程独立，无锁访问 │
│ - 大小对齐：8B ~ 1024B，共128个桶 │
└─────────────────────────┬───────────────────────────────────┘
│ 批量申请/释放
▼
┌─────────────────────────────────────────────────────────────┐
│ CentralCache (全局) │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ SpanList[0] SpanList[1] ... SpanList[127] │ │
│ │ (8B) (16B) ... (1024B) │ │
│ └─────────────────────────────────────────────────────┘ │
│ - 每个桶有独立的锁，减少锁竞争 │
│ - 管理多个 Span，每个 Span 包含多个内存块 │
└─────────────────────────┬───────────────────────────────────┘
│ 申请 Span
▼
┌─────────────────────────────────────────────────────────────┐
│ PageCache (全局) │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ SpanList[1] SpanList[2] ... SpanList[128] │ │
│ │ (1页) (2页) ... (128页) │ │
│ └─────────────────────────────────────────────────────┘ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ TCMalloc_PageMap3 (基数树) │ │
│ │ PageID → Span* 映射，支持48位页号 │ │
│ └─────────────────────────────────────────────────────┘ │
│ - 全局唯一，使用互斥锁保护 │
│ - 向系统申请物理内存（以页为单位） │
└─────────────────────────────────────────────────────────────┘
1. ThreadCache（线程私有）
- 每个线程独立拥有，无锁访问
- 快速分配已缓存的小对象
- 只有缓存耗尽时才向 CentralCache 申请
2. CentralCache（桶级锁）- 批量中转
- 作为 ThreadCache 和 PageCache 之间的缓冲层
- 桶级锁：不同大小的内存块使用不同的锁
- 批量分配/释放，减少跨层级调用次数
3. PageCache（页面级）- 物理内存管理
- 管理物理页面的分配与释放
- Span 合并：释放时合并相邻空闲页
- 向系统申请/归还内存（以页为单位）
三级架构通过分层职责分离，在并发性能和内存利用率之间取得了最佳平衡。
| 成员 | 类型 | 说明 |
|---|---|---|
_objSize |
size_t | 每个对象的大小（0 表示大对象） |
_n |
size_t | Span 包含的页数 |
_pageID |
PageID | 起始页号 |
_freeList |
void* | 空闲内存块链表头 |
_next / _prev |
Span* | SpanList 双向链表指针 |
_isUse |
bool | 是否正在被使用 |
use_count |
size_t | 引用计数 |
| 成员/方法 | 说明 |
|---|---|
Push(obj) |
将对象加入空闲链表 |
Pop() |
从空闲链表取出一个对象 |
Empty() |
判断链表是否为空 |
Size() |
返回链表大小 |
| 成员/方法 | 说明 |
|---|---|
Begin() |
返回第一个 Span |
End() |
返回哨兵节点 |
Insert(pos, ptr) |
在指定位置插入 Span |
Erase(pos) |
删除指定 Span |
PushFront(ptr) |
在头部插入 Span |
PopFront() |
从头部删除 Span |
使用三层基数树替代 std::map，实现 O(1) 时间复杂度的页号到 Span 的映射。
页号 (48位)
├── 第一层 (10位) → 索引 root_[0..1023]
│ └── 第二层 (11位) → 索引 node[0..2047]
│ └── 第三层 (27位) → 索引 leaf[0..134217727]
│ └── Span*
- TCMalloc_PageMap3 类接口
| 方法 | 参数 | 返回值 | 说明 |
|---|---|---|---|
set(key, value) |
Number key, void* value | void | 设置映射 |
get(key) |
Number key | void* | 获取映射 |
erase(key) |
Number key | void | 删除映射 |
Ensure(start, n) |
Number start, size_t n | bool | 确保 n 个连续页的节点已分配 |
| 层级 | 锁类型 | 说明 |
|---|---|---|
| ThreadCache | 无锁 | 线程本地存储，每个线程独立 |
| CentralCache | 桶级锁 | 每个 SpanList 有独立的锁 |
| PageCache | 全局锁 | 使用 _pageMtx 保护所有操作 |
使用 thread_local 实现线程独立的缓存：
| 组件 | 单例类型 | 获取方式 |
|---|---|---|
| CentralCache | 饿汉模式 | CentralCache::GetInstance() |
| PageCache | 饿汉模式 | PageCache::GetInstance() |
| EmergencyPool | 懒汉模式 | EmergencyPool::Instance() |
1. CentralCache（中央缓存）
- 必要性：所有线程共享同一个中央缓存来批量申请/释放内存
- 原因：如果每个线程独立一个中央缓存，则无法实现跨线程的内存共享和负载均衡
- 作用：协调多个 ThreadCache 之间的内存分配，维护全局的 Span 链表
2. PageCache（页面缓存）
- 必要性：系统只需要一个页面级缓存来管理物理内存
- 原因：多个页面缓存会导致 Span 合并困难、内存碎片加剧、页号映射冲突
- 作用：统一管理系统物理内存、Span 合并、向系统申请/释放内存
3. EmergencyPool（紧急内存池）
- 必要性：紧急情况下全局共享一个后备内存池
- 原因：系统内存耗尽时需要统一的应急资源，避免多个组件各自预分配
- 作用：作为最后手段的后备内存来源
| 区间 | 对齐粒度 | 桶数 |
|---|---|---|
| 统一大小分配 | SizeClass 对齐 | 减少外部碎片 |
| 内存复用 | FreeList 空闲链表 | 快速分配已释放内存 |
| Span 合并 | ReleaseSpanToPageCache | 合并相邻空闲页 |
| 批量操作 | FetchRangeObj | 减少跨层级调用开销 |
| 大对象直接分配 | >256KB 直接向系统申请 | 避免小对象池碎片化 |
- Span 合并机制 当 Span 完全空闲时，PageCache 会尝试合并相邻空闲 Span 释放 Span → 检测左边相邻 Span并尝试合并 → 检测右边相邻 Span并尝试合并
在传统线程缓存中，线程 A 释放的对象属于线程 B 的缓存块时，无法直接放回 B，只能还给 CentralCache，增加了中心锁竞争。任务窃取机制让 ThreadCache 可以直接从其他线程的本地缓存中"偷"空闲对象，实现更好的负载均衡。
| 成员 | 类型 | 说明 |
|---|---|---|
_head |
std::atomic<Node*> |
队列头指针（原子操作） |
_size |
std::atomic<size_t> |
当前队列大小 |
| 方法 | 说明 |
|---|---|
Push(obj) |
将对象加入队列 |
Pop() |
从队列取出一个对象 |
PopBatch(size) |
批量取出多个对象 |
StealHalf() |
窃取队列中一半的对象 |
| 策略 | 实现 | 说明 |
|---|---|---|
| 随机选择受害者 | 随机挑选 N 个其他线程 | 减少重复冲突 |
| 批量窃取 | 一次窃取多个对象 | 平摊开销 |
| 窃取阈值 | 本地缓存空虚到一定程度才触发 | 避免无意义竞争 |
当系统内存耗尽时，使用预分配的紧急内存池处理关键分配
| 策略 | 说明 |
|---|---|
返回 nullptr |
兼容 malloc 语义，由上层处理 |
| 抛异常 | 可配置策略，适用于 STL 容器 |
| 强制回收 | 尝试回收空闲缓存后重试 |
当使用 new_object<T> 接口时，构造函数抛异常会自动回滚内存
┌──────────────────────────────────────────────────────────┐
│ PageCache │
│ ┌────────────────────────────────────────────────────┐ │
│ │ SpanList[1] SpanList[2] ... SpanList[128] │ │
│ │ 空闲 Span 按页数组织 │ │
│ └────────────────────────────────────────────────────┘ │
│ ┌────────────────────────────────────────────────────┐ │
│ │ TCMalloc_PageMap3 (页号→Span映射) │ │
│ └────────────────────────────────────────────────────┘ │
│ ┌────────────────────────────────────────────────────┐ │
│ │ 内存统计: _totalPages, _peakPages, _allocatedBytes │ │
│ └────────────────────────────────────────────────────┘ │
└────────────────────────────┬───────────────────────────┘
│ 按需申请
▼
┌──────────────────────────────────────────────────────────┐
│ 系统调用层 │
│ mmap(MAP_PRIVATE|MAP_ANONYMOUS) / munmap │
└──────────────────────────────────────────────────────────┘
水位线策略：低于峰值 50% 时触发回收
大对象（超过 256KB）直接使用 mmap 分配，不进入缓存：
| 对象大小 | 分配策略 |
|---|---|
| ≤ 256KB | 走内存池缓存 |
| > 256KB | 直接 mmap |
| 方法 | 说明 |
|---|---|
GetMemoryStats() |
返回当前内存使用统计 |
PrintMemoryStats() |
打印内存使用报告 |
GetPeakUsage() |
返回内存使用峰值 |
本项目提供了符合 C++ 标准的自定义分配器 ConcurrentAllocator，可以无缝替换 std::allocator，让 STL 容器使用并发内存池进行内存管理。
| 特性 | 说明 |
|---|---|
| 标准兼容 | 完全符合 C++11/14/17 分配器要求 |
| 线程安全 | 基于并发内存池，支持多线程并发分配 |
| rebind 机制 | 支持容器内部类型转换（如 std::list 的节点类型） |
| 异常安全 | 内存分配失败时抛出 std::bad_alloc |
| 零拷贝 | 分配器对象可自由拷贝，无状态设计 |
#include <vector>
#include "ConcurrentAllocator.h"
// 使用 ConcurrentAllocator 替代 std::allocator
std::vector<int, ConcurrentAllocator<int>> vec;
| 方法 | 功能 |
|---|---|
allocate(n) |
分配 n 个 T 类型大小的内存 |
deallocate(p, n) |
释放指针 p 指向的内存 |
construct(p, args...) |
在已分配内存上构造对象 |
destroy(p) |
析构对象但不释放内存 |
max_size() |
返回最大可分配数量 |
address(x) |
返回对象的地址 |
- 内存压缩：对大对象使用更高效的分配策略
- 统计监控：添加内存使用统计和监控接口
- 内存预分配：提前分配内存池，减少运行时系统调用
- C++20 特性：支持
std::pmr(Polymorphic Memory Resource)