优先级队列性能基线与并发压测
环境：Windows 11 ｜ i5-12400（6C/12T）｜ .NET 8.0.30 ｜ Workstation GC（2026-08-17 全量压测）； 单线程 BDN 为 short job。数字用于实现间横向对比，绝对值随硬件浮动。
复现：
# 单线程 BDN（short job） dotnet run --project benchmarks/TC.Tier.Core.Benchmarks -c Release -- --filter "*PriorityQueueBenchmarks*RoundTrip*" --job short # 并发吞吐矩阵 + 积压敏感性 + 并发正确性（独立计时探针） dotnet run --project benchmarks/TC.Tier.Core.Benchmarks -c Release -- --pq-probe dotnet run --project benchmarks/TC.Tier.Core.Benchmarks -c Debug -- --pq-probe correctness # DEBUG 链校验器 # 活性回归绊线 dotnet run --project benchmarks/TC.Tier.Core.Benchmarks -c Release -- --pq-wedge配套：API 语义与选型见 ../priority-queues.md。
1. 单线程混合往返（稳态积压 1024，均匀 8 级优先级）
| 实现 | Mean | Ratio | 分配/次 |
|---|---|---|---|
.NET 内置 PriorityQueue（非线程安全，参照） |
11.0 ns | 1.00 | 0 B |
BucketPriorityQueue（离散 8 桶） |
52.4 ns | 4.75 | 48 B |
SkipListPriorityQueue（任意 long） |
328.0 ns | 29.8 | 1376 B |
AsyncPriorityQueue（无锁 Route A） |
423.2 ns | 38.4 | 1256 B |
- Bucket 是并发队列里的性能之王：50~66 ns 对积压深度不敏感（出队扫桶 O(桶数)）——优先级能映射为 少量离散枚举时无条件选它。
- SkipList / Async 的差距是"任意优先级 + 线程安全"的代价——两者定位是优先级必须任意取值时的选择。
- 与内置 11 ns 对照不是"落后"，是线程安全的定价——单线程场景就该用内置。
2. 并发吞吐矩阵（混合往返 × 线程数，独立计时探针）
方法论：Thread 直起 + Barrier 对齐起跑 + Stopwatch 总时/总 ops；先探测轮（50K ops/线程，10s 护栏）
再 5 轮正式（200K/线程，60s 护栏）取中位。LockedHeap 对照基线 = 一把 lock + 内置 PriorityQueue
（四叉堆）+ 一项一许可信号量。
| 实现 | 1T ns/op | 2T ns/op | 4T ns/op | 8T ns/op | 8T 总吞吐 | 分配 B/op |
|---|---|---|---|---|---|---|
| Bucket | 151.6 | 232.4 | 193.0 | 231.4 | 34.6 Mops/s | 48.7 |
| LockedHeap（大锁+堆，对照） | 304.5 | 154.0 | 231.1 | 250.4 | 32.0 Mops/s | ~0 |
| Async | 466.7 | 615.2 | 539.9 | 635.7 | 12.6 Mops/s | 1264 |
| SkipList | 465.6 | 465.3 | 657.5 | 851.1 | 9.4 Mops/s | 92 |
- Bucket 近线性扩展（1T→8T ×5.2）：桶间天然分区，无队头热点。多消费者 + 离散优先级 = 无脑选它。
- 细粒度锁 vs 一把大锁（SkipList vs LockedHeap）——大锁领先 3.4×：优先队列负载的 DeleteMin 全打 队头、插入集中于少数优先级段——细粒度锁的"区间并行"收益趋零。吞吐优先的任意 long 场景， 自建"一把 lock + 内置 PriorityQueue"仍是最优解。
- SkipList 是健康可用的细分锁选项（8 线程 9.4 Mops/s、分配 92 B/op）：任意 long + 中低并发 +
零分配路径 + 无锁
TryPeek的定位，而非吞吐选择。 - Async 并发下无锁优势兑现（8 线程 12.6 Mops/s，ns/op 随线程数不升）：价值不是吞吐（大锁更高）， 是免疫持锁者延迟（§4.2）——但 Workstation GC 下分配尾巴抵消此优势（§4.3）。
2.1 超额订阅扩展（16/32/64 线程 @ 12 逻辑核，Server GC）
| 实现 | 8T Mops/s | 16T | 32T | 64T | 64T ns/op | 扩展形态 |
|---|---|---|---|---|---|---|
| Bucket | 37.6 | 72.4 | 148.2 | 292.8 | 219 | 完美线性（ns/op 不涨） |
| LockedHeap | 37.7 | 66.1 | 135.0 | 245.0 | 261 | 近线性（大锁未饱和） |
| Async | 16.7 | 32.6 | 65.5 | 128.1 | 500 | 线性（ns/op 平） |
| SkipList | 11.0 | 20.5 | 30.2 | 46.4 | 1379 | 亚线性（445→1379ns，3× 恶化） |
边界：超额订阅下吞吐超过"核数 × 单线程"是流水线效应（跨线程 Enqueue/TryDequeue 重叠），不代表 单核能力。超额订阅 ≠ 真高核：同核线程共享缓存，掩盖真 64 核下"64 个核抢一个锁字/CAS 目标的缓存 行乒乓"。本表结论：①扩展性分层 = 分区（Bucket）> 大锁 > 队头单点 CAS（Async）> 队头锁链（SkipList）； ②SkipList 的锁链在竞争压力下最先恶化；③**"无锁"属性本身不带来扩展性——热点是不是单点才带来**。
3. 积压深度敏感性（单线程 50K 往返实测）
负载 A：均匀 0..7（基准负载）｜负载 B：单一 P7 纯尾插（跳表高层索引压力负载）。
| 实现 | 负载 | 1K | 8K | 64K | 256K |
|---|---|---|---|---|---|
| LockedHeap（大锁+堆，对照） | A | 57 | 70 | 98 | 113 |
| LockedHeap（大锁+堆，对照） | B | 73 | 61 | 56 | 52 |
| Bucket | A | 175 | 58 | 117 | 436 |
| Bucket | B | 68 | 68 | 83 | 61 |
| SkipList | A | 462 | 438 | 667 | 870 |
| SkipList | B | 930 | 774 | 661 | 949 |
| Async | A | 986 | 1597 | 1884 | 2874 |
| Async | B | 954 | 868 | 1349 | 1255 |
- LockedHeap 全程最快且最稳（45~103ns）——单线程任意优先级场景它同样是正确答案（比 SkipList 快 5~10×）。
- Async 256K 积压仅 1.4~2.0 µs/op——健康的跳表对数增长（尾插也建高层索引）。
- Bucket 与积压无关（54~162ns 全程平）：大积压 + 离散优先级 = Bucket 主场。
- 优先级分布偏斜（如 99% 同级）对 Bucket 更有利；对 Async 中性偏正。
4. 真实负载维度——think-time 与持锁者延迟
§2/§3 是"背靠背纯内存操作"微基准：临界区 50ns 且从不被外部延迟——偏向大锁。本节补两个真实 维度：think-time（worker 出队→干活→回来）与毒丸（持锁线程被外部延迟）。
4.1 think-time 负载（8 线程，往返间自旋指数分布均值 50µs）
| 实现 | 总吞吐 ops/s | op p50 | op p99 | op p999 | op max |
|---|---|---|---|---|---|
| Bucket | 144,724 | 300 ns | 1.3 µs | 5.4 µs | 6,408 µs |
| LockedHeap（大锁+堆） | 143,366 | 200 ns | 800 ns | 2.0 µs | 606 µs |
| SkipList | 135,151 | 700 ns | 2.7 µs | 17.7 µs | 15,478 µs |
| Async | 130,029 | 600 ns | 3.2 µs | 53.6 µs | 21,900 µs |
- think-time 下大锁并不溃败——队列操作占比 <2% 时锁几乎无竞争，LockedHeap 与 Bucket 完全同级， 其 p50/max 甚至全场最优。§2"大锁吞吐王"延伸到低频真实负载依然成立。
- Async 的尾延迟被自身分配压力拖累（p999 53.6µs、max 21.9ms）：1.3 KB/op 的 Gen0 分配率在 Workstation GC 下制造毫秒级 GC 停顿——无锁 ≠ 低尾延迟，分配率才是尾延迟杀手。
4.2 持锁者毒丸（8 线程高频往返，0.2% 操作注入 2ms 延迟）
LockedHeap☠ 把 2ms 注入在锁内（模拟持锁线程被抢占/GC 暂停/页错误），其余实现注入在操作前 （延迟只属于自己）。报告非毒丸 op 的延迟分布——"一个人的延迟变成全队的灾难"的直接量化：
| 实现 | 注入位置 | 非毒丸 p50 | p99 | p999 | max | max/p50 |
|---|---|---|---|---|---|---|
| Bucket | 操作前 | 500 ns | 3.8 µs | 10.6 µs | 309 µs | 617× |
| LockedHeap | 操作前（对照） | 700 ns | 6.8 µs | 48 µs | 1,500 µs | 2,143× |
| LockedHeap☠ | 锁内 | 700 ns | 8.3 µs | 46.6 ms | 140.6 ms | 200,905× |
| Async | 操作前 | 1.3 µs | 6.4 µs | 206 µs | 186 ms | 143,224× |
- 大锁柱塞实锤且被放大 ~70 倍：同样 0.2% × 2ms 延迟剂量，锁外注入时 max 1.5ms（正常长尾）， 锁内注入时非毒丸 op 的 p999=46.6ms、max=140.6ms（放大 94 倍）。机理：持锁者延迟期间全队积压 在锁上，恢复后 burst 冲锁 → 唤醒风暴。真实系统里持锁线程被 OS 抢占、GC 暂停、页错误是常态—— 大锁的吞吐王座有明确适用条件：临界区短 且 持锁者不被外部长时间延迟。
- Async 对持锁者延迟结构性免疫（别人的延迟不通过任何锁传播给自己），但它的 GC 尾巴（186ms max）比柱塞本身还大——Workstation GC + 高分配下，无锁的柱塞免疫被分配停顿抵消。
- Bucket 全维度最稳：无单点锁、无大分配——毒丸下 max 仅 309µs。
4.3 Server GC 对照（DOTNET_gcServer=1，2026-08-18 补测）
| 指标（8 线程） | Workstation GC | Server GC | 变化 |
|---|---|---|---|
| Async 吞吐 | 12.6 Mops/s | 17.4 | +38%（并行回收释放分配压力） |
| LockedHeap 吞吐 | 32.0 | 37.5 | +17% |
| Bucket think-time max | 6,408 µs | 109 µs | 59× |
| SkipList think-time max | 15,478 µs | 205 µs | 75× |
| LockedHeap think-time max | 606 µs | 343 µs | 1.8× |
| Async think-time max | 21,900 µs | 30,855 µs | 反而最差 |
| Async 毒丸非毒丸 max | 170 ms | 248~326 ms | 依然全场最差 |
| SkipList 毒丸非毒丸 max | — | 62 ms | 比 LockedHeap（1.3ms）差 47× |
结论：GC 调整释放了大部分实现的尾延迟（Bucket/SkipList 改善 59~75×）——但 Async 是例外： 1.3 KB/op 的分配率连 Server GC 的并行回收都打不服（think-time/毒丸 max 依然 31ms/250ms+）。Async 兑现"无锁延迟确定性"的前提不是 Server GC，是降分配。SkipList 的毒丸数据（62ms）说明分段锁只 部分免疫持锁者延迟——victim+preds 链上的锁被延迟者持有时照样传导。
5. 并发正确性压测（Debug 链校验器 + Release 全量）
方法论：P=4 生产者各 N 唯一项 × C 消费者尽力消费 → 超时停止 → 主线程单线程 drain 收尾 → 全集 HashSet 校验。Debug 构建下 AsyncPriorityQueue 每 64 op 自动巡检链不变式。
| 场景 | Bucket | SkipList | Async | LockedHeap（对照） |
|---|---|---|---|---|
| MPMC 不丢不重（40 万项 Debug / 20 万项 Release） | ✓ | ✓（187ms） | ✓ | ✓ |
| SPSC 严格序（生产先行，消费段 0 反转硬断言） | ✓ | ✓ | ✓ | ✓ |
| MPSC 排序语义（drain 0 反转 + 全序列反转率参考） | ✓ 25.2%¹ | ✓ 18.0%¹ | ✓ 8.9%¹ | ✓ 10.0%¹ |
| DequeueAsync 等待-唤醒（4 消费者先真实挂起再生产） | ✓ | ✓ | ✓ | ✓ |
| DEBUG 链校验器（巡检 6 千+ 次/场景） | —（无此仪器） | —（无此仪器） | ✓ 无结构损坏 | —（一把锁无从损坏） |
¹ 反转率是"竞争性最小"语义的固有参考值（后到的更高优先级项可越过已出队的低优先级项），非缺陷； 单消费者语义下（SPSC 硬断言）全部 0 反转。
6. 实验版本（V2/V3）不入基准
AsyncPriorityQueueV2/V3 为设计验证实验（[Experimental] + internal）——性能数据无生产参考意义，
不测。
7. 选型速查（实测数据支撑）
| 场景 | 选择 | 依据 |
|---|---|---|
| 优先级 = 少量离散枚举（4~16 级） | Bucket | 单线程 52ns、8 线程 34.6 Mops/s、think-time/毒丸全负载最稳（§4）——没有短板的全维度王 |
| 优先级任意取值 + 高吞吐 + 临界区短且持锁者不被外部长延迟 | 自建一把 lock + 内置 PriorityQueue（LockedHeap 模式） |
8 线程 32.0 Mops/s、单线程 305ns、think-time 下 p50/max 全场最优（§4.1）。⚠️ 柱塞边界（§4.2）：持锁者被抢占/GC/页错误时全队 max 放大数百倍——延迟敏感场景换 Bucket/Async |
| 任意 int 优先级 + 免疫持锁者延迟（无单点锁依赖） | Async | 8 线程 12.6 Mops/s、256K 积压 1.3µs、别人的延迟不通过锁传播。⚠️ 分配率 1.3KB/op 在 Workstation GC 下尾延迟 22~170ms（§4）——延迟敏感需 Server GC 或降分配 |
任意 long 优先级 + 中低并发 / 零分配路径 / 无锁 TryPeek |
SkipList | 单线程 466ns、8 线程 9.4 Mops/s、分配 92 B/op、think-time 135K ops/s——健康可用的细分锁选项；吞吐落后大锁 3~4×（§2），吞吐优先选大锁 |
| 单线程/无并发 | .NET 内置 | 11ns——线程安全的定价不值 |
8. 已知边界
- Windows Workstation GC 实测；Server GC / Linux 下 Async 分配压力（1.3 KB/op）的 GC 频率未单测。
- 探针吞吐用 Thread 直起（非 ThreadPool），与真实异步工作负载的调度差异未消除——数据用于实现间 横向对比。
- think-time 用自旋模拟计算型 worker（均值 50µs 指数分布）；IO 型 worker（Sleep 让出）未测。
- 毒丸剂量 0.2% × 2ms 为单一组合；柱塞放大系数随剂量/线程数变化，未做扫参。
- short job 快速基线；正式入库用默认 job 复跑。