超越顺序一致性

标题：Beyond Sequential Consistency - Leveraging Atomics for Fun & Profit

日期：2025/08/11

作者：Christopher Fretz

链接：https://www.youtube.com/watch?v=qNs0_kKpcIA

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注一：看了眼好像话题很常规，估计是彭博的软广……代码有空再更新。

备注二：同样的话题，不如看看我的文章？超短的。

好的。太棒了。是的。我的名字是 Chris Fretz。这是我的演讲《超越顺序一致性——利用原子操作实现乐趣与性能提升》。我是 Bloomberg 团队的一员。我是 Bloomberg 的一名高级 C++ 工程师，在一个名为 Tickerplant 的组织工作。按惯例说一句，我们正在招聘。如果你喜欢你所看到的，可以来找我聊聊。好的。

对于这次演讲，我乐于在进行中回答问题。我之前排练时时间有点紧，所以可能会在某个时刻停止接受提问。我们看到时候的情况。好的。

那么，我们先从本次演讲的概览开始。这里的目标，显然是讨论 C++ 中可用的不同内存排序模型，以及这些模型的性能差异。我认为这一点，我希望这一点是这次演讲的独特之处。我看过，我知道 Alex 去年在这个会议上做过一个关于不同内存模型的非常棒的演讲。我见过几次类似主题的演讲。但我从未见过有人真正将这些模型应用到一个具体的数据结构上，然后实际去探讨它们能带来怎样的性能差异。我认为这是一个有趣的问题。因为，如果你要花费时间和精力、承担维护和开发成本去真正尝试使用松散原子操作（relaxed atomics），你最好对你到底能得到什么有所了解。因为说到底，这会让代码变得更复杂。

好的，所以我们会从一个快速的介绍开始，定义术语和核心概念，然后考虑使用不同内存模型的具体实现。我们会特别关注一个无锁数据结构——队列，它非常适合进行内存排序优化。关于这一点，这是我在之前一份工作中花了很多时间研究的数据结构，但它也恰好是一个优化效果非常好的结构。所以你在这里看到的具体结果，将总是与你实际关注的数据结构和你使用它的场景相关。

是的，我们专注于一个特定的数据结构，比较不同内存模型下这个队列的相对性能，然后还会考虑一些令人惊讶的结果，在这些情况下原子操作实际上并非必需。

首先是一些免责声明。无锁编程，我认为在技术上很酷，但它也会导致复杂的解决方案。我记得很久以前在一个演讲中，有人说，“你知道，我的无锁算法”，然后展示了一个疯狂的鲁布·戈德堡机械（Rube Goldberg machine）。它确实倾向于产生复杂的解决方案。它很难写对，很难维护，很难测试。而且我认为它常常被滥用。

关于无锁编程，你必须记住的一件事是，它不保证会更快。它可能会更快。但很多时候，你其实是在用“平均做更多的工作”来换取对线程的“进度保证”，这样你就知道你不会被阻塞，但你平均下来可能做了更多的工作。所以，它是否真的有收益，很大程度上取决于具体的应用场景。所以，基准测试，基准测试，再基准测试。性能是很难推理的。计算机很复杂。你认为某件事会有性能提升，结果却并非如此，这种情况时有发生。

是的，性能通常是与使用场景和硬件相关的。这次演讲关注的是数据结构本身的性能。而且，它选择了一个优化效果很好的数据结构。所以你必须时刻记住你的应用场景。如果你从队列中取出一个东西，然后马上尝试从网络套接字读取数据，那么你的队列有多快可能根本不重要。所以你得记住这一点。你的实际效果可能会有所不同。

但最后还有一个免責聲明，这是我尝试与 ChatGPT 讨论无锁编程中所谓的性能、正确性和可维护性之间的内在冲突时，它给我的。所以，请时刻思考你是否真的需要它。

好的。那么，在我们开始讨论具体的内存模型之前，我们可能应该先定义一下我们所说的“无锁编程”到底是什么。

通俗地讲，人们通常指的是避免使用互斥锁（mutex）和像软件锁这样的系统调用。显然，说到底，如果你的代码要完成任何有用的事情，你仍然需要某种形式的同步。所以，它通常更多地关注于可用的最小粒度的硬件锁，特别是依赖于那些保证某些操作是不可中断或原子的硬件指令。但归根结底，如果你希望你的程序能做出合理的行为，同步仍然是必需的。

更正式地讲，无锁（lock-freedom） 保证了至少有一个线程总是在取得进展。这听起来可能不是一个很强的保证，但我们稍后会深入探讨它的含义。

我们来看一个非常非常简单，虽然很糟糕，但很有说明性的例子。我们有这段代码。不要写这样的代码。 这不是好代码。但假设我们有这个 increment 函数，它的语义是想将某个全局计数器增加一个特定的值，你可以这样做：

/* 生成代码，仔细甄别 */

// 糟糕的、仅用于说明的互斥锁版本
void increment(int value) {
    static std::mutex m;
    std::unique_lock l(m); // CTAD，很方便
    global_counter += value;
}

我们有一个全局计数器，一个全局互斥锁。我们进入函数，立即获取一个 unique_lock。 nhờ vào class template argument deduction (CTAD)，我们可以直接这样写，很方便。这只是一个作用域锁。当我们进入词法作用域时，它会获取锁；当我们离开词法作用域时，它会释放锁。这是一种非常直接和传统的方式。这也是糟糕的代码。你不应该这样做。但同样，它说明了我正在谈论的问题。

在这个特定的例子中，我们没有互斥锁，而是一个全局的原子整数，它仍然初始化为零。我们有相同的 increment 函数和相同的语义。不同之处在于，这次我们在一开始加载一次计数器，然后调用这个 compareExchangeStrong 函数。

/* 生成代码，仔细甄别 */

// 糟糕的、仅用于说明的原子版本
void increment(int value) {
    auto prev = global_counter.load();
    while (!global_counter.compare_exchange_strong(prev, prev + value));
}

如果大家不熟悉，这个函数的语义本质上是：我们先加载计数器的值，然后当我们调用 compareExchangeStrong 时，如果内存中的值与我们加载的值相同，硬件就会原子性地将我们想要的新值交换进去。所以，我们加载一次，如果没有其他线程进来修改这个值，我们就会换入我们增加后的值。如果我们失败了，这个函数的语义是 prev（它是一个左值引用）会被更新为新的当前值，这样下次我们循环时，它就是最新的值。

这里的核心观察点是，尽管我说这是糟糕的代码，但如果我们最终进入了这个 while 循环的循环体，如果我们失败了，那必然是别人成功了。我们之所以需要退让（back off），唯一的原因就是我们知道另一个线程已经进来并完成了它的操作。

如果我们看一下汇编代码的分解：对于传统的加锁版本，这最终会归结为对 pthread_mutex_unlock 和 pthread_mutex_lock 的调用。而另一边，我们有一个神奇的 lock cmpxchg 调用。

那么，从概念上讲，这两种情况有什么不同呢？如今，操作系统对互斥锁的优化已经非常非常好了。所以在非竞争情况下，你实际上可能只会停留在用户空间。但如果你看 pthread_mutex_lock 的正式定义，它被允许做任何事情。你可能立即被置于休眠状态。操作系统可能会让线程堆积起来，然后在它方便的时候唤醒它们。你确实得到了“关键区内一次只有一个线程”的保证，但 pthread_mutex_lock 的定义本身并没有给出正式的进度保证。所以操作系统可以做它想做的任何事。

而在 lock cmpxchg 指令这边，我们再次得到了那个保证：如果我们失败了，就意味着有其他线程进来更新了计数器。所以，如果我们有三个线程同时进来，任何一个线程最多可能失败两次。所以你有了更强的保证。

（观众提问）

问：为什么是 while 循环而不是 if 语句？
答：嗯，说到底，我们可能会失败。问题是，我们必须重试，因为如果另一个线程在我们之前进来更新了值，比如说我们进来加载了计数器，然后被操作系统挂起。如果另一个线程进来，加载了那个计数器并换入了它的值，当我们醒来时，我们就会失败。所以这个操作不保证成功。这就是为什么我们需要一个循环。

话虽如此，这才是你应该实际写的版本，就是直接使用 +=。

/* 生成代码，仔细甄别 */

// 你应该实际写的版本
global_counter += value;

但我只是想传达这样一种思想：如果我失败了，必然有别人成功了。是的，这才是你应该写的版本。你可能甚至不需要为这个写一个函数。std::atomic 非常棒，它的所有操作符都被设计成能做你想要的事。如果你写这样的代码，你会得到右边的 lock add 指令。

; C++: global_counter += value;
lock add    QWORD PTR global_counter[rip], rax

这里的 lock 前缀使其成为原子的。在 x86 上，你得到的保证是：这个操作需要从内存中读取 counter 的值，增加它，然后写回。lock 前缀意味着这是原子的，从硬件其余部分的视角来看，这一切都是不可分割地发生的。

好的。现在我们来谈谈 C++ 内存模型本身。从 C++11 开始，我们获得了一个正式定义的内存模型，它包含了多种不同的内存排序。在 C++11 之前，显然人们已经写了几十年的多线程代码。但在 C++11 之前，你非常依赖于你所使用的特定库、特定硬件的保证和语义。像 Boost 和许多其他库让这变得容易了很多。但从 C++11 开始，我们真正地在标准本身中获得了保证。

在这些不同的排序中，我们有：

  • relaxed (松散)

  • acquire (获取)

  • release (释放)

  • acquire_release (获取-释放)

  • sequentially_consistent (顺序一致性)

技术上还有一个第六种，叫做 consume。别想它了。它在 C++26 中就要被移除了。我的理解是，它真的只适用于非常特定的硬件用例，而且它从来没有真正按照任何人想要的方式工作。所以，我们真正关心的是上面这些。而 acquire_release 只是前两种的组合。

所以，在一个较高的逻辑层面上，我们基本上有 C++ 标准提供给我们的三种不同模型。那么，我们为什么要有所有这些不同的排序呢？这是为了什么？这似乎增加了很多复杂性。嗯，是这样的，在一台现代的对称多处理（Symmetric Multiprocessing）机器上，也就是你过去 20 多年里用过的任何一台机器，所有的核心（也就是芯片上的所有独立处理单元）都在同时与内存交互。有趣的是，每个核心都有自己的缓存。CPU 实在太快了。从系统其他部分的角度来看，CPU 是你机器上最快的东西。因此，要让 CPU 发挥高性能，很大程度上取决于如何让内存的移动速度跟上它。

每个核心都有自己的缓存，而且在现代机器上还有多级缓存。这意味着不同的核心可能拥有相同数据的独立副本。所以，如果你有不同的核心在操作共享数据，那么谁在什么时间看到哪些更改？不同的核心对事件的相对顺序是否会达成一致？比如，如果你有两个核心在改变内存中两个不同的值，核心 0 和 1 在改变一些标志，那么核心 3 和 4 会看到什么？你怎么知道它们会以什么顺序看到那些变化？

C++ 内存模型的不同排序，给了程序员对此进行细粒度控制的能力，并允许你为混乱带来秩序。你可以这样想：C++ 定义了一个抽象的内存模型，提供了几种可用的排序，这些排序对不同线程如何观察事件给出了不同的保证。然后，最终，厂商和库作者的工作就是去使用硬件和工具链特定的内在函数（intrinsics）来实现和维护这个模型。所以，如果你作为程序员，用 release 排序做了一次存储操作，那么标准库 std::atomic 和工具链本身就有责任确保它真正维护了 C++ 在该操作上所承诺的保证。

为了深入细节，我们必须谈谈所谓的内存栅栏（memory fences）或内存屏障（memory barriers）。我们必须认识到，现代机器和工具链可以到处重排你代码的执行顺序。如果你使用链接时优化（LTO），你的代码可以在构建、链接或运行时被重排。优化器或多或少可以做任何它想做的事，只要它遵守 “as-if” 规则，即它实际构建的程序运行起来就好像是你写的那样，并且符合 C++ 标准的要求。

是的，CPU 流水线可能会根据运行时的依赖关系决定重排指令。缓存一致性协议可能导致加载和存储被不同线程以不同顺序观察到。因此，从单个核心的角度来看，运行时顺序似乎违反了程序员的常识因果关系。

而栅栏和屏障让我们能够做的是，它们是我们能用来约束这些重排的最低级原语。有多种不同类型的栅栏。你可以有编译器栅栏，这纯粹是一个编译时构造，它在运行时不产生任何代码。但你基本上可以告诉编译器或工具链，“我需要你不要重排这些指令。我需要它们按照我写的顺序发生。” 这可以防止工具链重排操作。

你也可以有运行时栅栏，这实际上是汇编指令，是运行时的操作码，它们约束 CPU 流水线和内存子系统，防止硬件重排操作。最终，std::atomic 这样的库和工具链会使用这些构造，或者允许程序员使用这些构造，来限制实现可以做什么，以便你能推理你的代码。

（观众互动）

问：运行时栅栏是特定的实际操作，还是其他操作上的标志？
答：通常我看到的是两者都有。如果我们回到之前那个 lock add 的例子（幻灯片太多了我不想翻回去了），lock 是一个前缀，它本身就具有内存栅栏的语义。所以你可以把它看作是现有指令上的一个标志。但也有专门的指令。比如在 x86 上，有 sfence、mfence 和 lfence（我相信是这几个）。这些都是独立的汇编指令，用来设定可以做什么的约束。

问：C++ 标准化的是数据栅栏和屏障，对吧？跟指令无关？
答：是的，没错。C++ 标准给你提供了一个抽象的接口。然后你的特定标准库使用这些工具来实现它们。

问：我的意思是关于指令。比如你有一个缓冲区，你把指令写入其中，然后想执行它，大多数硬件都需要某种屏障，对吧？因为你要让指令缓存之类的东西失效。
答：是的，是的。我记得我在某处写过，关于加载和存储缓冲区。是的，说到底，那些栅栏也会确保它们被正确刷新，以便其他核心可以看到。

栅栏也有多种类型，你有存储栅栏、加载栅栏和组合的全栅栏。这再次控制了你要刷新的部分。好的。

现在我们来谈谈具体的排序。

顺序一致性

对于这个，你可以看到我们有一个非常有序的火车站。我们有一个非常漂亮的钟，火车准时运行。人们非常有秩序地走在站台上，走向他们的火车。我不知道为什么列车员站在铁轨上，忽略那个。但除此之外，这里的一切看起来都非常有秩序。

当实现使用顺序一致性时，存在一个所有顺序一致操作的全局总排序，所有线程都对此达成一致。你仍然有操作的传递性可见性，也就是说，如果一个线程看到了 A，然后是 B，然后是 C，并且这些操作是用顺序一致性排序的，那么可以保证所有线程在任何地方都会看到 A，然后 B，然后 C。

这提供了全局的保证，让程序员可以推理事件的顺序。这是默认行为。我们在 C++ 中有句俗话，说我们所有的默认值都是错的。我认为这可能是个例外，这个默认值可能实际上是好的。

（观众：我不同意）

答：那是问题所在。它是最慢的行为，而且正如我们将看到的，它非常慢。它默认采取了最保守的排序。

给一个具体的例子。我们有三个全局原子整数 A、B 和 C，都初始化为零。然后在我们的 main 函数中，我们有一个线程向量。如果不熟悉 jthread，它是一个可加入的线程，基本上当它的析构函数被调用时，它会自动与它管理的线程汇合（join）。我们只是把三个 lambda 表达式 emplace_back 到这个向量中。所以我们隐式地启动了三个线程。当 main 结束时，它会尝试销毁向量，这会尝试销毁线程，它会等待所有这些线程退出。

/* 生成代码，仔细甄别 */

std::atomic<int> a = 0, b = 0, c = 0;
// ... in main ...
std::vector<std::jthread> threads;
threads.emplace_back([&]{ a++; b++; c++; });
threads.emplace_back([&]{ c++; a++; b++; });
threads.emplace_back([&]{ b++; c++; a++; });

有趣的是，我们可以看到在这三个不同的线程中，我们对这些变量的增量操作顺序完全不同。我们的代码没有设置任何东西来保证实际的运行时顺序会是怎样的。操作系统可以以任何顺序启动这些线程，或在任何时候取消调度它们。我们对运行时顺序没有任何保证。但是，我们确实有一个保证：无论最终的顺序是什么，所有线程都会观察到同样的事情。所以，如果线程一看到了某个特定的事件顺序，所有线程都会对此达成一致。不可能看到在事件排序上不一致的情况。正如我之前所说，顺序一致性是默认的，这就是为什么前缀自增 ++ 操作符会直接给我们这个行为。

好的。

获取-释放

接下来是获取-释放。我不确定 GPT 是否真的理解我想要表达什么。我想在这只钟上放多只手，来表示人们不一定对现在是什么时间达成一致。但是，我们至少还有一个站台，人们还在做些什么。火车开始变得有点奇怪，但我们仍然有一些一致性。

我理解获取-释放的方式是这样的：在特定的原子变量上使用获取-释放，会在线程之间建立一个同步点。通过获取-释放，程序员获得了进行那种常识性因果推理的能力，那种顺序一致性的推理，但只是在特定的线程集合内。

这是一大段文字，但我认为它很好地解释了这一点。如果线程 A 以 release 排序将一个值存入变量 X，而线程 B 以 acquire 排序从该变量加载那个值，那么可以保证 B 能看到在 A 存储到 X 时对 A 可见的所有传递性存储。

你可以想象，如果线程 A 正在做一堆事情，比如使用不同的类，它们都在改变全局状态。然后它用 release 排序将 5 存入变量 X。如果线程 B 接着用 acquire 排序从该变量加载了 5，那么 B 就能看到 A 那边发生的一切。在 A 中那个存储操作之前发生的一切，都保证对 B 是可见的。

这听起来很像顺序一致性，但不同之处在于，这只对以这种方式同步的线程成立。在这种情况下，我们说线程 B 与线程 A 同步（synchronizes-with）。对于没有以这种方式同步的线程，没有任何保证。这就是它与顺序一致性的本质区别：顺序一致性是全局保证，而这个，你只对明确选择加入同步的线程有保证。

（观众：这是单向的吗？）

答：是的，是的。没错。没错。

给一个具体的例子。假设我们有两个线程，一个生产者线程和一个消费者线程。我们再次有两个全局变量。我不知道为什么我这里用了等号而不是通用初始化，但无所谓。我们有两个变量，一个是非原子的布尔值，另一个是原子的布尔值。

/* 生成代码，仔细甄别 */

bool non_atomic = false;
std::atomic<bool> atomic = false;

// 生产者线程
void producer() {
    non_atomic = true;
    atomic.store(true, std::memory_order_release);
}

// 消费者线程
void consumer() {
    if (atomic.load(std::memory_order_acquire)) {
        assert(non_atomic == true);
    }
}

在生产者线程中，我们将 true 存入 non_atomic，然后用 release 排序将 true 存入 atomic。在消费者线程中，我们用 acquire 排序从 atomic 加载。在运行时，如果我们进入了这个 if 语句的主体，那么可以保证那个断言会通过。不保证我们能进入那个 if 块，因为操作系统可能选择在启动生产者线程之前启动消费者线程。但如果我们进入了那个 if 块，那个断言就保证会通过。

你可以这样想，这就是我之前谈到的栅栏：对 non_atomic 的这次存储在流水线的任何一点上都不能被重排到 atomic 存储操作之后。而这个对 non_atomic 的加载（在 assert 里）在流水线的任何一点上都不能被重排到这个 acquire 加载之前。如果需要发出运行时操作码来保证这一点，实现会为我们做。

（观众互动）

问：如果在 atomic 存储下面还有另一个对非原子变量的 true 赋值，那个可以被移上去吗？
答：我相信那种情况下是允许被移上去的。我认为这是一个单向的屏障。你对那个操作是否可见没有特定的保证。它可能是可见的，但你没有保证。

问：那个非原子存储甚至不需要是 relaxed 原子存储吗？
答：不，它只是一个普通的存储。这里的 release-acquire 建立了一个“happens-before”关系，所以你保证了即使那个是非原子的，它在另一个线程中也是可见的。

问：如果我们想用这些原子加载和存储来实现一个互斥锁，这是我们需要的内存排序吗？
答：你当然可以用这个排序来实现它。但我鼓励你不要自己实现互斥锁。

问：我的问题是，我们能用更松散的模型吗，还是需要这个模型？
答：我相信你可以用这个模型来做。最终取决于你的实现会是什么样子，但我相信可以。在互斥锁中，关键区内发生的一切都必须对其他线程可见。所以我想这就是它的思想。是的，你应该可以用这个来做。

问：如果你用完全松散（relaxed）的模型，你什么都做不了。
答：是的，我们接下来会讲到。relaxed 真的给不了你什么依据。

好的，很好的问题。

松散

然后我们来到了 relaxed，这里是完全的混乱。时钟爆炸了。没有站台了。人们都在铁轨上。一切都乱七八糟，没人知道发生了什么。

使用 relaxed 排序，它只保证原子性，也就是说，没有线程能看到一个部分的写入。你仍然有“要么发生要么不发生”的保证。还有一个叫做修改顺序（modification order）的东西，这很有趣，我在为这次演讲做研究之前其实并不知道。修改顺序基本上只是说，对于那一个变量，仍然存在一个所有写入操作的总排序。对于内存中的那一个位置，你仍然保证有一个所有线程都同意的写入总排序。但是，对于这些写入与其他读写操作的可见性顺序，没有任何保证。

它既不建立运行时栅栏，也不建立编译器栅栏，因此可以在编译时或运行时被任意重排。

（观众互动）

问：所以它只保证对写入的排序，其他什么都不保证？
答：它只保证，基本上，你有一个保证，所有线程都会同意对内存中那一个位置的写入顺序。但你无法推理这些写入与程序中任何其他写入的关系。
问：所以它只会保证它发生了，但不会保证……好的。
答：是的。修改顺序是个有趣的概念。它确实能让你推理一些事情，但这是一个非常非常弱的保证。

好的，给一个具体的例子。我们再次有两个不同的线程，线程 A 和线程 B。这个程序的一个有效输出——这并不是说这在任何方面都是保证的，但这是一个有效的输出——是两个线程都打印 42。

/* 生成代码，仔细甄别 */

std::atomic<int> one = 0, two = 0;

// 线程 A
void thread_a() {
    one.store(two.load(std::memory_order_relaxed), std::memory_order_relaxed);
    std::cout << one.load(std::memory_order_relaxed) << std::endl;
}

// 线程 B
void thread_b() {
    two.store(42, std::memory_order_relaxed);
    std::cout << two.load(std::memory_order_relaxed) << std::endl;
}

这怎么可能发生呢？因为 42 直到线程 B 的一半才出现。但是，完全可能发生的是，编译器或运行时环境决定，“嗯，我更愿意先做那个。” 比如，“我想在实际存储到 one 之前先运行对 two 的存储。” 然后也可能发生的是，操作系统决定，“嗯，让我们在启动线程 A 之前先启动线程 B。”

所以，一个有效的运行时顺序是：

  1. 线程 B 存储 42 到 two。

  2. 线程 B 被取消调度。

  3. 线程 A 启动，从 two 加载 42，然后将其存回 one。

  4. 线程 B 醒来，从 one 加载 42。（译者注：原文这里似乎说反了，应该是线程 A 从 two 加载 42 存入 one 并打印，然后线程 B 醒来从 one 加载并打印。或者反过来。关键点在于重排使得这种看似不可能的结果成为可能。）

  5. 我们现在两个线程都打印了 42。

这可能不是任何人在最初看代码时会猜到的。但使用 relaxed 排序，这是被允许的。

（观众互动）

问：你得到的结果可能对应于任何顺序，比如“凭空”（out-of-thin-air）写入？
答：是的，那是……我的理解是，确实存在“凭空”写入的可能性，即某个值凭空出现然后变得自我证明。我的理解是，这在内存模型中是形式上允许的，但在任何现有的实现中都不存在。

问：我觉得在 ARM 上可以得到。
答：真的吗？好吧。是的，Intel 对此有更强的理念。

问：所以看起来你无法用 relaxed 来推理任何事情。那么，它至少运行得更快吗？
答：哦，是的。这就是它的目的。我想我有一张关于这个的幻灯片。是的，它给了实现完全的自由，在任何或多个层面上进行重排。它让程序员几乎无法推理任何事情。但同时，是的，它超级快。

问：所以你得到的是垃圾，但速度很快。
答：不，你得到的不是垃圾。你可以用它做事。我不知道你会得到垃圾。承认一下，关于“凭空”写入的情况我了解不多，所以我无法直接对此发表评论。我在我用过的任何真实硬件上的经验是，你仍然可以使用 relaxed 排序。你必须小心使用，并且需要知道排序对你来说不重要。在这次演讲中，我们会有些情况使用 relaxed 排序。

问：我对此的理解是，relaxed 的几乎所有实际有效的用法都涉及到把它当作从 AI 那里得到的东西。你得到一个东西，它是一个猜测，它可能是对的。你可以基于这个猜测做一些事，这可能会加速你的程序，但你最终必须在某个点进行验证。
答：最常见的实际用途只是用于日志记录的计数器。比如，我只想大概知道这件事发生了多少次。

问：我的理解是，这只对原子性有好处，但对同步没用。对于你展示的第一个原子操作的例子，汇编代码中 add 指令有 lock 前缀。那是一个在原子变量上加值的单条指令。如果用 relaxed 模型，这会有所不同吗？
答：这取决于硬件本身能提供什么。我相信如果你在 Intel 上用 relaxed 排序做一个 fetch_add，你仍然会得到一个 lock 前缀。所以你得到了比你要求的更强的保证。但这取决于硬件能做什么。

问：那种情况下它们会产生相同的代码？
答：我相信在 Intel 上会。是的。但你形式上没有这个保证。

问：想象一个系统，有一个主线程设置一个布尔值，当这个布尔值被设置后，所有其他线程都需要终止。这会是 relaxed 的一个合理用例吗？除了这个布尔值，没有其他数据交换。
答：在我用过的任何平台上，我认为这会表现得很合理。但同样，没有正式的保证。

问：这里有个问题，因为没有重排约束，那个对布尔值的 relaxed 设置可能会被提到比你预期的早得多的位置。所以你的所有线程可能会在你预期之前就终止了。
答：啊，但这是编译器的问题，因为编译器移动了那个变量。
答：这是所有层面的组合。是的。话虽如此，就像我说的，在我用过的任何硬件上，你说的这种情况似乎是可行的，但我不知道它在所有情况下是否可移植。

好的，我想继续前进，因为我还有很多幻灯片。但这确实是非常有趣的东西，你可以从 relaxed 排序中得到很多非常奇怪的东西。

一个实用的无锁数据结构

现在我们来谈谈一个实用的无锁数据结构。我们将从一个典型的例子开始，它非常有用、优雅且快速，我认为是这样。那就是一个无锁环形缓冲区（lock-free ring buffer）。

其思想是，我们有一个内存的循环缓冲区，以及用于在线程间移动数据的原子计数器。基本用例是单生产者，单消费者（SPSC）。它可以被轻易地扩展为单生产者，多消费者（SPMC）。如果你需要有多个生产者，事情会变得更复杂，但也是可以做到的。

这是一个高层次的概念图。我会再回到这张图。这只是为了给出一个粗略的想法。

核心思想是所谓的“无限数组”。我不认为这是我的术语。但基本上，你可以想象如果你有无限的内存，实现一个队列最简单的方式可能就是拥有一个永远延伸的数组。然后你只需要两个索引，两个原子整数。

  • 向这个无限数组入队，将通过把数据复制到数组中，然后增加生产者索引来完成。

  • 从这个无限数组出队，将通过从数组中复制出数据，然后增加消费者索引来完成。

你有一个至关重要的保证：索引是单调递增的。它们永远不会减少。所以消费者只需要看着生产者索引说，“我和生产者索引相等吗？这个队列里真的有数据吗？” 如果不相等，那么你就可以复制出来并增加索引。你知道索引会永远增长，永不减少。

这再次是那个概念的图示，想象你有无限的内存。数据在消费者和生产者之间。消费者只是复制、增加、复制、增加、复制、增加。而生产者做相反的事情。

（观众提问）

问：我只想确认一下，是先增加索引然后放入数据，还是……
答：不。生产者是先复制到队列中，然后才增加索引。其思想是，生产者索引代表了下一个将被写入的条目，但你还不知道那里是否有数据。
问：哦，所以是单……哦，是单生产者。好的，好的。明白。

好的。太棒了。

在实践中，我们显然没有无限的内存。要是能有就好了。但这个设计可以被轻易地改造。实际上，我们仍然有两个原子计数器，一个生产者索引和一个消费者索引。这些计数器，这些索引，仍然是无限数组的索引。但我们使用模运算从无限数组映射到有限的内存中。缓冲区被循环使用，从末尾绕回到开头。如果 overrun。

这又是 GPT 对此过程的可视化。我们的数据在上面。队列按顺时针方向旋转。生产者在这里写入东西，消费者在这里读出它们。这就是这里发生的事情。我有一个更好的可视化。

当生产者和消费者相等时，意味着队列中没有数据，因为生产者还没有写入那条记录。但生产者可以向右跑，现在消费者有三条记录可以读取。这些东西会继续向右跑，消费者追赶生产者。然后核心部分是这里的环绕情况。

最终，生产者会用完空间。因为我们使用模运算，它会映射回零。但它的索引仍然是 12。因为它的索引是无限数组的索引。所以你仍然有那个单调递增的保证。但在环绕情况下，它看起来是这样的。

如果我们从接口的角度来想象，我们有生产者函数和消费者函数。它们会在两个不同的线程上。我们有一个环形缓冲区的指针，指向实际的队列本身。对于生产者，我们这里做的是，我只是循环到 100 亿。所以我们有世界上最简单的队列，我们此刻只是在推送整数。但我们将循环遍历从 0 到 100 亿的所有值，把它们推进去，而消费者只是把它们弹出来。然后消费者在进行时也在计数，这样我们就可以断言我们的队列是正确的，并且我们是以放入的顺序取出的数据。但我们只是从队列中弹出数据，断言它等于我们期望的值，然后循环。

/* 生成代码，仔细甄别 */

// 生产者
void producer(RingBuffer* rb) {
    for (uint64_t i = 0; i < 10'000'000'000; ++i) {
        rb->push(i);
    }
}

// 消费者
void consumer(RingBuffer* rb) {
    uint64_t count = 0;
    while (true) {
        uint64_t val = rb->pop();
        assert(val == count++);
    }
}

我认为这是一个人能写出的最简单的环形缓冲区了。你可以想象它可能是这样的。显然在非幻灯片代码中，这会是一个类模板。你会把它模板化在 T 上，可能还有你的容量。但目前，我们只是将容量固定为 2 的 15 次方。在我的测试中，这似乎性能最好。

/* 生成代码，仔细甄别 */

struct RingBuffer {
    static constexpr size_t CAPACITY = 1 << 15;

    std::atomic<uint64_t> next_producer_record = 0;
    std::atomic<uint64_t> next_consumer_record = 0;

    void push(uint64_t val);
    uint64_t pop();

    // ... helper functions ...
    size_t size() const;
    void sleep();
    size_t map_index(uint64_t index) const;

    uint64_t data[CAPACITY];
};

我们下面有两个索引。next_producer_record 和 next_consumer_record。这是下一个要写入的记录，这是下一个要读取的记录。我们有 push 函数，pop 函数，然后是一些辅助函数。size 函数只是给出生产者和消费者之间的当前距离。sleep 只是一个小的退让自旋锁。然后 map_index 就是那个将无限数组的索引映射到我们实际数据数组中的部分。

我们来看 push 的实际实现，非常简单。

/* 生成代码，仔细甄别 */

void RingBuffer::push(uint64_t val) {
    while (size() == CAPACITY) { // 队列已满
        sleep();
    }
    data[map_index(next_producer_record)] = val;
    ++next_producer_record; // 通知消费者
}

上面的主要谓词是 while (size() == CAPACITY)，这意味着队列已满，生产者不能再放入数据。它已经环绕了，生产者正坐在消费者身上。但在那之后，就实际的生产而言，我们只是复制到数据数组中。我们有 map_index 函数，它只是做一个模运算。因为我们是 2 的幂，这可以是一个位掩码，但我认为这段代码更明显。编译器无论如何都会为我们做这个。而 size 只是用生产者索引减去消费者索引。所以只要队列里有空间，我们就复制进去，然后增加我们的生产者记录，让消费者知道这个值现在已经被写入了。

（观众提问）

问：你只检查了 size 是否等于 CAPACITY，但当它满的时候会发生什么？
答：嗯，那就是它满的情况。基本上，你显然可以有很多不同的实现。目前的实现是，它会永远阻塞直到它不满。你可以有不同的语义。你可以有像 push_if_empty 或 push_if_space_available 之类的。这个实现现在会一直阻塞，直到消费者最终在队列中释放了空间。

pop 函数基本相同。

/* 生成代码，仔细甄别 */

uint64_t RingBuffer::pop() {
    while (size() == 0) { // 队列为空
        sleep();
    }
    uint64_t val = data[map_index(next_consumer_record)];
    ++next_consumer_record;
    return val;
}

我们再次有自旋计数器。我们的谓词不同。在这种情况下是 while (size() == 0)。所以当队列中没有数据时，我们休眠。但除此之外，完全一样，我们只是映射到数据数组，取出记录，然后增加消费者索引。

这是一个非常基础的环形缓冲区实现。

（观众提问）

问：在检查和 size 之间，记录和消费者的指针不会改变吗？ 答：关键的一点是，我们的队列中有两个线程，但生产者和消费者各自是单线程的。这就是为什么这能行。是的，如果你需要开始担心多个线程增加同一个索引，事情会变得复杂得多。但这就是为什么这能行，为什么 size 可以这么简单，我只需要检查一次然后就完成了。

好的，很好的问题。

如果你这样做，我是在一个 64 位 x86 的 Intel Xeon 处理器上运行的，一个服务器级别的芯片。我得到的结果是，这个程序运行了 10 分钟，像这样写的队列，我们每秒大概能处理 1000 万条记录。

不知道大家对写无锁队列有多少经验，1000 万条记录听起来可能很棒，但实际上它相当糟糕。这个特定的芯片运行在 2.6 GHz。所以 1000 万条记录意味着我们每条记录大约需要 260 个时钟周期。而我们的队列什么都没做。它完全没有做任何工作。它只移动整数。这应该是最快的可能情况。我们应该能快得多。所以问题是，怎么回事？

如果我们回头看我们的 push 函数，右边是汇编分解。细粒度的细节不那么重要。

  • 这里我们从生产者加载。

  • 这里我们从消费者加载。

  • 我们在这里做减法得到队列的大小差。

  • 我们将其与最大大小比较。

  • 如果不相等，JNE，我们跳转到标签 48，在那里我们进行实际的生产。

  • 否则我们进入我们的 nanosleep 退让。

标签 48 是生产实际发生的地方。

  • 我们加载生产者索引。

  • 这个 and 指令是我们映射到队列中。这是位掩码，用来截掉高位，只停留在队列内。

  • 这个 mov 指令是实际存储到数组中。这是 x86 允许我们做的复杂索引。

  • 然后，这里是 lock add。这个 lock add 直接对应于 ++next_producer_record。

如果我们看消费者，它基本上完全一样。我们加载我们的索引。这次我们直接比较，因为我们想知道索引是否彼此相等。如果不相等，意味着队列中有数据。所以标签 22，再次，我们做位掩码。我们在从队列中取出后有我们的 lock add。

有趣的是，如果我们实际去看这个汇编，它都是 and、mov、cmp、条件分支。这里面没有任何有趣的东西。唯一有趣的是这个 lock add。这真的是唯一可能成为瓶颈的东西。其他一切都只是非常标准的 x86 汇编。

是的，这个汇编中唯一的潜在瓶颈是 lock add。这是一个读-改-写指令。它发出一个完整的内存栅栏。正如我之前提到的，这意味着我们基本上要做三件事。硬件必须读取 consumer_record 的值，增加它，然后刷新回内存。由于 lock 前缀，它将这三件事作为一个整体来做。

我们真的需要这个吗？这回到了你刚才提出的问题，我们真的不需要。通过在 std::atomic 上使用默认的 API，即调用操作符，我们隐式地请求了完全的顺序一致性。通过使用前缀自增操作符，我们还隐式地请求了读-改-写。但是生产者和消费者各自是单线程的。我们知道没有其他人会触碰那个索引。所以这个模式不需要顺序一致性。我们可以同时避免顺序一致性和 fetch_add。

下一个版本，我们现在用手动加载和存储替换了所有的操作符调用。

/* 生成代码，仔细甄别 */

// 生产者
void RingBuffer::push(uint64_t val) {
    while (!has_space()) {
        sleep();
    }
    // ...
    data[map_index(next_producer_record.load(std::memory_order_relaxed))] = val;
    next_producer_record.store(prod_idx + 1, std::memory_order_release);
}

// 消费者
uint64_t RingBuffer::pop() {
    while (!has_data()) {
        sleep();
    }
    // ...
    uint64_t val = data[map_index(next_consumer_record.load(std::memory_order_relaxed))];
    next_consumer_record.store(cons_idx + 1, std::memory_order_release);
}

  • 我们用 acquire 排序加载我们的生产者记录。

  • 我们用 release 排序存回生产者。

  • 在 has_space 中，我们只是用 acquire 排序从消费者加载，检查我们是否低于容量。

这本质上是相同的代码，只是现在我们手动发出加载和存储，并且我们使用 acquire 和 release 排序。

（观众：你真的需要在生产者中用 acquire 吗？）

答：有趣的是，这实际上是我从幻灯片中删掉的一个内容。不，我相信你在这里实际上不需要 acquire 排序。但是，暂且不论，这是个好观点。

消费者的代码基本相同。都是 acquire，release，acquire，release。这个对生产者的 acquire 特别重要，我们稍后会讲到为什么。但是的，这只是手动进行加载和存储，以确保我们得到我们想要的行为。

仅仅通过做这些改变，微不足道的修改，这是汇编最终的样子。再次，它不那么重要。编译器在优化和内联方面变得非常激进。事情实际上最终被重新排序了。

  • 我们加载生产者，加载消费者，位掩码。

  • 标签 59 是我们实际生产的地方，它实际上在汇编的上方。

  • 标签 59 在这里，我们存储到队列中。

  • 然后更新生产者索引，你可以在这里看到。

这里的重点是，在现在的汇编中，我们没有 lock 前缀。它都只是非常标准的汇编。

（观众：你能尝试用顺序一致性替换每个 acquire/release 吗？）

答：我没有为这个特定的代码尝试这样做。在 x86 上，这最终可能等同。很有可能。我们稍后会讲到，x86 默认就非常非常一致。所以你建议的可能导致了相同的汇编。是的。但这会在其他平台上获得更好的性能。

好的。仅仅通过这样做，没有其他任何改变，这就是我们得到的。

  • 蓝色是我们的原始顺序一致性。

  • 橙色是我们现在使用 acquire/release 排序的情况。

我们现在平均每秒处理大约 1.75 亿条记录，这相当惊人。我们的新代码在 64 位 x86 上实际上没有任何原子指令或栅栏。在 2.6 GHz 下，这大约是每条记录 15 个时钟周期。

这几乎让人怀疑这些数字是不是太好了。但是，测试机器有 32KB 的 L1 缓存和 1MB 的 L2 缓存。队列只包含整数。所以整个东西都装在 L2 里。大约八分之一装在 L1 里。我们有极其可预测的内存访问模式。我们只是在一个数组上顺序地、一遍又一遍地循环。有了预取，我认为这确实是合理的。而且我也确实去检查了汇编。我知道我不是在测试一个空循环。

但是这个队列有点太小了，不现实。显然在真实世界的用例中，你的程序中会有更多的噪音，会扰乱缓存。但这显示了硬件实际上能做到什么。

那么，我们还能更快吗？

伪共享

这是另一张 GPT 的图片。我们有这个评论，“独立的例程，共享的资源。伪共享拖慢了每个人。” 我们有一个哥哥和一个妹妹。他们都想用同一个浴室。他们想做完全不同的事情。妹妹想刷牙。哥哥想梳头。但只有一个浴室。一次只能有一个人在浴室里。所以即使他们想做完全不相关的事情，他们最终还是会互相干扰，不得不等待。

那么，我们可能在竞争什么呢？这是无锁的。这是从哪里来的？

如果我们看一下我们队列的声明，next_producer_record 和 next_consumer_record 在内存中是紧挨着声明的。它们是 64 位整数。它们每个 8 字节。基本上可以保证这两个记录会落在同一个缓存行上。

/* 生成代码，仔细甄别 */

struct RingBuffer {
    // ...
    std::atomic<uint64_t> next_producer_record; // 可能会在同一个缓存行
    std::atomic<uint64_t> next_consumer_record; //
    // ...
};

通常这是好事。因为，更好的数据局部性。这意味着我们会更缓存友好。但在这个特定的情况下，这真的不好。是的，它们很可能落在同一个缓存行上。不同的核心会为了同时修改同一个缓存行而争斗。

我们还没怎么谈到缓存行，但在大多数系统上，缓存行是内存子系统的最小粒度。问题在于，至少对于 Intel 来说，有一个叫做 MESI 缓存协议的东西。它代表 Modified, Exclusive, Shared, Invalid。这是每个独立缓存行可以处于的状态。问题是，我们的两个索引都在同一个缓存行上。所以，当生产者去更新它的索引时，它会使消费者拥有的副本失效。然后当消费者去更新它的索引时，它将不得不从另一个队列（核心）把它拉回来。这些东西会来回争抢，你最终会来回发送这个缓存行。

（观众：你的部分队列数据也在那里，你关心吗？）

答：我们也会讲到那个。在我修复这个的版本中，我们也会……是的，我们会讲到。

问题是，这两个线程最终会持续地互相争斗，不得不来回发送这个缓存行。酷的是，在 C++11 中，我们得到了 std::hardware_destructive_interference_size。这正是为了解决这个问题而存在的。

如果我们看一下下一个版本，你可以看到，我们也将数据数组对齐了。如果我们真的去修复这个问题，我们可以加载 std::hardware_destructive_interference_size。这来自头文件 <new>。我们可以得到我们的缓存行大小。然后如果我们为所有这些东西添加 alignas 说明符，我们实际上可以把每个计数器都对齐到一个缓存行对齐。

/* 生成代码，仔细甄别 */

struct RingBuffer {
    static constexpr size_t CACHELINE_SIZE = std::hardware_destructive_interference_size;

    alignas(CACHELINE_SIZE) std::atomic<uint64_t> next_producer_record = 0;
    alignas(CACHELINE_SIZE) std::atomic<uint64_t> next_consumer_record = 0;

    alignas(CACHELINE_SIZE) uint64_t data[CAPACITY];
};

这现在保证了 producer_record 和 consumer_record 都会得到自己独一无二的缓存行。这确实浪费了一点缓存空间，因为现在这两个家伙每个基本上都是 64 字节而不是 8 字节。但就避免核心在同一个缓存行上反复争抢而言，这是一个相当大的胜利。

如果我们做了这个改变，这就是我们实际看到的结果。

  • 蓝色 (Naive): 顺序一致性版本。

  • 橙色 (Relaxed): acquire/release 版本。

  • 绿色 (Fast): acquire/release + 对齐版本。

仅仅因为伪共享，我们现在得到了大约 20% 的提升。你可以看到结果也变得更加稳定。这种稳定性，我认为主要是缓存效应。

是的，在这个特定的情况下，当我们正确地对齐数据并使用不同的内存排序时，有超过 20 倍的巨大差异。再次，这个队列和基准测试程序太简单了，对于真实世界的程序来说不现实。

但我们如何让基准测试更现实呢？我们可能想做的第一件事是，看看当数据变大时性能如何变化。

在这个图中，我们有 Naive 队列（顺序一致性）和 Fast 队列（acquire/release + 对齐）。

  • 64 字节记录: Fast 队列大约是 70M ops/s，仍然有 7 倍的提升。

  • 128 字节记录: 从顺序一致性的角度看，128 和 64 字节性能完全一样。我们的 acquire/release 版本大约是 50M，所以是 5 倍。

  • 256 字节记录: 我们仍然有 100% 的性能提升。你可以看到，即使在 256 字节，内存排序仍然比数据拷贝更昂贵。

  • 1KB 记录: 我们必须到一个完整的千字节，才能真正看到数据拷贝变得比内存排序更昂贵。即使在这种情况下，我们仍然节省了 25%（4M vs 3M）。

所以它实际上相当持久，即使在数据大小显著增加的情况下。

我们还能如何让它更现实？

多消费者队列

现在我们将进入多消费者队列的概念。我想非常清楚地说明我在这里想要基准测试的是什么。我想要基准测试的是我称之为广播队列（broadcast queue）。我曾在前一家公司花了很多时间，将每个数据记录广播给许多不同的消费者，这是一个非常有用的范式。

很多人期望的是一个工作队列（work queue），我们将传入的数据分配给一个协作线程池。我说的不是那个。在我称之为广播队列中，所有消费者线程接收所有数据。每个消费者维护其自己的独立队列索引。这在像语义分析、入侵检测、分类等工作流中非常有用，在这些情况下，你必须在相同的数据上运行许多不同的谓词。你基本上可以将其建模为为每种你想要运行的逻辑规则设置不同的消费者。而且它扩展得非常好。

我一直试图为此设置一个类比，你可以把它想象成一个单一的 Kafka 主题，只不过一切都完全在内存中并且是无锁的。

多消费者带来了一个新问题：如果有许多不同的消费者，生产者如何知道队列是否已满？我们需要在队列中增加一个新的实体，一个新线程，它的工作是识别最慢的消费者。我们称这个线程为收集器（collector）。这个线程持续地查看消费者索引，识别哪个索引值最低，并将其记录为自己的索引，成为循环缓冲区的新边缘。

我指的是这样的东西。这条黄色的虚线是收集器。我们现在队列中有多个消费者线程。这边是生产者。这些东西会继续前进，收集器不断地告诉生产者队列的边缘在哪里。你可以看到消费者自己并不真正关注彼此。我们有 C1 和 C2 在完全不同的位置。在第三张图中，C1 超过了 C2，只是因为我们从实现中得到的任何运行时排序导致了这种情况。

收集器类似于旧的消费者。生产者用它来决定队列中是否有可用空间。实现这个非常直接。

（观众提问）

问：如果有一个消费者滞后，这不会阻塞生产者吗？
答：是的。你谈论的是“车队效应”（convoy effect）。是的，如果你有一个消费者一直比其他所有消费者都慢，那将开始主导整个队列的速度。所以你必须做一些分析。我们当时实际做的是，会有一个东西随时间观察队列，并尝试调整进程优先级来给它更好的机会。根据你的系统，有些消费者可能运行成本太高。但这是个好问题。

问：你会谈到消费者之间的竞争吗？
答：再次，这就是我试图传达的，这些消费者之间不竞争。在我们设置这个队列的方式中，它们不分割数据。每个消费者接收每个记录。

问：但它们在生产者的数据上竞争。它们在 min 上竞争。它们必须更新 min，那是竞争。
答：嗯，收集器需要遍历所有消费者并找出最慢的那个。所以，如果在我们之前谈到的伪共享方面存在竞争，那很可能是在收集器和生产者之间。但无论如何，我仍然把所有这些数据都对齐了，所以我们不应该有伪共享问题。

好的，对于修改，我们现在有这个 ConsumerContext 结构体。我们可以对结构体本身使用 alignas 来确保所有这些都缓存对齐。每个消费者都有自己的索引。然后我们有生产者索引，和以前一样。现在我们有这个 slowest_consumer_index，这是我们的收集器。然后我们有一个消费者数组。

收集器的实现非常直接。我们只是遍历所有消费者索引，并试图找出哪个是最慢的。

/* 生成代码，仔细甄别 */

// 收集器线程
void collector(RingBuffer* rb) {
    while (true) {
        uint64_t slowest = -1; // UINT64_MAX
        for (size_t i = 0; i < NUM_CONSUMERS; ++i) {
            uint64_t cons_idx = rb->consumers[i].next_consumer_record.load(std::memory_order_relaxed);
            if (cons_idx < slowest) {
                slowest = cons_idx;
            }
        }
        rb->slowest_consumer_index.store(slowest, std::memory_order_release);
    }
}

有一点我真的很有兴趣听听大家的看法。我这里用 relaxed 排序写的。我从未见过它失败。但听到是否有人认为这不能是 relaxed 会很有趣。我们在这里做的是，我们遍历消费者。因为我们有单调递增的保证，我们知道没有消费者会降低它们的值。我真的不认为我们以什么顺序读取它们有关系。最坏的情况是，收集器取到了一些过时的值，并采取了一个过于保守的位置。但至少在我见过的任何情况中，都不应该出现我们得到不正确结果的情况。

（观众互动）

问：我认为如果你的生产者对消费者的副作用有内存排序依赖，你就没有 happens-before 关系了。
答：有道理。是的。在这种情况下，假设是它们是完全不相交的。至少我一直都是这样用的。

问：你试图在消费者中发生的事情和稍后可能在生产者中发生的事情之间建立一个 happens-before 关系。消费者必须已经说了它完成了那个记录，在生产者使用下一个记录之前。
答：嗯，我仍然在这里对实际的 slowest_consumer_index 有一个 release 存储。这是生产者最终会加载的。这在生产者和收集器之间创建了一个 happens-before。但是，在收集器和消费者之间没有 happens-before 关系。

问：你在 TSan 里运行过吗？
答：我运行过。它没有抱怨，但这不一定意味着什么。我的想法是，如果我在这里读到了过时的东西，除非你能遇到一种情况，即收集器不知何故看到了一个比它上一次迭代还小的值——我一直认为这是不可能的——我认为你得到的最坏情况是，收集器没有像它本可以的那样前进得那么远。

这就是我看到的结果。Naive（蓝），Relaxed（橙），Fast（绿）的含义和以前一样。你可以看到，当你开始向程序中添加更多线程时，伪共享问题被放大了。在这一点上，仅仅是伪共享，我们就得到了大约 4 倍的改进。所以对齐真的很重要。当我们添加更多线程时，它只是继续保持你所期望的趋势。即使在 32 个线程时，我们仍然从大约 1000 万提升到大约 5000 万，所以我们仍然从中获得了大约 5 倍的改进。

这是移动 128 字节记录的情况。即使在这种情况下，你仍然得到基本相同的趋势，从顺序一致性到 acquire/release 大约是 5 倍。你仍然在这里获得了巨大的节省。

volatile 与平台差异

有一件有趣的事，我知道你不能这样做，但这很有趣：这段代码现在在 x86 上发出了零个内存栅栏。我们真的还需要 std::atomic 吗？它给了我们什么？如果我们把它扔掉会怎么样？

现在我们可以定义我们的未定义行为队列。这是坏代码，不要写。但在 x86 上，我们现在做大家最喜欢的事：用 volatile 同步。我们声明的所有东西仍然是缓存对齐的，只是它们现在是 volatile 而不是 std::atomic。

/* 生成代码，仔细甄别 */

// 糟糕，未定义行为
struct UB_RingBuffer {
    // ...
    alignas(CACHELINE_SIZE) volatile uint64_t next_producer_record;
    alignas(CACHELINE_SIZE) volatile uint64_t next_consumer_record;
    // ...
};

在实现中，这个 atomic_signal_fence 是一个编译器屏障。它在运行时不发出任何东西。我只是非常努力地鼓励编译器不要破坏我的代码。但这没有运行时影响。除此之外，它完全一样。

我们从中得到的是这个。在 x86 上，它确实能工作。性能基本相同。比较汇编代码产生了基本相同的代码生成。我们是否证明了 std::atomic 是不必要的？标准做了所有这些工作都是白费力气吗？

那么，如果我们尝试在我现在正在演示的这台笔记本电脑上运行同样的代码会怎么样？你会发现它立即“砰”地一声爆炸了。这很好，它表明我们的断言确实起作用了。但到底哪里出错了？为什么这在 x86-64 上能行，但在 ARM64 上不行？

这归结于平台保证，这也是几位观众之前一直在暗示的。

  • Intel x86-64 架构规范：

    • 加载和存储不会与同类操作重排。

    • 存储不会与更早的加载重排。

    • 加载可能会与更早的对不同位置的存储重排。

    • 存储是传递性可见的。

    • 存储被其他处理器以一致的顺序看到。

这一大堆文字最终意味着，在 x86-64 上，acquire/release 语义基本上是免费的。内存子系统基本上就是为我们实现了它。

（观众：一个更好的说法是，在 x86-64 上，你一直在为 acquire/release 语义付费。）

答：非常正确。是的，100% 正确。

但这在像 ARM 和 PowerPC 这样更弱排序的平台上是不成立的。ARM 需要显式的 load-acquire 和 store-release 操作码来完成同样的事情。这些就是我们之前谈到的内存栅栏。

如果我们真的在 ARM64 上构建这个，我们会看到当我们存储到生产者索引时，我们有一个 STLR，这是一个实际的存储-释放指令。在下面，当我们加载生产者和消费者索引时，我们有一个 LDAR，这是一个实际的加载-获取操作码。这些就是使这能工作的栅栏。

我们知道我们需要这些栅栏，但实际问题是什么？我们在 ARM 上缺少了什么？显然是栅栏指令，但它们为什么重要？我们为什么真的需要这些栅栏？

  • 生产者乱序读取消费者的操作重要吗？不重要。

  • 生产者乱序读取收集器的操作重要吗？不重要。

  • 消费者乱序读取生产者的操作重要吗？是的，这是致命的。

这是关键部分。生产者做了两次存储：一次到数据数组，然后一次到生产者索引。问题是，在像 ARM 这样的架构上，我们可能会在看到对数据数组的更新之前，先看到了对生产者索引的更新。所以你可能会陷入这样的情况：消费者认为生产者已经前进了，但它接着去读取了陈旧的数据。

没有生产者端的 release 栅栏和消费者端的 acquire 栅栏，消费者可以在生产者队列更新可见之前看到生产者的移动。在这种情况下，消费者只是从上一次迭代中读取了垃圾。而 std::atomic 确保了我们在所有平台上总是得到正确的行为。它在 x86 上给了我们最快的可能，同时也确保了代码在其他平台上实际能工作。

对于 ARM，因为我时间不多了，我只展示了一个基准测试案例。这是我在笔记本上运行的结果。我移动的是 64 字节的记录。

  • Naive (蓝): 顺序一致性

  • Relaxed (橙): acquire/release

  • Fast (绿): 对齐的 acquire/release 我们可以看到，即使在 ARM 上，从顺序一致性到 acquire/release，我们仍然看到了 100% 的性能提升。所以这很酷。

最终优化：缓存的索引

最后一个优化。我快到时间了。但当我在为这个演讲做研究时，我遇到了这篇 2009 年发表的研究论文。它建议通过为生产者和消费者都引入缓存的索引来进一步优化缓存性能。它为生产者和消费者都增加了一个额外的缓存行对齐的索引，该索引持有对方索引的先前快照。这些缓存的副本只在生产者或消费者本将需要休眠时才更新。这解决了简单队列最后一个剩下的缓存未命中情况。

让我解释一下我的意思。

/* 生成代码，仔细甄别 */

struct CachedRingBuffer {
    // ...
    alignas(CACHELINE_SIZE) std::atomic<uint64_t> next_producer_record = 0;
    alignas(CACHELINE_SIZE) uint64_t cached_consumer_record = 0; // 消费者索引的本地缓存

    alignas(CACHELINE_SIZE) std::atomic<uint64_t> next_consumer_record = 0;
    alignas(CACHELINE_SIZE) uint64_t cached_producer_record = 0; // 生产者索引的本地缓存
    // ...
};

next_producer_record 是真正的生产者索引。但这个 cached_consumer_record 是生产者使用的消费者索引的缓存。next_consumer_record 是真正的消费者索引，而 cached_producer_record 是消费者对它的缓存。

有趣的是，我们不再有伪共享问题。但仍然正确的是，每当生产者去看消费者决定是否有空间，或者消费者去看生产者决定是否有数据时，这几乎总是缓存未命中。因为我们刚刚使它失效了。生产者每次增加它的索引，都会使消费者线程中它的 L1 版本失效。

这个方法的有趣之处在于，生产者在生产记录时，一开始会读取消费者记录，这时我们会产生一次缓存未命中。但然后它会尽可能地运行，直到碰到那个缓存的边界。只有到那时，它才会重新从消费者那里加载。消费者也做同样的事情。它缓存生产者索引，只有当它碰到它的缓存边界时，它才会从生产者重新加载并再次产生一次命中。

这真的非常酷。这是 perf 的输出。这是我之前基准测试我的简单、快速、小队列的结果（移动 64 位整数，已对齐）。

  • 优化前: L1 d-cache 未命中率只有 6%，这很棒。但 L1 未命中后，LLC (Last Level Cache) 未命中率大约是 33%。

  • 优化后: L1 d-cache 未命中率从 6% 降到 5%。但我们的末级缓存未命中率从大约 33% 降到几乎为零。

你会看到总的 L1 d-cache 加载次数从大约 300 亿增加到大约 900 亿，它们运行的时间相同。所以当我加载下一张幻灯片时，它完全疯了。我最初基准测试这个时，差点被食物噎住。对于这个非常非常小的队列，这带来了如此荒谬的差异，令人惊叹。我基准测试时简直不敢相信。

这显然是针对非常小的数据。这再次只是移动整数。

  • 64 字节值: 简单快速队列（无优化）从 75M ops/s 提升到 110M。

  • 128 字节记录: 从 50M 提升到 70M 左右。

所以随着数据变大，这个效果会迅速衰减。但有真实世界的用例会使用 8 字节的记录。比如你可能在传递指针。所以我对这个感到非常惊讶。对于小队列大小，这个优化带来了巨大的差异。我们的队列只传递整数，但一个真实世界的用例是传递指针。

有趣的是，根据我的研究，这个特定的优化似乎没有被 Folly 或 Boost 实现。我检查了这两个。也许有很好的理由。也许在某些情况下，缓存压力会成为比我看到的更主导的因素。我显然是在做一个微基准测试。但至少从我看到的来看，如果你在传递指针，这真的是一个荒谬的改进。

结论与问答

最后的一些警告：

  • 再次，这是一个优化效果特别好的数据结构。性能差异巨大的原因在于，这个数据结构与 acquire/release 语义非常契合。

  • 通常不可能移除所有的读-改-写操作，比如 fetch_add。在 x86 上，fetch_add 和 compare_and_swap 基本上总是需要一个完整的栅栏，无论你请求什么。所以，基准测试。

  • 有趣的事实: 我的 MacBook 上的缓存行大小显然是 128 字节。我说“显然”是因为我是从网上查到的，因为 Apple Clang 没有 std::hardware_destructive_interference_size。我不知道为什么。即使在标准 C++ 中，你有时也得不到标准的东西。奇怪的是，假设网上是对的，在我的测试中，最佳对齐是 64 字节，我完全不知道为什么。

总结论:

  • 为工作选择正确的内存模型，根据你的用例，可以产生巨大的差异。

  • 性能可能难以推理，有时会产生惊喜。

  • 标准内存模型做得非常出色，确保了你无法自己写出更好的代码（我真的试过，但没能做到）。

  • 松散原子操作可能非常难以推理，但在正确的上下文中是值得的。

谢谢大家。

(问答环节)

问: 当你为伪共享做对齐时，你似乎尝试对齐了两个消费者可访问的变量和两个生产者可访问的变量。你觉得……
答: 我甚至需要那么做吗？这实际上是个好观点。我可能不需要。只要我……是的，实际上我认为你是对的。我认为没有理由那样做。（观众的观点是，对于 cached_consumer_record 和 cached_producer_record，因为它们只被单个线程使用，所以不需要对齐，甚至可能不需要是原子的。）

问: 你能回到生产者索引更新了，但数组没有及时更新的部分吗？就是那个代码。你能交换那两条指令的顺序吗？
答: 问题是，从另一个线程的角度来看，它们可能会被交换。对于这个队列的结构，对数据数组的存储必须发生在这个增量之前。如果不是这样，一切都会崩溃。

问: 在你那个只有一个 relaxed 的例子中，你有没有尝试编译它，看看生成的代码是否有差异？
答: 那是一个在 ARM 上我可能会得到可测量差异的地方。在 x86 上，再次，它都是 acquire/release。我没有不幸地去调查那个。

问: 如果不是用缓存，而是每 10 个元素发布一次呢？
答: 哦，就像你批量生产一样？你可以试试。我想这再次取决于你的用例。如果你关心确保所有东西都被即时读取，那可能会是个问题。这是一个有趣的想法。我喜欢这个缓存优化的原因是，我认为它基本上在所有情况下都有效。

问: 你做的这些优化，如果应用到一个栈上效果会如何？
答: 哦。栈更有问题，因为你可以上下移动。我的很多优化都非常依赖于我们有单调递增的索引。
观众: 栈的主要问题是所谓的 ABA 问题。
答: 是的，完全正确。由于他用的是完整的 uint64_t，你永远不会再次看到同一个 uint64_t。如果你真的把它们截断到数组的大小，就会有 bug。ABA 问题是，一个线程快照了一个值，被挂起，别人进来改变了值然后又改了回去。线程醒来说，“哦，还是一样的”，然后你就完蛋了。

问: 你展示了一些传递 64 字节甚至更大元素的例子。你说在生产环境中人们传递指针。如果你想 malloc 你的元素，你有什么建议吗？
答: 这是个好问题。因为是的，说到底，传递指针是可行的。但问题是，如果你调用 malloc，那会在堆上加锁，那就什么都不重要了。我能建议的主要事情是预分配。有一个内存池，从中分配，然后传递指针。但你确实需要小心，确保获取那些指针的成本不要高到完全掩盖了队列本身的成本。
观众: 你需要把指针传回给生产者。
答: 是的，你需要某种方式让生产者意识到指针可以被重用了。我在这里没有真正深入垃圾回收。可以想象，你可以有一个东西，让收集器去标记中间距离的所有东西。但你确实需要一种方式来知道你可以回收。

还有其他问题吗？好的。谢谢大家。谢谢。