Restartable Sequences
2 hours ago
- #performance-optimization
- #system-programming
- #linux-kernel
- Linux 4.18+ introduces restartable sequences (rseq) for lock-free, scalable thread-safe data structures on multi-core systems.
- rseq is currently used by few software (tcmalloc, jemalloc, glibc, cosmopolitan) but is poised for wider adoption with 128+ core CPUs.
- rseq provides significant performance gains, e.g., malloc can be 34x-43x faster compared to traditional sharding methods.
- The mechanism involves TLS memory updated by the kernel with CPU IDs, and an rseq_cs field to define critical sections that restart on preemption.
- A practical example demonstrates push/pop operations for a sharded linked list using rseq, eliminating locks and atomics.
- Benchmarks on 96-core AMD and 128-core ARM systems show rseq outperforms mutex, atomic, and sharded approaches in hit counter scenarios.
- rseq assembly code requires careful handling, including defining rseq_cs structures and abort handlers for restartable sequences.
- Cosmopolitan Libc uses rseq in its malloc implementation, with environment variables to control rseq usage for cross-OS compatibility.