无锁并发队列的尾延迟归因：以缓存行隔离受控实验测定伪共享在异构多核笔记本上对 p99.9 延迟的贡献份额

1 · 研究问题

在现代异构多核（heterogeneous / hybrid core，如性能核 P-core 与能效核 E-core 混合）笔记本 CPU 上，若干开源无锁（lock-free）并发队列实现的入队–出队延迟尾部（p99、p99.9），有多大比例可归因于伪共享（false sharing）？把生产者索引与消费者索引做缓存行隔离（padding）这一单一改动，对尾延迟的改善幅度能否由"生产者与消费者所在核之间的拓扑距离"（同一物理核的两个超线程 / 同一 L2 簇内的两核 / 跨簇 / 跨核类型）单调预测？

2 · 研究背景与空白

技术背景。 无锁队列用原子读改写指令（compare-and-swap、fetch-and-add）代替互斥锁，让多个线程并发入队出队而不阻塞。它的性能上限不由指令数决定，而由缓存一致性协议的消息往返决定：当生产者写头指针、消费者写尾指针，若两者落在同一条 64 字节缓存行内，每次写都会使对方核上的这条行失效，触发一次跨核的所有权转移——这就是伪共享。伪共享不改变平均吞吐太多，但会把延迟分布的尾部拉长若干倍，而尾延迟才是实时与交易类系统真正关心的量。已有工程报告显示：在严格核绑定条件下，一个生产级无锁队列因微架构伪共享出现约 3.1 倍的性能塌陷，用 128 字节空间隔离加影子变量批处理可以打破该瓶颈；同核双线程通信延迟最低，跨核后延迟增加 3 倍以上，跨 CCX（core complex）或跨插槽进一步增加。这类课题对纯 CPU 笔记本是最优匹配：它测的是多核之间的缓存一致性行为，一台八核笔记本与一台六十四核服务器在"两核之间的一次往返要多少周期"这个基本量上是同等可测的；而且笔记本上的异构核心结构反而提供了服务器上没有的自变量维度。

已有工作到哪一步。 学术侧有针对多核通信 API 的无锁算法性能影响研究（arXiv:1401.6100）与近期的免协调无锁队列工作（arXiv:2511.09410）；工程侧有成体系的无锁队列基准（max0x7ba/atomic_queue 提供吞吐与延迟基准与公开数据、psy-lob-saw 系列的队列分析、多篇对阻塞与无锁队列的对比测评）。这些工作的共同特征是：（a）主要在同构服务器 CPU上测量；（b）主要报告吞吐量与平均延迟，尾延迟即使给出也很少做分布形态分析；（c）把伪共享当作已知的设计注意事项（"要加 padding"），而不是当作一个被定量归因的自变量。

空白在于：没有公开工作把"缓存行隔离"作为受控变量、在异构核心拓扑上系统测量它对延迟分布尾部的贡献份额。这个空白同时占了两个可靠类型——换样本（异构核心是 2021 年后才普及的新硬件类别）与评价维度转换（从吞吐/均值转到尾部分位数与分布形态）。它对学生课题极友好：受控实验设计简单（改一个 alignas 就是全部处理组差异）、算力零门槛、且结论正负都成立。

3 · 可检验假设

• H1：移除缓存行隔离后，p99.9 延迟的中位增幅 ≥ 2.0 倍，而中位延迟（p50）的增幅 ≤ 1.3 倍——即伪共享的代价主要落在分布尾部而非中心。若 p50 与 p99.9 的增幅比值接近 1，H1 被否证，说明伪共享是均匀抬升而非尾部效应。
• H2：隔离带来的 p99.9 改善幅度随生产者–消费者核对的拓扑距离单调不减：同物理核超线程对 < 同簇不同核 < 跨簇同类型核 < 跨核类型（P↔E）。判据为 4 档拓扑上的 Jonckheere–Terpstra 趋势检验 p < 0.05。若在跨 P/E 核这一档出现反转，则说明异构调度的频率差异盖过了一致性效应——这是对异构 CPU 上并发设计的一条独立发现，同样有效。

4 · 量化验收标准

1. 方法学校验（硬门槛）：用自建基准骨架重现 atomic_queue 项目公开发布的吞吐与延迟基准结果。因跨硬件绝对值不可比，判据定为两条同时满足：（a）在本机上各队列实现的相对排序与官方公布结果一致；（b）"同物理核两超线程之间一次乒乓往返（ping-pong round trip）的延迟"这一硬件基本量，与用独立的最小化 std::atomic 乒乓程序测得的值偏差 ≤ 10%。这一步不过关，说明计时或绑核有系统误差，后续全部结论无效。
2. 正确性门槛（第二道硬门槛）：任何被测队列（含自行修改 padding 的版本）必须先通过线性一致性抽查——记录带时间戳的入队/出队操作历史，用暴力搜索验证存在一个合法的顺序化重排（历史长度 ≤ 12 时可穷举），至少 1000 条随机历史全部通过。修改过的实现若未通过此检验，其性能数据一律作废。
3. 基准测试方法学：每个（队列 × padding 条件 × 核对 × 负载强度）组合独立重复 ≥ 30 次，每次记录 ≥ 10⁶ 次操作的逐次延迟（不做在线聚合，保留全分布）；固定 CPU 频率与调度策略（taskset 绑核 + chrt 实时优先级，需核实笔记本 OS 上是否可用）、禁用节能与 Turbo、每次运行前预热 ≥ 2 秒并丢弃预热段；报 p50 / p90 / p99 / p99.9 与 IQR，明确写明不报均值与标准差（延迟分布重尾，均值无代表性）；组间比较用 Mann–Whitney U 与分位数自助法置信区间。
4. 温度与频率漂移控制：全程记录 CPU 温度与实际频率（powermetrics / turbostat / /proc/cpuinfo），每轮运行之间强制冷却间隔；若某轮的频率中位数偏离基线 > 5%，该轮数据标记并在敏感性分析中剔除，剔除比例须报告。这一条是笔记本平台特有的必需项，必须写进正文。
5. 双成本口径：与已发表实现对照时同时报等工作量（相同操作条数下的延迟分布）与等墙钟时间预算（固定 10 秒内完成的操作数及其延迟分布），两种口径都要给出。
6. 可复现性：全部队列源码（含改动 diff）、基准骨架、绑核脚本、原始逐次延迟数据（压缩后 CSV/二进制）、分析与绘图脚本开源；一键重跑脚本；随机种子与核对映射写死在配置中；硬件与 OS 版本、微码版本完整披露。

5 · 数据与工具

用途	来源 / 工具
队列实现（对照基准）	max0x7ba/atomic_queue（C++14，header-only，含官方基准与公开结果）；cameron314/concurrentqueue（moodycamel MPMC）；boost::lockfree::queue（Boost 提供）；一个自行实现的 Michael–Scott 队列与一个 Lamport SPSC 环形缓冲（作为教科书基线）。外部实现仅用于校验与对比，不计入本项目贡献
拓扑发现	hwloc / lstopo（识别物理核、超线程兄弟、L2/L3 共享关系）；Linux /sys/devices/system/cpu/*/topology；异构核心的类型识别需查 OS 特定接口（Apple Silicon 上的 P/E 核绑定 API 与 Linux 上的 cpu_capacity 均需核实）
计时	rdtsc/rdtscp（x86）或 cntvct_el0（ARM），须先校准计数器频率并验证跨核一致性（非常关键：跨核 TSC 是否同步需实测确认，不同步则单向延迟不可测，只能测往返延迟）
微架构计数器	Linux perf（cache-misses、mem_load_l3_miss、HITM 事件是伪共享的直接证据，HITM 事件在消费级笔记本上是否可用需核实）；perf c2c（专为伪共享设计的分析工具，若可用则是最强证据）
线性一致性检验	自行实现的小规模穷举检验器（历史长度 ≤ 12）；可参考 Herlihy–Wing 线性一致性定义
统计与作图	Python + SciPy（Mann–Whitney、Jonckheere–Terpstra 趋势检验）+ Matplotlib（延迟分布的互补累积分布函数 CCDF 图，对数纵轴）
算力	纯 CPU，内存需求 < 1 GB。总工作量约 5 队列 × 2 padding × 4 核对 × 3 负载 × 30 重复 × 数秒 ≈ 10–20 机时，可分夜跑。超出范围：NUMA 效应、跨插槽通信、大规模线程数（> 物理核数）不在本课题范围，须在正文明确声明

6 · 方法路径

1. 装环境与工具链，编译各队列实现，跑通 atomic_queue 自带基准；用 lstopo 画出本机拓扑图并写入正文；实测 TSC 跨核同步性与频率校准。
2. 核实工具能力边界（本课题风险最集中的一步）：perf c2c 与 HITM 事件是否可用；实时调度优先级是否可设；异构核心的显式绑定 API 是否存在。任一不可用都要在此步写明替代方案，不得边做边发现。
3. 实现基准骨架：绑核、预热、逐次延迟记录（用预分配数组避免测量本身引入分配）、温度/频率监控、防编译器优化屏障；用最小化乒乓程序完成验收第 1 条的硬件基本量校验。
4. 制备处理组：对每个队列产出"有缓存行隔离"与"无缓存行隔离"两个版本（改动限于 alignas/padding 字段，diff 必须最小且公开），逐一通过线性一致性抽查。
5. 执行主扫描（队列 × padding × 4 档核对 × 3 档负载强度 × 30 重复），同步采集 perf 计数器与温度/频率日志。
6. 分析：CCDF 图、分位数表（p50/p90/p99/p99.9 + 自助法置信区间）、H1 的尾/中心增幅比、H2 的拓扑趋势检验、双成本口径对照表；剔除频率漂移轮次并报告敏感性。
7. 独立交叉校验：（a）用 perf c2c 或 HITM 计数直接验证"无隔离版本的缓存行竞争确实更高"，把性能证据与微架构证据对上；（b）在另一台不同架构的机器（同学的 Intel/AMD/Apple Silicon 笔记本）上重跑关键组合，检验拓扑趋势是否跨架构成立。

7 · 新颖性边界

本课题不声称：不提出新的无锁队列算法，不声称任何队列实现更优，不声称"应该加 padding"这一工程常识是本项目发现（它是众所周知的）。atomic_queue、moodycamel、Boost.Lockfree 与全部微架构工具均为他人工作，标注为对照基准，不计入本项目贡献。

已有工作完成了什么：学术侧已给出无锁算法对多核通信 API 性能的影响（arXiv:1401.6100）与新的免协调无锁队列设计（arXiv:2511.09410）；工程侧的公开基准给出了各队列在同构服务器 CPU 上的吞吐与平均延迟排名，并有报告指出严格 NUMA 绑核下伪共享可造成约 3.1 倍的性能塌陷、128 字节隔离可打破该瓶颈，以及跨核通信延迟比同核高 3 倍以上这一量级。这些结论本项目引用而不重复声称。

本项目的贡献：把伪共享从"设计注意事项"变成受控自变量，在异构核心笔记本 CPU这一新硬件类别上，定量给出它对延迟分布尾部（p99.9）的贡献份额，并检验该份额是否随核间拓扑距离单调变化。主结论是这份"尾延迟归因表"与拓扑趋势判定，不是任何新实现。

为什么有价值：异构核心已是消费级与移动端 CPU 的标配，而并发数据结构的性能经验几乎全部来自同构服务器。若拓扑趋势成立，它给出一条可操作的线程放置建议；若在 P↔E 核这一档反转，则说明异构平台上的并发调优需要与服务器完全不同的直觉。

风险提示：笔记本平台的噪声（温度节流、后台进程、OS 调度）是本课题最大的效度威胁。若剔除频率漂移后剩余样本不足或组间差异落在噪声内，"无法分辨"必须如实报告，并给出分位数自助法置信区间证明所需样本量——不得用增加重复次数以外的方式凑显著性。

8 · 决策门槛（go / no-go）

• 第 5 周：计时基础设施门槛。若 TSC 跨核不同步或频率无法锁定，降级路径 A：全部改测往返延迟（ping-pong，只需单核时钟）而非单向延迟，并把负载模型从"生产者持续推、消费者持续拉"改为"配对请求–应答"。主结论框架（伪共享对尾部的贡献 × 拓扑距离）完全保留，仅测量语义从单向改为往返，须在正文声明。
• 第 8 周：微架构证据可用性必须核实完毕。若 perf c2c/HITM 不可用，降级路径 B：改用"缓存缺失总数 + 受控消融"作为间接证据——即用一个刻意制造伪共享的合成微基准（两个线程反复写同一/不同缓存行）标定本机上伪共享的延迟代价上界，再以该标定值解释队列上的观测。此路径的证据强度略低但完整自洽，主结论不变。
• 第 12 周：正确性门槛。若自行修改 padding 的版本无法通过线性一致性抽查，降级路径 C：放弃修改第三方实现，改为只在自行实现的 Michael–Scott 队列与 SPSC 环形缓冲上做 padding 消融（自己的代码可控），第三方实现只作为"当前工程实践的参照点"以原样参与横向比较。主结论框架保留。
• 第 24 周：主扫描完成且 H1 有明确判定。若噪声导致数据大量作废（作废率 > 40%），降级路径 D：缩减到 2 个队列 × 2 档拓扑（同核超线程 vs 跨核类型，即差异最大的两档），把节省的时间全部投入重复次数（提到 100 次）与冷却间隔。宁可减少条件数也不减少重复次数——本课题的全部价值建立在能否从噪声中分辨出效应。
• 预算裁剪顺序：负载强度档数 → 队列实现数量（下限 2）→ 拓扑档数（下限 2）→ （绝不裁剪）重复次数、频率控制与线性一致性检验。
• 选择前提：仅在学生已能写 C++ 多线程代码、且明确接受"笔记本噪声可能导致效应无法分辨"这一风险时才启动。若学生的机器是单一同构核心的旧款 CPU，H2 无从检验，应改选 K01。

---