容量感知的线程缓存批量增长策略#

摘要#

线程缓存分配器通过批量搬移空闲对象减少中心缓存访问，但批量上限与底层 Span 页数若独立计算，会产生跨层不可行请求。本文分析一个包含 208 个尺寸类的 C++ 线程缓存分配器。现有策略先将批量数翻倍，再按 256 KiB 字节预算和 1024 个对象上限裁剪；Span 页数则由对象大小、请求数与 4 KiB 页的最小公倍数决定，并在结果超过 256 页时退回到最小整页倍数。虽然裁剪前的批量序列为二的幂，裁剪后的终值可以是任意整数，因此 Span 实际容量可能小于请求数。

本文提出容量感知的终止增长策略，仅在终值裁剪时检验 Span 容量，若候选批量不可满足则保留上一批量。我们建立保留对象来源和 Span 身份的离散事件模型，覆盖 5 类负载、240 组参数和 10 个配对随机种子，共 12000 次运行。模型在每个采样点验证已提交字节等于存活尺寸类字节与缓存字节之和。

全尺寸类枚举发现，现有策略在 80 个尺寸类出现终止欠填充，容量感知策略将其降为 0。在三个普通随机负载中，新策略与现有策略的运行轨迹和全部报告指标一致。在 384 字节饱和负载中，慢路径调用下降 91.11%，配对 95% 置信区间为 90.99% 至 91.22%，短取数归零，平均缓存增加 2.18 MiB。结果支持保留二倍增长、2n 回收阈值、256 KiB 字节预算和 1024 对象上限，并在终值裁剪处增加容量检查。本文结果是结构性性能证据，最终吞吐量和尾延迟仍需真实机器基准确认。

关键词： 线程缓存；内存分配器；批量增长；尺寸类；离散事件仿真；容量约束

Abstract#

Thread-caching allocators move free objects in batches to reduce synchronized accesses to a central cache. This paper studies a cross-layer failure that occurs when the batch limit and the backing Span geometry are computed independently. The examined C++ allocator doubles a per-class batch size and clips it by a 256 KiB byte budget and a 1,024-object cap. Span pages are derived from the least common multiple of object bytes and the 4 KiB page size, with a fallback when the request exceeds 256 pages. The pre-clipping batch sequence contains powers of two, but the clipped terminal value need not; the fallback Span may therefore contain fewer objects than requested.

We propose a capacity-aware terminal guard that accepts the clipped candidate only when its computed Span can satisfy the batch. A trace-paired discrete-event model evaluates 208 size classes, 240 parameter configurations, five workloads, and ten seeds per cell, totaling 12,000 runs. The current policy underfills 80 classes, whereas the guard eliminates all terminal underfills. It is observationally identical to the current policy in three ordinary random workloads. For a saturated 384-byte class, it reduces slow-path calls by 91.11% with a paired 95% confidence interval of 90.99% to 91.22%, eliminates short fetches, and increases mean cached memory by 2.18 MiB. The evidence supports retaining 2x growth, a 2n return threshold, a 256 KiB budget, and a 1,024-object cap while adding the guard only at terminal clipping. Because the model does not measure execution time or contention, wall-clock validation remains necessary.

Keywords: thread cache; memory allocator; batch growth; size class; discrete-event simulation; capacity constraint

1 引言#

通用内存分配器同时追求低延迟、高并发和低内存占用。这三个目标彼此制约。线程本地空闲链表可以使多数小对象申请和释放避开共享锁，但空闲链表过小会频繁访问中心缓存，过大又会让空闲对象长期滞留。Wilson 等人的综述指出，分配器的策略选择通常比单一机制更重要，并警告只使用随机且相互独立的请求假设会遗漏真实程序中的规律性[1]。这一判断对线程缓存尤其重要，因为批量增长、回收阈值、尺寸类和页分配策略共同决定慢路径频率与缓存占用。

本文研究的代码采用三层结构。ThreadCache 按尺寸类维护每线程空闲链表；CenterCache 按尺寸类管理 Span；PageCache 以 4 KiB 页和最多 256 页的连续 Span 为单位向下层供给内存。ThreadCache 的单次申请数初值为 1，每次缺货后翻倍。该设计看似天然保持二的幂，但代码随后执行上限裁剪，终止值可能不再是二的幂。如果终止值触发页数计算的回退分支，新 Span 的对象容量就可能远小于请求批量，从而让一次批量补给退化为短取数，并把线程反复送回慢路径。

本文的核心结论是：最高性价比的改动不是重写增长函数，也不是把所有终止值强制取二的幂，而是在终值裁剪处检查底层 Span 是否装得下候选批量。该检查只在增长阶段发生，或者可以按尺寸类预计算，不进入对象申请的正常快路径。实验支持保留现有二倍增长、2n 回收阈值、256 KiB 字节预算和 1024 对象上限。

本文贡献如下：

• 形式化批量增长与 Span 页数之间的可行性约束，解释二的幂增长为何仍会在终值裁剪后产生欠填充。
• 提出容量感知的终止增长策略。该策略在候选批量可满足时保持现有行为，在不可满足时保留上一批量。
• 实现可复现的离散事件模型，覆盖 208 个尺寸类、240 组参数、5 类负载和 12000 次运行，并在每个采样点验证内存守恒。
• 使用相同随机轨迹进行配对比较，给出置信区间、Holm 校正后的显著性结果和配对效应量，同时明确模型不能替代真实计时基准。

2 研究背景与相关工作#

3 问题形式化#

4 容量感知策略#

1
candidate = min(2 * n, L(S))
2
if candidate < 2 * n and Q(S, candidate) < candidate:
3
    next = n
4
else:
5
    next = candidate

5 实验方法#

6 实验结果#

6.1 全尺寸类几何#

在 208 个尺寸类上穷举终止请求后，当前裁剪策略有 80 个尺寸类出现 $Q(S,n)<n$。容量感知策略和无条件二次幂停止策略均为 0 个。图 1 给出当前终止批量容量比和容量感知结果。容量比低于 1 的红点对应新 Span 无法满足请求；容量感知策略只在这些终值拒绝裁剪结果。

图 1 208 个尺寸类的终止批量与 Span 容量比

6.3 欠填充负载#

负载	当前慢路径	容量感知慢路径	配对变化	当前缓存 MiB	容量感知缓存 MiB	短取数 当前到新
均匀原始	14,797.3	14,797.3	0.00%	295.72	295.72	6,967.8 → 6,967.8
均匀尺寸类	4,901.9	4,901.9	0.00%	305.50	305.50	478.9 → 478.9
八二热点	4,636.8	4,636.8	0.00%	214.26	214.26	821.9 → 821.9
欠填充热点	3,139.2	3,127.7	−0.37%	19.39	19.62	162.0 → 126.4
384 字节	1,148.0	102.1	−91.11%	1.34	3.52	1,124.0 → 0.0

表 1 主配置下当前策略与容量感知策略

欠填充热点中，容量感知策略把平均慢路径从 3139.2 降至 3127.7，配对下降 0.366%，95% 置信区间为 0.280% 至 0.452%；短取数下降 21.93%，平均缓存增加 0.227 MiB。虽然慢路径降幅有限，但它说明针对多个欠填充类的检查方向一致，没有把问题转移到其他尺寸类。

384 字节饱和负载呈现清晰的机制效应。慢路径从 1148.0 降至 102.1，配对下降 91.11%，95% 置信区间为 90.99% 至 91.22%；Holm 校正后 $p=3.66\times10^{-18}$，Cohen $d_z=-84.50$。短取数从 1124.0 降至 0。代价是平均缓存从 1.34 MiB 增至 3.52 MiB，绝对增加 2.18 MiB；最终已提交内存增加 2.60 MiB。极大 $d_z$ 来自十条配对轨迹都产生近乎相同的计数差，不表示真实运行时间会提高同样倍数。

图 2 相对当前裁剪策略的配对变化

6.4 策略消融#

无条件二次幂停止同样修复 384 字节反例，但它在普通负载中过早停止增长。相对当前策略，均匀原始大小、均匀尺寸类和八二热点的慢路径分别增加 3.93%、1.14% 和 3.76%，平均缓存仅分别减少 1.02%、1.22% 和 0.80%。这些差异在配对检验中均显著，但工程含义更重要：为了节省不到 1.3% 的平均缓存，无条件停止把普通路径推回中心缓存的次数提高到约 1% 至 4%。容量感知策略避免了这项普遍代价。

图 3 384 字节饱和负载的 240 组参数搜索空间

6.5 回收阈值#

回收阈值控制另一个独立权衡。当前代码在空闲链表达到 $2n$ 时向 CenterCache 返回 $n$ 个对象。将阈值提高到 $3n$ 可以保留更多线程本地对象，因而在三个普通负载中进一步降低慢路径，但增加平均缓存。将阈值降为 $1.5n$ 则明显增加往返搬移。

负载	$1.5n$ 慢路径	$2n$ 慢路径	$3n$ 慢路径	$1.5n$ 缓存 MiB	$2n$ 缓存 MiB	$3n$ 缓存 MiB
均匀原始	22,221.0	14,797.3	8,448.5	241.5	295.7	374.7
均匀尺寸类	8,472.5	4,901.9	4,404.4	249.5	305.5	340.9
八二热点	5,609.3	4,636.8	3,948.2	208.7	214.3	224.6

表 2 当前增长策略下不同回收阈值的均值

以 $3n$ 替代 $2n$ 时，均匀原始大小的慢路径减少 42.90%，但平均缓存增加 79.03 MiB；均匀尺寸类的慢路径减少 10.15%，缓存增加 35.42 MiB；八二热点的慢路径减少 14.85%，缓存增加 10.38 MiB。没有业务侧的内存价格或延迟预算时，不能把这些指标压成唯一标量最优。

本文选择 $2n$，是因为它保留了明显的缓存上界，并避免 $1.5n$ 的高频往返；若部署目标把慢路径成本置于内存占用之上，$3n$ 可以作为单独的性能档。

图 4 回收阈值的慢路径与平均缓存权衡

7 讨论#

8 有效性威胁#

内部有效性。 模型逐 Span 记录对象来源，并用式 6 检查所有采样点，降低了重复计数和丢失对象的风险。源代码快照与生成文件均有 SHA-256 清单。但模型仍是独立实现，可能共同复现了对源代码的误解。后续应使用真实分配器的事件日志对照每个尺寸类的申请数、返回数和 Span 页数。

构念有效性。 慢路径、搬移对象数和短取数是同步压力的代理，不是 CPU 周期。平均缓存字节也不等于进程 RSS，因为操作系统提交、虚拟地址保留和页驻留未被建模。本文因此不报告模拟吞吐率。

外部有效性。 五类合成负载覆盖均匀、热点和针对性饱和场景，但不代表数据库、游戏服务器、编译器或浏览器的完整分配轨迹。请求范围限于 256 KiB 以下的 ThreadCache 路径，也没有模拟 NUMA、不同页大小和线程调度。

统计结论有效性。 每个单元只有 10 次重复，$t$ 区间对差值分布有近似要求。固定配对轨迹降低了噪声，也使 $d_z$ 在确定性强的负载中非常大。Holm 校正控制了同一指标跨五负载的多重检验，但没有把整个 240 组参数搜索解释为确认性假设检验。

9 结论#

线程缓存的批量增长不能只看申请数序列。即使申请数从 1 开始并按二倍增长，min 上限裁剪仍会生成任意整数终值；当该终值与 Span 页数回退组合时，新 Span 可能只能返回请求批量的一小部分。本文在 208 个尺寸类中发现 80 个终止欠填充类，并用 12000 次离散事件运行验证容量感知终止检查。

实验结果支持一项局部且可解释的改动：保留二倍增长、2n 回收阈值、256 KiB 字节预算和 1024 对象上限，只在终值裁剪时拒绝容量不足的候选。该策略在普通随机负载中不改变轨迹，在 384 字节饱和负载中把慢路径减少 91.11% 并消除短取数，代价是平均缓存增加 2.18 MiB。下一步应把该策略实现为预计算表，并以真实多线程计时、锁等待和 RSS 指标完成外部验证。

数据与复现材料#

• 离散事件模拟器：allocator_model.cc
• 模型与复现说明：README.md
• 运行级数据：model_runs.csv
• 汇总数据：model_summary.csv
• 尺寸类几何：bucket_geometry.csv
• 主数据工作簿：allocator_model_paper.xlsx
• 配对统计结果：paired_comparison.csv
• 论文文件哈希：manifest.sha256

model_runs.csv 含 12000 行运行记录，model_summary.csv 含 1200 行配置负载汇总，bucket_geometry.csv 含 208 个尺寸类。实验可使用 Visual Studio 2022 的 C++17 编译器重新生成；随机种子、预热次数、测量次数和并行作业参数均在复现说明中记录。

参考文献#

1. Wilson P R, Johnstone M S, Neely M, Boles D. Dynamic Storage Allocation: A Survey and Critical Review. International Workshop on Memory Management, 1995. https://www.cs.hmc.edu/~oneill/gc-library/Wilson-Alloc-Survey-1995.pdf
2. Berger E D, McKinley K S, Blumofe R D, Wilson P R. Hoard: A Scalable Memory Allocator for Multithreaded Applications. ASPLOS IX, 2000, 117–128. DOI: 10.1145/378993.379232. https://people.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf
3. Evans J. A Scalable Concurrent malloc(3) Implementation for FreeBSD. BSDCan, 2006. https://papers.freebsd.org/2006/bsdcan/evans-jemalloc/
4. Google. TCMalloc Design. Accessed 4 September 2026. https://google.github.io/tcmalloc/design.html
5. Google. Performance Tuning TCMalloc. Accessed 4 September 2026. https://google.github.io/tcmalloc/tuning.html
6. Leijen D, Zorn B, de Moura L. Mimalloc: Free List Sharding in Action. APLAS 2019, 244–265. DOI: 10.1007/978-3-030-34175-6_13. https://www.microsoft.com/en-us/research/publication/mimalloc-free-list-sharding-in-action/
7. Liétar P, Butler T, Clebsch S, et al. snmalloc: A Message Passing Allocator. ISMM 2019, 122–135. DOI: 10.1145/3315573.3329980. https://www.microsoft.com/en-us/research/wp-content/uploads/2020/04/snmalloc.pdf
8. Holm S. A Simple Sequentially Rejective Multiple Test Procedure. Scandinavian Journal of Statistics, 1979, 6(2), 65–70. DOI: 10.2307/4615733. https://www.ime.usp.br/~abe/lista/pdf4R8xPVzCnX.pdf
9. Cohen J. Statistical Power Analysis for the Behavioral Sciences. Second edition. Lawrence Erlbaum Associates, 1988. https://www.routledge.com/Statistical-Power-Analysisfor-the-Behavioral-Sciences/Cohen/p/book/9780805802832

附录 A 关键实现关系#

离散事件模型对应的源代码关系如下：

• ThreadCache.hpp 的释放路径在空闲链表达到 2n 时调用回收。
• ThreadCache.hpp 的缺货路径把单次申请数乘 2，再用对齐尺寸 $S$ 的 LimitApplyNum 结果裁剪。
• CenterCache.hpp 每次普通回收恰好取 $n$ 个对象，并按对象所属 Span 归还。
• Common.hpp 的 IndexToPageNums 计算式 3 和式 4，LimitApplyNum 实现式 1。
• PageCache.hpp 使用 256 页系统块、最小充分空闲 Span、尾部分割与相邻合并。

建议新增的生产断言是：当 ThreadCache 更新单次申请数后，对应 IndexToPageNums 生成的 Span 容量不得小于申请数。若使用预计算表，应在构建期或单元测试中枚举全部 208 个尺寸类，并在页面大小、尺寸类边界、PageMaxContinuousNums、字节预算或对象上限改变时重新生成。