Restartable Sequences

May 31st, 2026 @ justine's web page

The best kept secret at the frontier of system programming right now is the Linux 4.18+ (c. 2018) concept of restartable sequences or rseq for short. They allow you to create thread-safe data structures without locks or atomics which scale to microprocessors with many cores.

It's currently only possible to use rseq on Linux using handwritten assembly code. However I believe in the future, all operating systems will be updated to support rseq(), all system programming languages will be redesigned to be able to express restartable sequences, and all data structure libraries will be rewritten to use them.

So far the only software I've seen using rseq is tcmalloc, jemalloc, glibc, and cosmopolitan. That's destined to change now that microprocessors with 128 or even 192 cores are becoming inexpensive. For example,

On my $160 Raspberry Pi 5 (which has 4 cores), rseq makes my malloc() implementation 3x faster versus having a dlmalloc mspace assigned to each thread. For most developers, that's a take it or leave it kind of improvement. However,

On my $4,834 System76 Thelio Astra with Ampere's 128 core 3GHz Altra CPU, rseq makes cosmopolitan malloc() go 34x faster (compared to sharding ops over an array of mspaces using sched_getcpu()%32)

On my $17,628.55 AMD Threadripper Pro 7995WX with 96 cores, rseq makes my malloc() 43x faster (versus using that same sched_getcpu() mutex sharding technique)

System programmers who don't have a workstation like the ones above are going to be left behind like a dinosaur, with no opportunity to pluck the low hanging fruit of 10x performance optimizations. For example, I wouldn't have been able to pull off the speedups I made to matrix multiplication last year if I hadn't splurged on a 96 core CPU.

It put me in the poor house for a few months (since the cheaper Ampere workstations weren't available it the time) but was so worth it, since my work received press coverage, it made me famous in the AI community, it helped my project get adopted by 32% of organizations, and even earned me a job offer from Google to work in their Gradient Canopy improving TPU performance for Gemini.

If you do have one of these microprocessors, then restartable sequences are going to be one of the most important tricks you'll use to exploit its capabilities. This tutorial will show you how they work, and provide you with a concrete example for pushing and popping which can be immediately useful.

What Problems Do Restartable Sequences Solve?

Whenever the Cosmopolitan C runtime creates a thread on a Linux system, it issues an rseq() system call which gives the kernel 32 bytes of TLS memory. Then, for the remainder of that thread's life, the kernel will update the TLS memory with the CPU number whenever the thread is rescheduled. I found that to be immediately helpful for improving my sched_getcpu() implementation. Since now it just needs a 1 nanosecond relaxed mov instruction to get the CPU number, whereas before I needed to wait an entire microsecond for the getcpu() system call.

However it gets better. There's a second field in the rseq TLS memory that allows the thread to send information back to the kernel. Normally the rseq_cs field is NULL, but it can be updated with a pointer specifying a sequence of assembly instructions in your program. Now, whenever the kernel preempts your thread and tries to move it to a different CPU, it'll notice your rseq_cs is non-null, and will check the program counter (a.k.a. %rip on x86) to see if it's currently within the specified interval. If that's the case, then the kernel will force the thread to jump to an abort handler you also specify, which can do things like jump back to the beginning of the function to retry the operation.

Here's why we need that. Let's say you have a GIL like this:

static pthread_mutex_t lock; static struct List *list;

If you're using that to protect your data structures, then it's going to go slow on systems with dozens of cores, since only a single thread can hold the lock at any given moment. So you might think, let's create a lockless list using atomics. That's pretty simple if we're only pushing, but if we want to also be able to pop, then we'd need to account for the ABA problem with something like the following:

#define MASQUE 0x00fffffffffffff0 // supports pml5t w/ malloc'd memory #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; }

The issue is this will likely go just as slow if not slower. The mere act of sharing the same 64-byte region of memory (a.k.a. cacheline) between multiple cores, causes the CPU internally to basically use a mutex, and chances are the CPU's internal mutexes aren't as good as the ones you've implemented in userspace.

So one potentially smarter approach is to shard the data structure, so each CPU gets its own area.

static struct { alignas(64) struct List *list; } lists[CPU_SETSIZE];

Then all you have to do is index the lists array using sched_getcpu(). The issue is that doesn't work. We still need a mutex, due to how the operating system might preempt and relocate your thread twixt the cpu number load and any mutations you've made.

static struct { alignas(64) pthread_mutex_t lock; struct List *list; } gil[CPU_SETSIZE];

So now that we've fixed things, it looks like we ended up back where we started, except now we have to manage 1024 copies. However, despite appearances, this code actually is much more optimal. By having a separate mutex for each cpu, we've ensured they'll only be contended when we hit corner cases. It matters because the difference between a contended versus uncontended lock is like the night and the day. With a great mutex library like nsync a contended lock operation will cost you at least 200 nanoseconds. However an uncontended lock/unlock operation only costs about 15 nanoseconds. We further use alignas(64) to ensure that the pointer is placed on a separate cacheline for each CPU, thereby reducing any hardware internal contention to a very low order of probability.

However if all we're doing is pushing and popping, then that 15 nanoseconds is still an enormous cost compared to a thread local linked list push or pop which only costs about a nanosecond. So we really want to get rid of the mutex. The only thing standing in our way is a fringe rarely-occurring corner case where the operating system interrupts our tiny sequence of a few assembly instructions during which we mutate the list.

So how do we get rid of the mutex? At this point, you might be thinking you need an RTOS which guarantees your thread won't be preempted, or perhaps your existing OS might have a sched_setscheduler() policy that gives you back some semblance of control. For specialized deployments, that might work. There's also sched_setaffinity() which is supported on Linux, FreeBSD, and Windows. That will work for a given application, if you feel comfortable pinning your threads to particular CPUs. But all these approaches folks have invented in the past for controlling the OS scheduler can be potentially disastrous if your program's execution doesn't go the way you planned.

This is why Linux now provides rseq() which is a much more enlightened solution. With restartable sequences, you actually can get rid of both the mutex and atomics, while the OS continues to fully abstract scheduling. The way it works is you advise the kernel whenever your program enters a critical section of code that you don't want interrupted. It's probably going to be maybe 10 assembly instructions tops. The first assembly opcode should be a move instruction that sets the rseq_cs field. The last instruction needs to be the thing that makes the modification to your global data structure. Think of it sort of like a really tiny database transaction. What makes it go fast, is that the bidirectional communication with the kernel happens via shared memory.

Example No. 1: Building the Fastest Hit Counter

Here's your gentle introduction to restartable sequences. We're going to build a program that just increments a number. Since that's probably the simplest thing imaginable.

Imagine you have a blog that gets billions of visitors per second, which is hosted on a multi-threaded webserver you wrote from scratch and you need to track visits. In that case, I can think of five ways you could build your hit counter (using cosmocc to build the example code).

96 core AMD Ryzen Threadripper Pro 7995WX (x86-64)

walltime (ms) wallops/sec usertime (ms) systemtime (ms) cpuops/sec implementation

62,461 30,739k 118,631 11,744,462 161k hitcounter-mutex.c (glibc)

29,389 65,331k 34,094 13,259 40,547k hitcounter-mutex.c (cosmo)

23,412 82,009k 4,366,203 0 440k hitcounter-atomic.c

543 3,535,912k 93,274 0 20,585k hitcounter-shard.c

20 96,000,000k 1,150 12 1,652,324k hitcounter-rseq.c

7 274,285,714k 0 11 174,545,455k hitcounter-affinity.c

Earlier when I