1.1 研究背景#

在服务器、游戏引擎、数据库、并行计算框架以及通用 C/C++ 应用中，动态内存分配会频繁出现在对象创建、容器扩容、消息处理和任务调度等路径中。单次内存申请的耗时通常很短，但在每秒数百万甚至数千万次调用的工作负载下，分配器的固定开销会被持续放大。尤其在多线程环境中，如果所有线程都需要访问同一个共享分配结构，互斥锁和共享元数据会进一步限制可扩展性。

线程缓存型分配器的核心思想是把“最常发生的操作”尽量留在线程本地，把跨线程共享和向操作系统申请内存的操作变成低频路径。Google TCMalloc 的公开设计文档同样采用前端缓存、中间层和后端的分层思想，并指出线程/CPU 本地缓存可以减少大多数分配路径上的锁竞争[1]。Hoard 等多线程分配器研究也表明，分配器的可扩展性和内存复用策略是多核环境中的重要性能因素[2]。

本文实现的 ThreadCachingMalloc 并非完整复刻某个工业分配器，而是在 C++17 下独立完成一个结构清晰、可运行、可测试的三级缓存内存管理系统，并通过实际 benchmark 数据验证其设计效果。

1.2 研究目标#

本文主要解决以下问题：

1. 为高频小对象建立线程私有缓存，使最常见的分配和释放路径不需要访问共享锁；
2. 使用 Center Cache 批量向 Thread Cache 转移对象，降低跨层访问频率；
3. 使用 Page Cache 统一管理连续页内存，并通过 Span 完成切分、回收和合并；
4. 设计分级大小对齐与 208 个 size class，在索引速度和内部碎片之间取得折中；
5. 在真实多线程测试中，从对象大小、线程数、batch 和操作次数等维度与 malloc/free 比较；
6. 根据性能异常反推实现中的瓶颈，为后续优化提供依据。

1.3 本文主要工作#

本文完成了从底层页申请到线程本地对象分配的完整路径，包括跨平台页接口、FreeList、Span、SpanList、Thread Cache、Center Cache、Page Cache 和外部 ThreadCacheMalloc/ThreadCacheFree 接口，并编写了可重复运行的基准测试程序。实验结果不只报告优势场景，同时保留并分析性能反转用例，以避免仅凭局部最优结果评价系统。

3.1 分级对齐#

为了避免每一种字节大小都建立单独链表，系统按照申请大小选择不同对齐粒度：

因此共有 208 个 size class。对齐后的对象大小可以表示为：

[ S_{aligned}=\left\lceil \frac{S}{A}\right\rceil A ]

其中 (S) 为用户申请大小，(A) 为当前区间的对齐粒度。

这种分级策略使小对象保持较细粒度，降低内部碎片；对象越大，对齐粒度越粗，从而控制桶数量和元数据规模。

3.2 页大小#

源码使用：

1
inline constexpr size_t PAGE_SHIFT = 12;

因此本文实现中的逻辑页大小为：

[ PAGE_SIZE = 1 << 12 = 4096\ \text{B}=4\ \text{KiB} ]

字节数转换为页数时采用向上取整：

[ pageNums=\left\lceil\frac{size}{4096}\right\rceil ]

Page Cache 最多使用 256 页作为常规连续 Span 的缓存规模，即常规最大 Span 为 1 MiB。

4.1 FreeList#

FreeList 使用侵入式单链表。空闲对象本身的起始字节被复用为 next 指针：

1
inline static void*& NextObj(void* obj) {
2
    return *(void**)obj;
3
}

这样无需为每个空闲对象额外建立链表节点。核心操作包括 Push、Get、PushRange 和 GetRange。单对象操作主要由若干次指针读写组成，而批量操作可以一次转移整段对象链。

FreeList 还维护 _singleApplyMemoryNums，用于记录当前线程该规格向 Center Cache 单次申请对象的数量。该变量既影响 refill 大小，也参与线程缓存回收阈值计算。

4.2 Span#

Span 描述一段连续页，其关键状态包括：

1
PAGE_ID id;
2
size_t pageNums;
3
FreeList _freeList;
4
size_t usedMemoryNums;
5
bool isPageCache;
6
Span* next;
7
Span* previous;

Center Cache 从 Page Cache 获得 Span 后调用 CutFreeList(bucketIndex)，按照 size class 对象大小将整段连续页切成等长对象并串成 FreeList。由于申请页数使用对象大小与页大小的最小公倍数关系计算，Span 总字节数能够被当前对象规格整除，避免尾部产生无法切分的残余空间。

4.3 SpanList#

SpanList 使用带哨兵头结点的双向循环链表。其特点是：

• 空链表通过 _head.next == &_head 判断；
• 插入和删除均为 O(1)；
• 不需要对首节点和尾节点单独处理空指针边界；
• Span 自身保存 next/previous，无需额外链表节点。

Center Cache 和 Page Cache 都使用 SpanList，只是索引维度不同：前者按对象规格索引，后者按页数索引。

5.1 thread_local 线程私有实例#

对外接口使用：

1
static thread_local ThreadCache threadCache;

为每个线程构造独立 ThreadCache。每个 ThreadCache 内部保存 208 个 FreeList。由于正常的小对象分配和释放只访问当前线程自己的结构，因此热路径无需互斥锁，这是整个系统最重要的并发优化。

5.2 小对象分配#

当 size <= 256 KiB 时：

1
1. 根据 size 计算 size class；
2
2. 检查当前线程对应 FreeList；
3
3. 非空：直接 Get()；
4
4. 为空：从 Center Cache 批量申请；
5
5. 将批量对象挂入本地 FreeList；
6
6. 再弹出一个对象返回。

本地命中时不需要系统调用，也不需要访问共享 Center Cache。

5.3 慢启动式批量申请#

Thread Cache 每次缺货时会调整单次申请数量：

1
reqMemoryNums = reqMemoryNums * 1.1 + 1;
2
reqMemoryNums = std::min(
3
    reqMemoryNums,
4
    Span::LimitApplyNum(size)
5
);

该策略不是固定 batch，而是随着该规格被持续使用逐步增加单次 refill 数量。对象越大，LimitApplyNum 越小，从而限制单线程对大对象的缓存量；对象越小，可以批量缓存更多对象以降低共享层访问次数。

LimitApplyNum 以 256 KiB 为基本容量计算，并将对象数限制在 2～1024 之间。

5.4 释放与回收#

小对象释放时先直接压入当前线程 FreeList。当：

[ FreeList.Size > 2\times singleApplyMemoryNums ]

时，线程缓存将部分对象交还 Center Cache。默认回收数量为：

[ \max(singleApplyMemoryNums,\ FreeList.Size/2) ]

该策略在“复用速度”和“避免单线程囤积”之间做折中。

5.5 大对象路径#

当 size > 256 KiB 时，不再进入小对象 size class，Thread Cache 直接计算页数并向 Page Cache 请求 Span。释放时则根据对象地址右移 PAGE_SHIFT 得到页号，再交给 Page Cache 回收。

6.1 向 Thread Cache 提供对象#

当 Thread Cache 请求一批对象时，Center Cache 锁定对应规格桶并寻找可用 Span。若当前桶为空或现有 Span 均没有可用对象，则临时释放桶锁，从 Page Cache 获取新 Span，完成切分后再将其插入当前规格桶。

之所以在访问 Page Cache 前释放 Center Cache 桶锁，是为了避免较慢的页级操作长时间阻塞同一 size class 上的其他线程。

6.2 从 Thread Cache 回收对象#

线程缓存归还一批对象后，Center Cache 逐个根据对象地址计算 PAGE_ID，再通过 Page Cache 的映射结构定位所属 Span，调用 Span::Push 将对象归还。

当 usedMemoryNums == 0 时，说明该 Span 的全部对象都已经返回。如果当前规格桶中仍有其他 Span，当前完全空闲 Span 会被移出 Center Cache 并交还 Page Cache。

7.1 页数桶#

Page Cache 使用：

1
SpanList _spanList[PageMaxContinuousNums + 1];

其中 PageMaxContinuousNums = 256。下标表示 Span 的页数，因而可以直接定位给定页数的空闲链表。

7.2 Span 申请与拆分#

如果请求 n 页，而 _spanList[n] 为空，Page Cache 会继续寻找更大的可用 Span。找到更大 Span 后，从其尾部切出 n 页构造新 Span，剩余部分重新挂入对应页数桶。

如果 1～256 页范围内都没有可用 Span，则向操作系统一次申请 256 页，即 1 MiB，再从中拆分所需部分。通过这种方式，多个后续请求可以复用同一次系统级页申请。

7.3 PAGE_ID 到 Span 的映射#

本版本使用：

1
std::unordered_map<PAGE_ID, Span*> _pageIDtoSpanPtrHash;

记录页号到 Span 的映射。当一个 Span 被提供给上层时，其覆盖的页会写入映射表，从而使 Center Cache 能够根据对象地址快速定位所属 Span。

MapSpanIDToSpanPtr 需要持有 Page Cache 的全局 _mtx。因此这条路径虽然功能直接，但在大量对象从 Thread Cache 回收到 Center Cache 时可能形成明显的共享锁压力。

7.4 Span 合并#

Span 回收到 Page Cache 后，会分别检查前一页以及后一段起始页是否存在可合并的空闲 Span。若地址连续、邻居位于 Page Cache，并且合并后的页数不超过 256，则从原页数桶摘除邻居并进行合并。

这一过程可以减少外部碎片，使较大的连续页请求更容易由缓存满足。

7.5 操作系统接口#

Windows 下使用：

1
VirtualAlloc(..., MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
2
VirtualFree(ptr, 0, MEM_RELEASE);

VirtualAlloc 用于在进程虚拟地址空间中保留并提交页，VirtualFree 负责释放对应区域[3][4]。在源码的 Linux 分支中还封装了 mmap/munmap，但本次 benchmark 的实验环境为 Windows 10，因此性能数据对应 Windows 路径。

9.1 分配#

1
ThreadCacheMalloc(size)
2
        │
3
        ▼
4
size <= 256 KiB ?
5
   ┌────┴────┐
6
  是         否
7
  │           │
8
计算桶下标   计算所需页数
9
  │           │
10
本地 FreeList 是否为空？  → Page Cache::NewSpan
11
  │
12
┌─┴─────────────┐
13
否               是
14
│                 │
15
Get()       Center Cache 批量取对象
16
│                 │
17
返回          Center 无可用 Span？
18
                  │
19
                  ▼
20
             Page Cache::NewSpan
21
                  │
22
               CutFreeList
23
                  │
24
             返回一批对象
25
                  │
26
            本地 FreeList
27
                  │
28
                Get()

9.2 释放#

1
ThreadCacheFree(ptr, size)
2
        │
3
        ▼
4
size <= 256 KiB ?
5
   ┌────┴────┐
6
  是         否
7
  │           │
8
Push 到本地    根据地址计算 PAGE_ID
9
FreeList       │
10
  │            ▼
11
超过回收阈值？ Page Cache::RecydeSpan
12
  │
13
  ├─否→结束
14
  │
15
  └─是
16
     │
17
     ▼
18
Center Cache 批量回收
19
     │
20
根据 PAGE_ID 查 Span
21
     │
22
Span::Push
23
     │
24
Span 全部空闲？
25
  ┌──┴──┐
26
 否     是
27
 │      │
28
结束   回 Page Cache
29
          │
30
       尝试合并邻居

10.1 实验平台#

本次测试使用同一台计算机完成，硬件与软件环境如下：

选择 Release x64 是为了使优化后的实际运行路径参与测试，避免 Debug 模式下断言、迭代器检查和未优化代码对分配器性能产生非代表性影响。

10.2 基本工作负载#

每个线程循环执行：

1
批量申请 N 个对象
2
→ 写每个对象首字节
3
→ 批量释放 N 个对象
4
→ 重复直到完成规定 pair 数

1 pair 表示“一次 allocation + 一次 free”。

测试程序还将分配地址参与 checksum 计算，并实际写对象首字节，避免编译器把分配调用视为无可观察效果而删除。

10.3 同步起跑与计时边界#

每个 worker 首先完成线程内预热，然后进入统一栅栏。主线程等待全部 worker ready 后记录开始时间并同时放行。所有 worker 完成正式 workload 后，主线程记录结束时间。

测试线程在计时结束前不会被销毁，因此 ThreadCache 析构时将剩余本地缓存归还 Center Cache 的成本不包含在正式计时区间内。本实验测量的是分配器的稳态分配/释放性能。

10.4 预热、重复与中位数#

每个线程最多预热：

[ 4096\ pairs/thread ]

预热与正式测试发生在同一个 worker 上，从而真正建立该线程自己的 thread_local ThreadCache 状态。

每组正式运行 5 次。奇数轮执行顺序为：

1
ThreadCachingMalloc → malloc

偶数轮为：

1
malloc → ThreadCachingMalloc

最终取 5 次运行时间的中位数。本文定义：

[ Speedup= \frac{T_{malloc}}{T_{ThreadCachingMalloc}} ]

若 Speedup > 1，说明 ThreadCachingMalloc 更快。

10.5 测试维度#

测试程序共启用五类 workload：

• 对象大小扫描：4 B ～ 256 KiB，共 17 个点；
• 线程数扫描：1 ～ 100 线程，共 9 个点；
• batch 扫描：1 ～ 2048，共 9 个点；
• 每线程 pair 数扫描：100,000 ～ 10,000,000，共 5 个点；
• 混合场景：6 组。

因此得到 46 组汇总用例和 460 条原始计时记录。

11.1 总体结果#

全部 46 组用例均正常完成，没有出现 alloc_failed 或因 1 GiB 安全阈值而跳过的情况。

总体上 ThreadCachingMalloc 在本 benchmark 的大多数配置中明显快于 malloc/free，但性能并非在所有参数组合下都占优。

11.2 对象大小扫描#

测试条件：24 线程、每线程 1,000,000 pair、batch=64。

从 4 B 到 8 KiB，ThreadCachingMalloc 在全部测试点获胜。其中 512 B 的加速比为 29.1866×，1024 B 为 24.6760×，128 B 为 21.0285×。这些对象在 Thread Cache 中能够形成高复用的本地 FreeList，命中后的工作主要是链表头指针操作。

32 KiB～256 KiB 范围内 ThreadCachingMalloc 仍然获胜，但加速比下降到约 2.60×～5.43×。对象变大后，同一 Span 能切出的对象数量减少，单线程允许缓存的对象数量也受 LimitApplyNum 限制，Center Cache 和 Page Cache 的参与比例随之增加。

最明显的异常发生在 16 KiB。此时 ThreadCachingMalloc 中位数达到 5.703320 s，而 malloc 为 0.421192 s，加速比仅 0.0739×。

11.3 16 KiB 异常的源码级分析#

16 KiB 用例不是偶发噪声。ThreadCachingMalloc 五次原始结果范围为 5.658290～5.731051 s，malloc 为 0.416718～0.422325 s，两者每次都保持明显差距。

结合源码可以得到一个较强的解释。

对于 16 KiB 对象：

[ LimitApplyNum=\frac{256KiB}{16KiB}=16 ]

因此 _singleApplyMemoryNums 最终不会超过 16。Thread Cache 的回收触发条件为：

[ FreeList.Size > 2\times16 = 32 ]

对象大小扫描使用 batch=64。也就是说，每轮一次释放 64 个对象时，本地 FreeList 明显超过回收阈值，会反复向 Center Cache 归还对象。

而 Center Cache 对归还对象的处理不是仅修改本地元数据。它对每个对象执行：

1
object address
2
→ PAGE_ID
3
→ PageCache::MapSpanIDToSpanPtr
4
→ unordered_map 查找
5
→ Span::Push

其中 MapSpanIDToSpanPtr 还需要 Page Cache 全局 mutex。24 个线程同时执行大批量归还时，频繁的页号映射和全局锁竞争会集中爆发。

这一判断还能被另一条数据佐证：混合 workload 中同样是 16 KiB、24 线程，但 batch=32 时，ThreadCachingMalloc 反而获得 12.5401× 加速。batch=32 恰好没有超过最终的 2 × 16 = 32 阈值，因此对象可以长期保留在线程本地缓存中，不会在每轮释放时大量流向共享层。

因此，16 KiB 性能反转并不能简单解释成“16 KiB 不适合线程缓存”，更准确的结论是：

当前固定回收阈值与大对象较小的 LimitApplyNum 结合后，在 batch=64 处触发了高频 Thread Cache → Center Cache → Page Cache 映射路径。

这也是本版本最值得优化的瓶颈。

11.4 线程数量扫描#

测试条件：64 B、每线程 1,000,000 pair、batch=256。

从单线程到 100 线程，ThreadCachingMalloc 在全部测试点获胜。加速比位于 7.5248×～11.9861×。

吞吐量方面，ThreadCachingMalloc 从 1 线程的约 190.62 Mpair/s 提升到 100 线程的约 2016.56 Mpair/s；系统 malloc/free 在 100 线程时约为 194.25 Mpair/s。

这一结果说明线程缓存有效降低了共享锁在热路径中的比例。线程数增加时，每个线程仍主要访问自己的 FreeList；只有本地缓存 miss 或溢出时才进入共享 Center Cache。需要指出的是，100 线程已经明显超过 24 个逻辑处理器，因此该点还叠加了操作系统调度和上下文切换影响。即便如此，ThreadCachingMalloc 的相对优势仍然保持稳定。

11.5 Batch 大小扫描#

测试条件：64 B、24 线程、每线程 1,000,000 pair。

batch 从 1 增加到 64 时，ThreadCachingMalloc 的优势持续扩大，在 batch=64 达到 13.2560×。之后加速比逐渐下降，在 batch=2048 时出现第二个性能反转，ThreadCachingMalloc 仅为 malloc 的 0.6839×。

该异常与 16 KiB 异常相比稳定性较低。ThreadCachingMalloc 五次耗时范围为 0.128060～0.283538 s，而 malloc 仅为 0.109726～0.115312 s。这表明 batch=2048 下不仅平均性能下降，运行波动也明显增大。

64 B 对象本身非常适合本地缓存，但单轮同时持有 2048 个对象会显著放大 refill、FreeList 容量演化以及共享层访问。一旦本地容量没有及时增长到足够水平，大 batch 会在短时间制造集中 refill 或回收，进而增加 Center Cache 和 Page Cache 的同步开销。因此当前统一的 1.1x + 1 慢启动策略并不是所有 batch 下的最优参数。

11.6 每线程操作次数扫描#

每线程 pair 数从 100,000 增加到 10,000,000 时，ThreadCachingMalloc 的加速比保持在约 9.11×～11.21×。测试持续时间增加并没有导致优势快速衰减，说明在固定 64 B、24 线程、batch=256 的配置下，该方案具有较稳定的稳态性能。

11.7 混合工作负载#

6 组 mixed case 全部由 ThreadCachingMalloc 获胜，加速比范围为 6.2839×～12.5401×。其中最关键的是 16 KiB、batch=32 的 12.5401× 结果，它与对象大小扫描中的 16 KiB、batch=64 形成对照，进一步证明性能异常取决于对象规格与缓存阈值、batch 之间的组合，而不是仅由对象大小决定。

12.1 热路径无锁#

本地 FreeList 命中时，分配近似为：

1
读取链表头
2
→ 链表头移动到 next
3
→ 返回旧链表头

释放近似为：

1
写入 next
2
→ 更新链表头

不需要 Center Cache 锁，也不需要 Page Cache 锁，更不需要系统页申请。

12.2 批量跨层转移#

Thread Cache miss 后一次从 Center Cache 获取多个对象，而不是每次只取一个。Center Cache 获得 Span 后也一次完成整段对象切分。共享层的单次成本能够被后续多次本地分配摊薄。

12.3 Center Cache 分桶锁#

208 个 size class 各自有独立 mutex，因此 64 B 和 1 KiB 等不同规格的线程不会竞争同一把 Center Cache 锁。这比单一全局中心锁具有更好的并发性。

12.4 Page Cache 复用系统页#

Page Cache 不会在每个小对象申请时调用 VirtualAlloc。系统级内存先以较大连续 Span 的形式进入页缓存，再被切分给 Center Cache。释放后的 Span 也可以保留并用于后续请求。

12.5 相邻 Span 合并#

空闲 Span 回到 Page Cache 后尝试与地址相邻的 Span 合并，从而降低连续内存被切碎后的外部碎片，提高大 Span 被缓存命中的机会。

13.1 ThreadCacheFree 依赖 size 参数#

当前接口为：

1
ThreadCacheFree(ptr, size);

而标准 free(ptr) 不要求调用者重复提供申请大小。如果传入错误 size，指针可能被放入错误的 size class，破坏分配器内部状态。

更完整的实现可以在 Span 中保存 bucketIndex/objectSize，释放时通过地址定位 Span 后自动获取规格。

13.2 Page Cache 全局锁粒度较大#

Page Cache 的 Span 桶、页号映射和单例访问都受同一 _mtx 影响。虽然高频 Thread Cache 命中路径不访问它，但当对象集中回收到 Center Cache 时，每个对象都可能调用 MapSpanIDToSpanPtr，导致全局锁迅速成为串行点。

16 KiB、batch=64 的结果已经显示了这一问题的实际影响。

13.3 页号映射采用 unordered_map#

unordered_map<PAGE_ID, Span*> 实现简单，平均查找复杂度较低，但每次访问涉及哈希计算、桶访问和额外的动态结构元数据。在内存分配器这种极端高频路径中，即使平均 O(1) 也不代表常数开销足够小。

本文实验版本仍采用该方案，因此性能结论应与该数据结构绑定。

13.4 Span 元数据直接 new/delete#

Page Cache 拆分、合并和大对象处理过程中会直接创建或销毁 Span 元数据。虽然它并不位于最常见的 Thread Cache 命中路径，但共享层活动增多时，元数据本身的动态分配也会形成额外开销。

13.5 单例获取仍包含互斥操作#

Center Cache 和 Page Cache 的当前实例获取路径均包含锁操作。虽然通常不在每次本地命中中出现，但从工程角度仍可以使用 C++11 以后线程安全的函数局部静态对象进一步简化。

13.6 Benchmark 的适用范围#

当前 workload 主要是：

1
批量申请 → 写首字节 → 批量释放

它非常适合衡量分配器的稳态 alloc/free 能力，但不能完全覆盖真实程序。真实应用还可能包含随机对象大小、长短生命周期混合、跨线程释放、随机释放顺序和长期碎片积累。因此本文所有性能结论均限定为“在本文 benchmark 条件下”。