Restartable Sequences
justine.lol
justine.lol
“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.”
And 2 more ops per rseq.
But rseq's are certainly cool.
(Based on my reading of the LWN article rwmj posted).
There is a time-slice extension feature in the works that's roughly "please let me finish this critical section before you interrupt me". But a hard guarantee that userspace code won't be interrupted is probably untenable in a preemptive multitasking system.
I wonder why this is the case. Considering modern (personal) computers have more cores than available work (or won't starve other processes even if they hog a part of the available cores), I would not think it so horrible for an OS to offer a guarantee to some (maybe specially privileged) processes, that as long as they don't wait on a resource, they won't be interrupted.
We also have a perfectly workable model for describing such a state to the OS - priority inversion. Imagine a 'god mutex', which when acquired would boost your thread's priority to the maximum - as if the 'god process' would be waiting for said mutex and as long as your thread held it, it couldn't continue working, until your thread finished using it.
I think it would be a neat feature for certain real-time(ish) scenarios, like audio/video processing.
I think a lot of modern OS facilities are catering towards a world with much scarcer resources than our current one, for example, it would be perfectly fine for a process to assume at least a core part of its data is always in RAM and can't be swapped out.
When you get into low-level systems, like kernels, a lot of the need for special privileges comes from having to have these guarantees, which could be granted nowadays on a much more lenient basies.
The way I read it, it either runs to completion in one go, or gets restarted from the beginning. This means the sequence as a whole isn't executed atomically, as the already-executed instructions during an interrupt aren't rolled back.
It can be used to build atomic actions, but it is up to the developer to create a sequence of instructions where the very last instruction "commits" the entire operation, with the side-effects of partial execution being harmless.
With rseq, we can allocate in any userland process one instance of a given synchronisation data structure per each CPU. It's important to understand that userland code accessing per-cpu data structures cannot prevent being scheduled away from a CPU and being replaced by another thread (kernel code can block scheduler for short critical sections). Such a replacement thread may subsequently corrupt that same data that was still in the middle of the transaction. But we can make a subset of transactions safe at least: If a transaction gets committed in a single (final) atomic instruction, and we get kernel support for this transaction to be restarted in case there has been a schedule mid-way, this is a guarantee that at the time of commit, the entire transaction hasn't been interrupted by the scheduler. I.e. a kind of "mutual exclusion" guarantee.
Did I get that right?
But agreeing with you, I've done big optimization stuff for multicore servers (not as many cores, but same kind of work) and my workstation was something small with not even the same os. I don't need the big machine on my desk to understand the concepts. I just need the big machine to check my work. For me, that's always been a production machine, sometimes a production machine taken out of rotation for pre-validation before running on production load. I guess I should mention, I work on applications specifically, and libraries and kernels as it relates to making whatever my application is work better. I also don't have a problem with pinning threads to cpus... but my applications are usually one big program that fills the system. Someone writing a general purpose library has a harder time.
Of course, if you want to do this kind of work and you don't have your own production load, you're going to have to borrow, rent, or buy a big machine. It doesn't need to be your workstation though. I hate working with cloud nonsense, but if your tests are short, and you do the upfront work to make your images start fast, you can probably save a lot of money by renting spot instances when testing ... I don't know if you can do spot instances of bare metal though, so you're probably stuck with vm overhead.
I understand why the author deleted it !
Your bad faith reading of that article says otherwise. It's bleedingly obvious that it's satire. Do you think people seriously ask for donations to fund a private airplane?
$20K of gear isn't that much if you're an independent developer, and if you're working for others as such in the US, and you're not a financial basket case, it's doable. She even says "It put me in the poor house for a few months" so she made sacrifices to get there. You can too, if you want to. Why the envy?
To the contrary, so you really seem to have a problem with her.
[references https://web.archive.org/web/20260529122658/https://justine.l... ]
Perhaps in the USA if you have a well-paid job at a MAMAA company ...
Also, it was pre-2025 (before she got her job at Gradient Canopy), so long before asking for donations.
Finally, if you read the actual donation request, you can see she is trying to make a living doing open source, and is being honest about what the money is going to. Why is that an issue?
And if she's even half the genius she's claiming to be, why aren't the big tech companies in a bidding war over who get to pay her a million-dollar salary?
From what I've read of her in the past she seems to be a pretty damn good developer. But in the open source world those are a dime a dozen. If you want to make a living off of it you've got to market yourself, and this... isn't how you do that.
Not exactly. Very few people in recent decades have achieved anything comparable to αcτµαlly pδrταblε εxεcµταblε and Cosmopolitan libc - they're in the category of "that should not even be possible". Of course, Tunney's work doesn't touch Fabrice Bellard in terms of sheer breadth and impact, but they're arguably in the same category.
A libc which is flexible enough to select specific code paths depending on runtime conditions? Every libc already does this to make use of the latest hardware features[1], using the same approach for platform-specific code isn't a huge stretch - you're basically doing a lightweight WINE.
Her work is definitely impressive, but it isn't magic. You'll see similar stuff if you look into the demoscene, or the IOCCC, or a decent chunk of the talks at CCC. And it's not like APE and Cosmo libc are seeing massive adoption: the people who want portability but can't even compile for multiple platforms are probably happier with something like Java due to the better ecosystem support.
[0]: https://en.wikipedia.org/wiki/Polyglot_(computing)
[1]: https://www.phoronix.com/news/Glibc-More-AVX-512-October-202...
- a fully cross-platform libc with cross-platform support built into the output binary, integrated into clang and gcc toolchains
- not just cross-platform, but also cross-architecture: output binaries work unmodified on both AMD64 and ARM64 architectures
- sheer number of executable format compatibilities: it's a polyglot across macOS, linux, windows, 3 BSDs, and a bootable BIOS target
- polyglot not just for executable outputs, but also for PKZIP. You can open and modify an executable using common zip file editors. And post-hoc zipped-in data can be accessed/modified by code in the executable using interfaces in cosmopolitan libc
- Zip polyglot can be used to create portable embeddable code-packaged interpreters where the code being interpreted is loaded/executed from zipped-in data. One example: RedBean is a very high-performance APE-packaged web server that serves data in its zip archive and hosts web service code from Lua scripts in its zip archive. Built-in library enables Lua code to store/retrieve data from zipped-in SQLite databases.
The comparison to the demoscene and IOCCC is apt, but this is at another level because it's all production-ready. The Llamafile format is an APE binary compiled with Cosmopolitan libc with model weights zipped into it.
But then they go on to take a Gemini job[1] so I dunno, more consolidation than consolation perhaps.
[1] TFA says “job offer” but another comment[2] says that they work there.
https://github.com/compudj/librseq
This has helpers for common use cases like counters and linked lists. You shouldn't need to write assembly at all to use rseq in most applications.
Is it claiming that?
The syscall these days is invoked by libc not the program; libc provides access to some symbols that let the program execute rseqs as well.
The key insight is that the preempter can introspect the program counter of the code being preempted (which is now stable since it was preempted) and act accordingly. The simplest mechanism is to reset their program counter if in a critical section. The more generic mechanism is to jump them to a supplied address. This allows you to do things like hard abort and more.
You can further remove the need for the preempter to understand the preempted code by having the preempted code create a self-introspection code snippet and supplying that with the program counter at preemption. So the preempter just vectors them to their own code which knows how to interpret its own state at any preemption point.
I fully agree that rseq should be more easily available to Linux developers, though.
Anyone with an informed opinion on this statement? It's seems counter intuitive (npi).
If you remove the 64 byte alignment (which forces each counter variable onto a separate cache line) from hitcounter-shard.c you ought to be able to see the performance difference for yourself.
The Q is: is it true the CPU mutexes are actually slower than those implemented in userspace?
EDIT: or maybe you're asking if introducing an explicit userspace mutex is better than a lockless algorithm with false sharing issues. The answer is that it's workload dependent but it definitely can be.
OP > 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.
The claim by OP is that "chances are" that userspace mutexes are better than CPU's internal mutexes. So either h/w guys are (for a first) lagging s/w folks and using outdated approaches to creating a mutex in hardware, OR, we somehow must use an inferior approach when implementing a mutex in a CPU, OR, ..
How is it possible that a hardware implementation of an algorithm could be slower than its software variant, and that in "userspace" and not even the kernel.
What Justine probably meant was an apples to oranges comparison: in userspace, you can sometimes add constraints that allow for a faster algorithm whereas the cpu generally has to assume the worst.
That being said, if you look through this thread you'll find similar issues with OP's phrasing. A fine engineer / hacker, but too much 4chan troll in my book.
MESI takes a non-trivial amount of time to run. It's usually mediated at the L3 cache, which is frequently clocked slower than the main core, so it's a non-trivial number of cycles for a MESI state transition to happen (think at least ~40 cycles).
Compare that with a cacheline that's already Exclusive on a core: Writing to this cacheline is a pure L1 cache write at ~1 cycle, no MESI involved, no L3 cache involved.
Note that the typical userspace space mutex (some memory location that's modified by compare-exchange) is implicitly relying on MESI whenever two cores race for the lock, or whenever a lock is release on one core and then taken on another, etc etc.
So if your userspace coherency can be handled via some sharding that avoids needing MESI to run, it can go much faster than relying on the CPU's "internal mutex" aka MESI.
To directly address "is it possible that a hardware implementation of an algorithm could be slower than its software variant": The point is that with RSEQ, you can write a _different_ algorithm that's faster than an implementation relying on hardware mediated MESI. Instead of having memory that's accessed for a bunch of different cores, there's a chunk of memory per core, and each core almost always writes only to it's allocated chunk of memory.
Even without rseq(2) you're looking at a "different algorithm". For one, a proper userspace mutex allows the excluded threads to be descheduled and the core can be repurposed to run other tasks, rather than hammering away at the contended cache line.
This happens on every memory access, so the thing you want to avoid is ping ponging writeable cache lines between CPUs (especially before you have a chance to actually write it) - LL/SC instructions sit on top of these protocols and allow instructions to tell is a cache line had been "stolen" before you have a chance to write it
You can do better than that, for example, I remember reading an article about some game engine, which had a static scheduling of tasks on each frame, so, for example there was no overlap in time between thread A and thread B referencing the same piece of memory. The whole scheme worked the exact same every frame, it was truly free, and there was a zero percent chance of memory inconsistencies.
Something like
greenbean
ftp -vvd4o/dev/stdout http://127.0.0.1:8080
Also why doesn't redbean do TLS1.3
And rusage "wall time" output seems to be wrong
Too much emphasis on Unicode for me, it's off-putting
I like consoles that do _not_ support UTF-8. At least, it should be optional
... bidirectional communication with the kernel happens via shared memory.