[Paper] 分片消除与合并用于高效并发栈

发布: 1周前 (2026年1月8日 GMT+8 10:42)

6 min read

原文: arXiv

Source: arXiv - 2601.04523v1

概述

本文介绍了 Sharded Elimination and Combining，这是一种新型的阻塞、线性化栈，结合了分片和巧妙的消除‑合并方案。通过降低对共享数据结构的争用，作者实现了相较于已知最佳并发栈 2× speed‑up 的提升，尤其在大量线程同时争用栈时效果显著。

Sharded Stack Layout – 将栈划分为独立的“分片”，可以并行访问，降低热点争用。
Elimination Mechanism – 直接相遇的 push 与 pop 操作绕过中心栈，相互抵消而不触及共享内存。
Combining Technique – 轻量级协调器将多个线程的待处理操作批量处理，在单个原子步骤中应用到一个分片。
Hybrid Design – 消除和合并组件无缝集成，使系统能够根据工作负载特性动态适配。
Empirical Evaluation – 在多核机器（最高 128 线程）上进行的大量基准测试显示，相较于最先进的并发栈（如 Treiber、Elimination‑Backoff、Flat‑Combining），性能提升稳定在 1.5‑2 倍。

Sharding – 将栈划分为 k 个子栈（分片）。每个线程首先对分片进行哈希，这样大多数操作都保持在本地。
Elimination Array – 线程在固定大小的消除数组中公布自己的意图（push 或 pop）。如果找到互补的操作，两条线程直接交换值并返回，避免对分片进行任何内存写入。
Combining Scheduler – 当消除失败时，线程可以成为其分片的 combiner。它从其他线程的（每线程）请求槽中收集挂起的请求，并使用一次对分片 top 指针的原子 fetch_and_increment 来批量更新。
Fallback Path – 如果消除和合并都不可用（例如数组已满、没有挂起请求），线程会回退到在其分片上使用传统的基于锁的 push/pop。
Correctness – 作者通过在成功的消除交换点或由 combiner 执行的原子更新点定义线性化点，从而证明线性化正确性。

该设计刻意保持简洁：仅依赖于在现代 CPU 上普遍可用的原子 fetch_and_increment 和 compare_and_swap 原语。

High‑Throughput Servers – 使用工作窃取队列或任务栈的应用（例如 Web 服务器、异步运行时）可以用此设计替换基于锁的栈，在负载下将吞吐量提升一倍。
Parallel Algorithms – 深度优先搜索、回溯或任何依赖共享栈的算法都可以受益于同步瓶颈的降低，尤其是在多核机器上。
Language Runtime Implementations – 虚拟机开发者（例如针对 Java、Go、Rust）可以采用分片消除‑组合模式，用于内部数据结构，如协程栈或垃圾回收器工作列表。
Ease of Integration – 该算法仅使用标准的原子操作；可以在 C/C++、Rust 或 Java 的 java.util.concurrent.atomic 包中实现，无需特殊硬件支持。