在大约2年前，我通过这篇文章探讨了有锁栈和无锁栈的性能，结果如下（单位为微秒）：

方法	有锁栈	无锁栈
#1	1,003,863	399,217
#2	884,579	186,314
#3	1,013,956	427,235
Avg	967,466	337,588

在当时的实验中，无锁栈的耗时大约是有锁栈的三分之一。

现在回过头来看，这个结果非常粗糙——实验运行在1C2G的Ubuntu环境中，只创建了两个工作线程，并且只测试入栈操作，其中还包含了节点分配的开销。它只能说明那一组条件下的性能，不能直接推出无锁数据结构在高并发场景下也一定更快。

本文想进一步探讨一个问题——在高并发场景下，大量线程持续竞争同一个栈顶时，无锁栈是否可能比有锁栈更慢？

下面的实验在本机macOS环境下进行。结果表明，在本文的高竞争负载下，使用std::mutex的栈确实比一个不带退避的Treiber无锁栈快。这种无锁栈由R. K. Treiber于1986年提出，因此以他的姓氏命名。¹

为什么无锁也会慢？

首先回顾有锁栈和无锁栈的区别。有锁栈需要先取得互斥锁，再修改栈顶，其他线程需要等待。而无锁栈通过CAS修改栈顶，如果栈顶还是刚才读到的值，就提交修改；如果已经变了，就重新读取并重试。

无锁省去了互斥锁，但没有消除对栈顶的争用。 线程少时，重试可能很少；但在高并发场景下，大量操作会失败并重新执行。这些失败的尝试同样消耗CPU时间，这也是无锁也会慢的原因。

实现与实验

实验环境

• Apple M4，10核（4个性能核、6个能效核），16 GiB内存。
• macOS 27.0.1，原生arm64运行。
• Apple clang 16.0.0，libc++，C++20，使用-O3 -DNDEBUG编译。

线程由macOS默认调度，没有绑核。值得注意的是，Apple M4芯片的两类核心性能不同，调度和后台任务可能影响结果。

C++实现

两个版本使用相同的链式节点。有锁版本在每次入栈、出栈时分别加锁。以入栈为例：

1
2
3
4
5

void push(Node* node, std::uint64_t&) {
    std::lock_guard<std::mutex> lock(mutex_);
    node->next = head_;
    head_ = node;
}

无锁版本使用Treiber栈，通过CAS循环修改栈顶，不加入退避等待（这也是一个很值得探讨的点，本文暂不深入）。入栈代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void push(Node* node, std::uint64_t& failures) {
    Node* expected = head_.load(std::memory_order_relaxed);
    do {
        node->next = expected;
        if (head_.compare_exchange_weak(expected, node,
                                       std::memory_order_release,
                                       std::memory_order_relaxed)) return;
        ++failures;
    } while (true);
}

CAS失败时，expected会更新为实际读到的栈顶，再进行下一次尝试。failures记录失败次数，每个线程单独计数，最后汇总。compare_exchange_weak允许伪失败，所以这个数字不完全等于被其他线程抢先修改的次数。²

入栈使用release发布节点，出栈使用acquire读取节点，保证其他线程能够正确读取next。出栈CAS失败后也需要acquire，因为下一轮会读取新栈顶的next。³完整的入栈、出栈代码见benchmark.cpp。

小fix：前文中的出栈代码在CAS成功后立即delete节点，但其他线程可能仍在读取它，可能会造成非法访存。本文实验代码在计时前分配所有节点，每个节点只入栈一次，发布后不再修改next。出栈后不释放、不重新入栈，等所有线程结束后统一回收。这样既避免了读取已释放节点，也避免了节点复用带来的ABA问题。两个版本采用相同做法，测量中都不包含分配和回收的开销。

实验方法

每组实验共执行1,000,000对入栈、出栈，再将任务平均分给各个线程。增加线程数时，总工作量不变。线程循环如下：

1
2
3
4

for (auto i = begin; i < end; ++i) {
    stack.push(&nodes[i], failures);
    popped[i] = stack.pop(failures);
}

所有线程操作同一个栈，中间不加入其他计算或等待。入栈、出栈分别同步，一个线程取出的不一定是自己刚压入的节点。

测量方式如下：

• 测试1至128个线程。每个配置先预热，再测量7轮，打乱线程数顺序，并交替两个版本的测试先后顺序。
• 线程准备好后统一开始计时，直到最后一个线程完成。计时包含唤醒和完成通知，不包含线程创建、节点分配和最终join。
• 记录实际耗时、累计CPU时间和CAS失败次数。结束后逐个检查节点，确认没有丢失、重复或残留。

一次入栈或一次出栈算一次操作，因此每组共有2,000,000次操作。吞吐量就是总操作数除以实际耗时。

实验结果

下表各项分别取7轮的中位数。吞吐量单位为Mops/s，即每秒百万次操作；倍率为两种吞吐量中位数之比。

两个线程时，无锁栈明显更快；四个线程时，两者比较接近；八个线程及以上，有锁栈更快。

以16线程为例，有锁栈的吞吐量约为无锁栈的9.71倍。此时，无锁栈每完成一次操作，平均还要经历约3.12次失败。这些重试没有增加完成的任务，却消耗了计算资源。

同一配置下，有锁栈完成任务的耗时中位数为33.17 ms，累计CPU时间为0.291 s；无锁栈分别为322.04 ms和3.004 s。无锁栈不仅更慢，完成同一批任务使用的CPU时间也更多。多线程CPU时间是各线程时间的累计，可以大于实际耗时。

为检查计数器是否改变结论，又关闭重试计数，针对8至128线程各补测3轮。16线程时，有锁栈仍约为无锁栈的9.51倍，其他配置也没有改变比较方向。完整数据见关闭计数后的结果。

结果也有明显波动。例如16线程的无锁栈有一次达到51.73 Mops/s，远高于其中位数6.21 Mops/s；单线程数据的波动也很大。全部样本均保留在原始结果中。

如何理解这个结果

单线程为什么也可能有锁更快

单线程没有CAS失败，差距不是重试造成的。互斥锁在没有竞争时通常可以在用户态完成加锁，无须阻塞等待；无锁栈仍要执行CAS，并保证读写顺序。两者都有同步成本，不能只看是否加锁。⁴

原来的7轮中，有4轮无锁栈更快，而且胜负与测试顺序一致。两组吞吐量分别取中位数后，有锁/无锁为1.58；逐轮计算比值再取中位数，则为0.75。结果对统计方式敏感，需要补测。

先检查测量过程本身：

接着，让同一个线程使用同一组节点，对比不同内存序。每次完成16,000,000次操作，每个版本测12轮，并轮换测试顺序。下表各项分别取中位数：

这些补测中的CAS失败次数均为0。“仅保留入栈release”一组的吞吐量范围为122.38至629.39 Mops/s，波动仍然明显。

保留CAS，只把内存序改为relaxed，吞吐量就提高了约5.9倍。这说明，原版CAS所需的读写顺序约束，是这段代码开销的重要来源。 指令数较少，也不代表耗时较少。

后四行只用于单线程诊断，不能替换多线程栈。 删除必要的release/acquire会破坏节点发布关系；把CAS拆成读和写，也不能保证多个线程正确修改栈顶。

补测还调整了线程的任务优先程度。⁵计数显示，两种实现的指令几乎都在性能核上执行，差距仍然存在，不能简单归因于无锁栈跑到了能效核。⁶

因此，在本机和这段代码中，无竞争的互斥锁路径比原版CAS操作序列更快。但这些数据还不能解释每一次波动，也不能当作单条CAS的固定成本。

完整的补充代码、数据、统计脚本和实验记录可供复现。

高并发时为什么更慢

单一栈顶是两个版本共同的瓶颈。无锁栈让多个线程不断尝试修改它，但同一时刻的竞争并不能让多个线程的修改一起成功。线程越多，失败和重试就可能越多，还可能增加核心之间传递共享数据的开销。

互斥锁也有成本，但有它的存在，不会出现所有线程一直重试取栈顶的操作。加锁也不意味着每次都进入内核，Apple的公开实现中同时存在用户态获取锁和内核等待的路径。⁴本文没有跟踪每次锁操作或测量缓存事件，无法进一步确定各部分开销。

需要注意，本文比较的是不带退避的Treiber栈，在多个线程连续操作同一个栈顶时的表现。减少共享、加入退避，或者在两次栈操作之间执行其他任务，都可能改变结果。这次实验也更换了旧文的硬件和负载，不能把两篇文章的差异全部归因于线程数。

无锁保证的是整体能够继续推进，并不保证更快。⁷在本次实验的高竞争负载下，有锁栈的吞吐量更高；低竞争时，无锁栈仍可能更合适。

复现

将C++代码和统计脚本下载到同一个目录，在macOS上执行：

1
2
3
4
5
6
7

clang++ -std=c++20 -O3 -DNDEBUG -Wall -Wextra -Wpedantic \
  -pthread benchmark.cpp -o /tmp/stack-benchmark

/tmp/stack-benchmark --pairs 1000000 --repeats 7 \
  --threads 1,2,4,8,16,32,64,128 > results.csv

python3 summarize.py results.csv

更多环境信息、关闭计数的命令和检查记录见environment.txt。

Reference

声明：本文使用生成式人工智能辅助撰写，观点及数据经过作者校对。