收紧共享元数据路径：RadixTree 与 ObjectPool 在 ThreadCachingMalloc 中的设计与实验#

2.1 从 64 位地址中剥离页内偏移#

当前实现的页大小为 4 KiB，因此：

1
inline constexpr size_t PAGE_SHIFT = 12;

对象地址右移 12 位即可得到 PAGE_ID。在 64 位构建中，可参与映射的位数为：

1
64 - PAGE_SHIFT = 52 bit

RadixTree 每层处理 9 bit，对应 512 个分支。52 bit 最终被拆成：

1
9 + 9 + 9 + 9 + 9 + 7 = 52

因此，一个页号最多经过六层即可到达叶子。Page Cache 中的类型定义为：

1
RadixTree<Span*, 8 * sizeof(PAGE_ID) - PAGE_SHIFT, 9>
2
    _pageIDtoSpanPtrHash;

这里保留了原成员名中的 Hash，但底层结构已经不再是哈希表。

2.2 逐层取位而不是计算哈希#

RadixTree 的核心操作是 Access。第一次进入时，代码先把 PAGE_ID 左移 12 位，恢复它在完整地址位宽中的位置；随后每层读取最高 9 bit 作为数组下标，再把剩余位左移交给下一层。

简化后的逻辑如下：

1
T* Access(PAGE_ID id, bool first, bool isCreate) {
2
    if (first) {
3
        id <<= PAGE_SHIFT;
4
    }
5

6
    if constexpr (AllBits <= LayerBits) {
7
        // 到达叶子，直接返回数组槽位
8
        return leaf_array + leaf_index;
9
    } else {
10
        // 取当前 9 bit，进入下一层
11
        return children[index].Access(id << LayerBits, false, isCreate);
12
    }
13
}

这条路径没有哈希函数，也没有“桶内再找节点”的第二阶段。只要树的相应分支已经建立，查找次数由位宽决定，而不是由元素数量决定。对于当前参数，它是固定的六层索引。

2.3 延迟创建与存在位图#

如果启动时直接建立完整的 52 位索引空间，内存开销显然无法接受。当前实现只在写入经过某个分支时才分配下一层数组：

1
if (_treeList == nullptr) {
2
    _treeList = new RadixTree<...>[1 << LayerBits];
3
}

叶子层也按需分配值数组，并使用 std::bitset 记录槽位是否存在。这样可以区分“没有映射”和“映射值恰好为空指针”，count/find/erase 也不需要额外的节点对象。

延迟创建对分配器的典型地址分布尤其有效。一次系统页申请会产生连续页号，这些页共享绝大部分高位前缀，只在靠近叶子的层级分叉。多个页的映射可以复用同一条上层路径，既减少结构分配，也提高查询时的局部性。

2.4 与 Page Cache 的结合#

Page Cache 在把 Span 交给上层时，会为 Span 覆盖的每一页写入映射：

1
for (size_t i = 0; i < span->pageNums; ++i) {
2
    _pageIDtoSpanPtrHash[span->id + i] = span;
3
}

对象释放时，地址先转换为页号，再通过同一个 RadixTree 找回 Span。Span 合并后，受影响页的映射也会指向合并后的 Span；大块 Span 归还操作系统时，对应页号则从树中擦除。

RadixTree 本身没有加锁。当前 Page Cache 仍然使用 _mtx 保护 Span 桶、页号映射和 ObjectPool。这项优化没有消除全局锁，而是尝试缩短锁内映射操作的执行时间。这样的改法侵入性较低，因为它不改变 Span 生命周期和现有同步边界。

3.1 为什么 Span 适合对象池#

Span 的大小固定，创建位置集中，生命周期也由 Page Cache 控制。拆分大 Span 时会产生新 Span，合并时会销毁被吸收的 Span，大对象直接申请和释放也会创建、回收 Span。与大小和生命周期不可预测的普通用户对象相比，这正是对象池容易发挥作用的场景。

ObjectPool 首先计算单个槽位大小：

1
_sizeofItem = std::max(sizeof(T), sizeof(void*));
2
_sizeofItem = AlignUp(_sizeofItem, sizeof(void*));

槽位至少能容纳一个指针，因为对象销毁后，槽位的首个机器字会被复用为空闲链表的 next 指针。空闲节点不需要额外分配链表结构。

3.2 慢路径按页扩容#

当空闲链表为空且当前内存块剩余空间不足时，ObjectPool 通过 SystemAllocPage 申请新页。基础页数由对象大小与页大小的最小公倍数决定：

1
_applyPageNums =
2
    std::lcm(_sizeofItem, 1 << PAGE_SHIFT) >> PAGE_SHIFT;

这样得到的内存块既是完整页，又能被固定大小槽位整齐切分。当前扩容级别从 5 开始，之后按 5、10、20、40……倍增长；实际申请页数是基础页数与该级别的乘积。这能减少对象池扩大后反复进入系统页申请的次数。

从新块分配对象时只需要移动游标：

1
T* obj = reinterpret_cast<T*>(_memory);
2
_memory += _sizeofItem;
3
_remainBytes -= _sizeofItem;
4
new (obj) T(std::forward<Args>(args)...);

这里的 placement new 只负责调用构造函数，不再为对象单独申请存储。

3.3 热路径是一次链表弹出或压入#

对象池已经拥有空闲槽位时，New 从侵入式链表头部弹出一个节点，然后在原地址重新构造 Span：

1
void* next = *reinterpret_cast<void**>(_freeList);
2
T* obj = static_cast<T*>(_freeList);
3
_freeList = next;
4
new (obj) T(args...);

Delete 则执行相反过程：

1
obj->~T();
2
*reinterpret_cast<void**>(obj) = _freeList;
3
_freeList = obj;

在稳定复用阶段，这条路径不调用通用 new/delete，也不产生独立链表节点。它把 Span 的“逻辑生命周期”和承载 Span 的“存储生命周期”分开：构造函数和析构函数仍然按次执行，底层槽位却可以长期循环使用。

3.4 为什么对象池仍放在 Page Cache 锁内#

当前 ObjectPool 没有内部互斥量。Page Cache 是它的唯一所有者，所有创建与回收操作都在 Page Cache _mtx 的同步范围内完成。这保持了较简单的所有权关系，也避免了对象池再嵌套一把锁。

代价是，ObjectPool 节省下来的时间主要体现为缩短 Page Cache 临界区，而不是让多个线程同时操作池。若未来拆分 Page Cache 锁，必须重新确认 ObjectPool 的同步方式，不能直接把当前实现当作线程安全组件使用。

5.1 环境与计时#

实验在第一版论文使用的同一台 Intel Core i7-13700K、32 GB 内存、Windows 10 64 位主机上运行。测试程序使用 MSVC 19.43.34810，Release x64、C++17、/O2、NDEBUG 编译，计时器为 std::chrono::steady_clock。

每个测试先预热，再正式执行 9 次并取中位数。每轮交替改变优化实现与基线实现的执行先后顺序，以降低温度、调度和缓存状态造成的固定顺序偏差。所有查找都通过校验和产生可观察结果，防止编译器删除循环。

完整程序见 benchmark_metadata_paths.cc，原始计时见 metadata_microbenchmark_raw.csv，汇总数据见 metadata_microbenchmark.csv。

5.2 页号映射实验#

映射表包含 131072 个有效页号，查询阶段执行 12000000 次保证命中的伪随机访问。基线 unordered_map 在插入前执行 reserve(131072)，避免因未预留容量而人为放大重哈希成本。查询使用 operator[]，与 Release 构建中 Page Cache 对已存在页号的实际访问方式一致。

实验设置两种地址布局：

• 连续页。 页号为 base + i，模拟一段或少量大段连续虚拟内存；
• 分段页。 每个区域包含 64 个连续页，相邻区域间隔 4096 页，模拟多个分散的系统页区域。

分段布局仍限制在合理的用户态地址范围内，没有把页号均匀撒满整个 52 位空间。后者会明显放大当前 RadixTree 的稀疏分支内存成本，却不符合这个分配器以连续页块为主的使用方式。

5.3 Span 对象池实验#

对象池实验维护 4096 个同时存活的 Span。每轮先构造 4096 个 Span，再全部销毁，共执行 1024 轮，即 4194304 个完整的“构造加销毁”周期。

优化组使用实际的 ObjectPool<Span>::New/Delete，基线使用 new Span/delete。正式计时前，ObjectPool 已经建立足以容纳 4096 个 Span 的空闲槽位，因此该实验测量的是设计目标中的稳定复用路径，不包含对象池首次 VirtualAlloc 的冷启动成本。

6.1 RadixTree 页号映射#

换算为单次操作后，连续页查询由 15.18 ns 降至 8.25 ns，分段页查询由 22.51 ns 降至 9.33 ns。连续页插入时，RadixTree 只需 6.60 ns/条；分段布局需要创建更多分支，插入成本上升到 12.36 ns/条，但仍低于 unordered_map 的 49.29 ns/条。

结果体现出两个特点。

第一，连续页共享高位前缀，RadixTree 可以复用已经建立的上层节点，因此插入收益最大。第二，分段布局下 unordered_map 的随机节点访问代价进一步上升，而 RadixTree 的查询深度仍然固定，所以查询加速比从 1.84 倍扩大到 2.41 倍。

不过，RadixTree 并没有把查询变成一次数组访问。当前 52 位配置仍需走六层，分段地址也会降低层级节点的缓存局部性。它的优势来自路径可预测、无需哈希节点，以及相邻页共享前缀，而不是“树一定比哈希表快”这样的普遍结论。

6.2 ObjectPool 元数据复用#

ObjectPool 的稳定复用路径相对直接 new/delete 快 7.76 倍。原因并不神秘：测试开始后，所需槽位已经存在，每次 New/Delete 只执行空闲链表操作、Span 构造和 Span 析构；基线则需要为每个生命周期进入通用堆分配与释放路径。

这项结果对 Page Cache 的意义不只是“Span 创建更快”。Span 创建、合并回收都发生在共享锁保护的元数据操作中。对象池缩短这些操作后，其他线程占用同一临界区的等待时间也可能下降。但本实验是单线程微基准，没有测量锁竞争，因此这里使用“可能”而不是直接宣称并发吞吐获得 7.76 倍提升。

7.1 它们证明了什么#

实验可以支持以下结论：

• 对当前页号位宽和典型连续页分布，RadixTree 的命中查询与插入都比预留容量后的 unordered_map 更快；
• 对预热后的固定大小 Span，侵入式 ObjectPool 显著降低了重复构造与销毁的存储管理成本；
• 两项改动分别针对映射和元数据存储，不依赖特定的上层工作负载即可独立验证。

7.2 它们不能证明什么#

实验不能直接证明整个 ThreadCachingMalloc 获得 1.84 倍、2.41 倍或 7.76 倍吞吐提升。真实分配路径还包含 Thread Cache 命中、Center Cache 分桶锁、FreeList 操作、Span 切分、内存触碰和操作系统页申请。若大部分请求始终命中 Thread Cache，页号映射和 Span 创建所占比例很低，端到端收益自然会小于微基准结果。

微基准也没有测量 RSS、缓存未命中、分支预测或锁等待时间。因此它更适合说明“被替换的机制本身更轻”，而不是完成全部性能归因。后续若要评估实际并发收益，应增加 Page Cache 进入次数、映射查询次数、锁持有时间和锁等待时间等内部计数器，并在相同工作负载下做逐项消融。

8.1 RadixTree 的空间成本和生命周期#

当前 RadixTree 延迟创建分支，但每次创建中间层时会一次分配 512 个子节点。连续页可以很好地共享这些节点，极度稀疏且遍布大地址空间的页号则可能消耗较多内存。本文的分段实验已经展示了更多分支会提高插入成本，但没有统计实际提交内存。

此外，当前类没有析构函数，erase 只清除叶子存在位，不回收叶子数组和中间节点。这与 Page Cache 进程级生命周期相符，也避免频繁收缩树，但它意味着树占用的峰值结构内存会保留到进程结束。若把该类用于可反复创建销毁的普通容器，就会发生内存泄漏。

operator[] 在路径不存在时会自动创建节点。Page Cache 在 Release 模式下依赖“查询页号必然已经登记”这一不变量；如果该不变量被破坏，查询可能悄悄创建空映射。更稳健的生产实现应让只读查询使用不会创建节点的 find，并把断言之外的错误处理保留下来。

8.2 ObjectPool 的通用性限制#

当前 ObjectPool 只把槽位对齐到指针宽度，没有按 alignof(T) 处理过度对齐类型。它用于当前 Span 没有问题，但还不能被无条件视为任意 C++ 类型的通用对象池。

对象池也没有记录并释放所有历史页块。对于与 Page Cache 同寿命的 Span 池，这是用内存保留换取后续复用速度的主动选择；若工作负载曾达到很高峰值后长期下降，池内存不会主动归还操作系统。

最后，ObjectPool 本身不是线程安全的，构造函数抛异常时的槽位恢复也没有单独处理。这些边界在当前 Page Cache 所有权和 Span 构造函数下尚可控制，但在扩大用途前需要补齐。

8.3 全局锁仍然存在#

RadixTree 和 ObjectPool 优化的是锁内工作量，并未改变 Page Cache 由一把全局 _mtx 串行化的事实。当线程缓存频繁回收对象时，真正的上限仍可能来自锁竞争。更进一步的优化可以考虑区分映射只读路径和 Span 结构修改路径，但必须先解决 Span 生命周期：读线程拿到 Span* 时，另一个线程不能同时合并并回收该 Span。

因此，下一步不应只是机械地把 mutex 换成 shared_mutex。需要先定义读者持有期、删除时机以及映射更新的一致性，再选择分段锁、读写锁、epoch 或其他方案。