可重启序列

# 可重启序列 来源：https://justine.lol/rseq/ 2026年5月31日 @justine 的网页 (https://justine.lol/index.html) [](https://justine.lol/rseq/rseq.png) 目前系统编程前沿最棒的秘密是 Linux 4.18+（约2018年）引入的可重启序列（restartable sequences，简称 rseq）。它们能让你创建无需锁或原子操作的线程安全数据结构，且可扩展到多核微处理器。目前只能在 Linux 上通过手写汇编代码使用 rseq。但我相信未来所有操作系统都会更新以支持 `rseq()`，所有系统编程语言都将重新设计以表达可重启序列，所有数据结构库都会重写来使用它们。 目前我见过使用 rseq 的软件只有 tcmalloc、jemalloc、glibc 和 cosmopolitan。但这种情况注定会改变，因为128核甚至192核的微处理器正在变得廉价。例如： - 在我的 **$160 树莓派 5** (https://amzn.to/3TYRti8)（4核）上，rseq 使我的 `malloc()` 实现**快3倍**，相比为每个线程分配一个 dlmalloc mspace。对大多数开发者来说，这种提升可有可无。 - 但在我的 **$4,834 System76 Thelio Astra 搭载 Ampere 的128核3GHz Altra CPU** (https://system76.com/arm) 上，rseq 使 cosmopolitan `malloc()` **快34倍**（相比使用 `sched_getcpu()%32` 在 mspace 数组上分片操作）。 - 在我的 **$17,628.55 AMD Threadripper Pro 7995WX** (https://justine.lol/rseq/threadripper.html)（96核）上，rseq 使我的 `malloc()` **快43倍**（相比使用相同的 `sched_getcpu()` 互斥分片技术）。 没有上面这类工作站的系统程序员会像恐龙一样被落下，无法摘取10倍性能优化这颗低垂的果实。例如，如果我没有花大价钱买96核CPU，去年我就无法实现**矩阵乘法的加速** (https://justine.lol/matmul/)。那让我穷了几个月（因为当时更便宜的 Ampere 工作站还没上市），但非常值得——我的工作获得了**媒体报导** (https://www.phoronix.com/news/Llamafile-0.7)，在**AI社区一举成名** (https://x.com/jartine/status/1777094783745556876/photo/1)，帮助我的项目被**32%的组织采用** (https://x.com/jartine/status/1940859907567505498)，甚至还让我拿到了谷歌的工作机会，在 Gradient Canopy 团队改进 TPU 性能以支持 Gemini。 如果你确实拥有这类微处理器，那么可重启序列将是你利用其能力的最重要技巧之一。本教程将展示它们的工作原理，并提供一个可立即使用的推入和弹出实例。 ## 可重启序列解决了什么问题？ 每当 Cosmopolitan C 运行在 Linux 系统上创建线程时，它会发起一个 `rseq()` 系统调用，为内核提供32字节的 TLS 内存。随后，在该线程的整个生命周期内，每当线程被重新调度时，内核会将 CPU 编号更新到 TLS 内存中。我发现这对改进我的 `sched_getcpu()` 实现立竿见影。现在只需一条1纳秒的宽松 `mov` 指令就能获取 CPU 编号，而之前需要等待整整一微秒的 `getcpu()` 系统调用。 但这还不是全部。rseq TLS 内存中还有一个字段，允许线程向内核发送信息。通常 `rseq_cs` 字段为 `NULL`，但可以更新为一个指针，指定程序中一段汇编指令序列。当内核抢占你的线程并试图将其移到另一个 CPU 时，它会注意到你的 `rseq_cs` 非空，并检查程序计数器（x86 上的 %rip）是否在指定区间内。如果是，内核将强制线程跳转到你指定的中止处理程序，该处理程序可以执行诸如跳回函数开头重试操作等动作。 这就是我们需要它的原因。假设你有一个这样的 GIL： ```c static pthread_mutex_t lock; static struct List *list; ``` 如果你用它保护数据结构，那么在数十核的系统上会很慢，因为任何时候只有一个线程能持有锁。于是你可能想到用原子操作创建一个无锁链表。如果只是推入，这很简单；但如果还要弹出，就需要用类似下面的东西来解决**ABA 问题** (https://en.wikipedia.org/wiki/ABA_problem)： ```c #define MASQUE 0x00fffffffffffff0 // 支持 pml5t 和 malloc 的内存 #define PTR(x) ((uintptr_t)(x) & MASQUE) #define TAG(x) ROL((uintptr_t)(x) & ~MASQUE, 8) #define ABA(p, t) ((uintptr_t)(p) | (ROR((uintptr_t)(t), 8) & ~MASQUE)) #define ROL(x, n) (((x) << (n)) | ((x) >> (64 - (n)))) #define ROR(x, n) (((x) >> (n)) | ((x) << (64 - (n)))) struct List { struct List *next; // ... }; _Atomic(struct List *) list; void push(struct List *elem) { struct List *tip; for (tip = atomic_load_explicit(&list, memory_order_relaxed);;) { elem->next = (struct List *)PTR(tip); if (atomic_compare_exchange_weak_explicit( &list, &tip, (struct List *)ABA(elem, TAG(tip) + 1), memory_order_release, memory_order_relaxed)) break; pthread_yield_np(); } } struct List *pop(void) { struct List *tip, *elem; tip = atomic_load_explicit(&list, memory_order_relaxed); while ((elem = (struct List *)PTR(tip))) { if (atomic_compare_exchange_weak_explicit( &list, &tip, (struct List *)ABA(elem->next, TAG(tip) + 1), memory_order_acquire, memory_order_relaxed)) break; pthread_yield_np(); } return elem; } ``` 问题在于这很可能一样慢，甚至更慢。仅仅让多个核共享同一块64字节的内存（即缓存行），就会导致 CPU 内部本质上使用互斥锁，而且 CPU 的内部互斥锁很可能不如你在用户空间实现的好。 一种更聪明的做法是对数据结构进行分片，让每个 CPU 拥有自己的区域。 ```c static struct { alignas(64) struct List *list; } lists[CPU_SETSIZE]; ``` 然后只需用 `sched_getcpu()` 索引 `lists` 数组即可。问题是这行不通。我们仍然需要互斥锁，因为操作系统可能会在加载 CPU 编号和之后的数据修改之间抢占并移动你的线程。 ```c static struct { alignas(64) pthread_mutex_t lock; struct List *list; } gil[CPU_SETSIZE]; ``` 修复后，我们似乎又回到了原点，只是现在要管理1024份副本。不过，尽管看起来一样，这段代码实际上要优化得多。通过为每个 CPU 设置独立的互斥锁，我们确保了它们只在极端情况下才会被争用。这很重要，因为争用锁与非争用锁的区别如同白昼与黑夜。使用像 **nsync** (https://justine.lol/mutex/) 这样优秀的互斥库，争用锁操作至少花费 **200纳秒**。但非争用的加锁/解锁操作仅需约15纳秒。我们还使用了 `alignas(64)` 确保每个 CPU 的指针位于独立的缓存行上，从而将硬件内部争用的概率降到极低。 但如果只是推入和弹出，与线程本地链表的推入/弹出相比（仅需约1纳秒），那15纳秒仍然是巨大的开销。所以我们真正想要去掉互斥锁。唯一的障碍是一个极少出现的边界情况：操作系统在我们修改链表的那几条汇编指令序列期间中断了线程。那么如何去掉互斥锁呢？ 这时你可能想到需要一个 RTOS 来保证线程不会被抢占，或者现有 OS 可能有 `sched_setscheduler()` 策略让你重获一些控制权。对于专门的部署，这或许可行。还有 `sched_setaffinity()`，它在 Linux、FreeBSD 和 Windows 上都受支持。如果你愿意将线程固定到特定 CPU，这对特定应用可以工作。但这些人们过去为控制 OS 调度器而发明的所有方法，如果你的程序执行不如预期，都可能是灾难性的。 这就是为什么 Linux 现在提供了 `rseq()`，一个更加明智的解决方案。有了可重启序列，你实际上可以同时去掉互斥锁和原子操作，同时 OS 继续完全抽象调度。其工作方式是：当你的程序进入不希望被中断的临界区代码时，你通知内核。这个临界区可能最多10条汇编指令。第一条汇编指令应该是设置 `rseq_cs` 字段的移动指令。最后一条指令必须是修改全局数据结构的操作。可以把它想象成一个非常微小的数据库事务。之所以快，是因为与内核的双向通信是通过共享内存进行的。 ## 示例1：构建最快的点击计数器 (https://justine.lol/rseq/#hitcounter) 下面是对可重启序列的温和介绍。我们将构建一个只加一个数的程序。这大概是最简单的事情了。想象你有一个每秒数十亿访问量的博客，托管在你从零开始编写的多线程 Web 服务器上，你需要跟踪访问量。在这种情况下，我想到了五种构建点击计数器的方法（使用 **cosmocc** (https://justine.lol/cosmo3/) 编译示例代码）。 [](https://justine.lol/rseq/threadripper.html) **96核 AMD Ryzen Threadripper Pro 7995WX (x86-64)** | wall time (ms) | wall ops/sec | user time (ms) | system time (ms) | cpu ops/sec | 实现 | |---------------|--------------|----------------|------------------|-------------|------| | 62,461 | 30,739k | 118,631 | 11,744,462 | 161k | hitcounter-mutex.c (https://justine.lol/rseq/hitcounter-mutex.c.html) (glibc) | | 29,389 | 65,331k | 34,094 | 13,259 | 40,547k | hitcounter-mutex.c (https://justine.lol/rseq/hitcounter-mutex.c.html) (cosmo) | | 23,412 | 82,009k | 4,366,203 | 0 | 440k | hitcounter-atomic.c (https://justine.lol/rseq/hitcounter-atomic.c.html) | | 543 | 3,535,912k | 93,274 | 0 | 20,585k | hitcounter-shard.c (https://justine.lol/rseq/hitcounter-shard.c.html) | | 209 | 6,000,000k | 1,150 | 1 | 21,652,324k | hitcounter-rseq.c (https://justine.lol/rseq/hitcounter-rseq.c.html) | | 72 | 74,285,714k | 0 | 1 | 1174,545,455k | hitcounter-affinity.c (https://justine.lol/rseq/hitcounter-affinity.c.html) | 之前我说 rseq 让我的代码快了34倍或43倍，重要的是我比较的是我的 `malloc()` 实现的**可移植**版本，它已经为多核系统高度优化了。如果把 rseq 与真正朴素的解决方案（比如用 glibc 互斥锁保护递增操作）比较，那么根据 CPU 时间消耗，rseq 实际上可以**快一百万倍**。听起来像开玩笑，但并非如此，因为我问过的朋友中有一半告诉我，他们本能地会先用互斥锁。 现在探讨上面列出的五种方法，我们可以看到只有三种值得考虑： - **分片**是当你需要跨所有操作系统可移植性时最好的选择。我们使用 `cosmo_shard()` 函数指针来实现。在现代 Linux 上这会使用 `__get_rseq()->cpu_id`，回退到诸如通过全局描述符表 `lsl`、`rdpid`、`rdtscp` 或 `sched_getcpu()`，如果都不可用，最后会使用 `murmur3(gettid())%32`。 - **亲和性**绝对是最快的，但它需要微观管理所有线程。这对库作者来说行不通。对应用作者来说可能也不是好主意。如果尝试这样做，我会害怕自取灭亡。不过，我可以想象在某些情况下它可能是合适的。但重要的是要注意 GCC 作弊了。通过消除所有 volatile 操作，我们利用编译器对数学的了解找到了递增的闭式解——也就是加法。所以这完全不是作弊。如果我在 `hitcounter-affinity.c` (https://justine.lol/rseq/hitcounter-affinity.c.html) 示例中使用 `alignas(64) volatile long x`，那么它的速度会与 rseq 示例完全相同。 - **可重启序列**做出了优越的权衡。它们目前只适用于现代 Linux，所以如果你在构建开源库之类的东西，也需要支持其他策略。它需要以更高难度编写代码。恐怕 LLM 还没有聪明到能帮助你构建可重启序列。但我相信未来编程语言会改变，让我们能优雅地表达可重启序列，类似于 C11 为原子操作引入的编译器 API。 现在转到我的 ARM 工作站。  **System76 Thelio Astra 搭载 Ampere 的128核3GHz Altra CPU (ARM64)** | wall time (ms) | wall ops/sec | user time (ms) | system time (ms) | cpu ops/sec | 实现 | |---------------|--------------|----------------|------------------|-------------|------| | 219,484 | 5,832k | 322,259 | 15,790,712 | 79k | hitcounter-mutex.c (https://justine.lol/rseq/hitcounter-mutex.c.html) (glibc) | | 212,005 | 6,038k | 144,163 | 67,841 | 6,038k | hitcounter-mutex.c (https://justine.lol/rseq/hitcounter-mutex.c.html) (cosmo) | | 17,924 | 71,413k | 2,162,867 | 0 | 592k | hitcounter-atomic.c (https://justine.lol/rseq/hitcounter-atomic.c.html) | | 417 | 3,069,544k | 42,972 | 0 | 29,787k | hitcounter-shard.c (https://justine.lol/rseq/hitcounter-shard.c.html) | | 393 | 2,820,513k | 2,966 | 1 | 61422,861k | hitcounter-rseq.c (https://justine.lol/rseq/hitcounter-rseq.c.html) | | 121 | 06,666,667k | 15 | 1 | 80,000,000k | hitcounter-affinity.c (https://justine.lol/rseq/hitcounter-affinity.c.html) | 上表中，ops/sec 列与 Threadripper 结果最直接可比，因为它们按工作负载缩放。ops/sec 越高越好。观察这些数字，几点值得注意： 1. Ampere 的 ARM Altra CPU 拥有非常快的原子操作。ARM 的一个优点是拥有更灵活的内存模型，`hitcounter-atomic.c` (https://justine.lol/rseq/hitcounter-atomic.c.html) 利用 `atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed)` 利用了这一点。得益于宽松排序，我们得到了一条 `ldadd` 指令，无需管理内存屏障。在 x86 上无法做到，因为 `xadd` 总是强排序。更有趣的是，即使我指定 `memory_order_seq_cst`（对应 `ldaddal`），我的 Altra CPU 仍然明显比我的 Threadripper 快。我怀疑可能是超线程导致了 Threadripper 的问题，因为我的 Threadripper **声称**有192个 CPU。 2. Cosmopolitan 对 POSIX 互斥锁的实现非常复杂。它比 glibc 做得好，但我认为可以在 ARM 微处理器上改进我们的实现以降低延迟。 3. 其余的数字差异大体上与价格差异相称。 4. 使用可重启序列把我的3GHz CPU 变成了33GHz CPU。 5. 使用互斥锁把我的3GHz CPU 变成了219MHz CPU。 我认为 Ampere 的 ARM CPU 很酷的一点是：我其实是 x86-64 的超级粉丝。我一直都是。