7 ms·
Restartable Sequences
- matheusmoreira 4mo agoThis is amazing. I'll definitely use this in my projects.
- khuey 4mo agoMaybe I'm just getting old but the "if you don't spend $20,000 on a workstation you're going to be left behind like a dinosaur" at the top of this article is a huge turn off to reading any further. And I say that as someone who owns a workstation with more cores than the author's.
- toast0 4mo agoIf we're being overly generous, they're saying you need at least a raspberry pi? You can see a 3x improvement there, which shows the pattern works, and that's good enough for a dinosaur (this interpretation is easier to justify if you just skim the article... Which I did the first time) 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.
- khuey 4mo agoYeah, you can rent an equivalent workstation from AWS for under $10/hour (and that's the on demand price) so I don't think cost is a huge barrier to doing this sort of work. The language and listing the prices of the workstations down to the penny just strikes me as a rather unprofessional way to communicate.
- eff-nix 4mo ago[dead]
- lpapez 4mo agoExcept that is not what the article says and you clearly missed the sarcasm.
- Avicebron 4mo agoThe author was also asking for money to buy a house in SF and travel on private planes like a few days ago..the donation must have really showed up if they are using 20k machines at home.
- blauditore 4mo agoDo you have a link?
- deleted 4mo ago[deleted]
- insamniac 4mo agohttps://web.archive.org/web/20260529122658/https://justine.lol/animus/ https://web.archive.org/web/20260529122658/https://justine.l...
- blauditore 4mo agoI was wondering if the author is joking, but after reading a bit more about the attribution drama, it seems rather a lack of reality check and reflection. If you plagiarize work, get called out on it, and then call this "harrassment", I don't know...
- nick__m 4mo agoThat's reads like an egotic cocaine fueled rant mixed with a PBS pledges drive. I understand why the author deleted it !
- nutjob2 4mo ago> I have nothing against this person. 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.lol/animus/ https://web.archive.org/web/20260529122658/https://justine.l... ]
- nutjob2 4mo agoShe's clearly making a point about taking advantage of the optimization/algorithm she's pitching, and doesn't seem very serious. Alternatively, someone reading that as a serious claim is rather naive.
- deleted 4mo ago[deleted]
- kitd 4mo agoGo to the end. Those machines were provided by the companies discounted so she could continue her llm research. She's not saying "anyone who's anyone" has a 1024-core workstation these days.
- loeg 4mo agoI wouldn't read it too literally. I read it as jokingly rationalizing an obviously overkill self-indulgent purchase.
- camgunz 4mo agoI gotta think people are working pretty hard to not see it's a joke.
- keybored 4mo agoYep. The consolation is I guess that it might be better if developers with such modest means as “splurged on” two 20KUSD~ work stations (and left in the “poor house” for a few months, oh my) are competitive instead of absolutely all of us becoming compute renters. 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. [2] https://news.ycombinator.com/item?id=48348919 https://news.ycombinator.com/item?id=48348919
- GlenTheMachine 4mo agoIf you had no idea what a restorable sequence is the takeaway is about halfway down the OP: “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.”
- manoDev 4mo agoThat’s clever — am I right to think it’s the intermediate solution between locks and full STM, implemented at the kernel level, and with zero abstraction cost?
- khuey 4mo agoIt's in some sense a light form of STM. The key insight behind rseq(2) is that if the data is local to a given CPU the only way to get a race is if the kernel deschedules your program from that CPU at an inopportune time. If your operation can be aborted and restarted and the kernel has a mechanism to notify you when that needs to happen you can dispense with the overhead of "real" synchronization and just use a couple mov instructions to enter and exit the critical section.
- squirrellous 4mo agoI am not very well versed here but I think due to the requirement for assembly and single-instruction commit, practical uses of rseq is generally very simple. It is nowhere near the usefulness of locks.
- rurban 4mo agoCertainly not zero cost. Syscalls are heavy, that's why everyone prefers green threads. And 2 more ops per rseq. But rseq's are certainly cool.
- Veserv 4mo agoRestartable windows, or more generically introspection windows, are a really useful technique you can apply in any situation where you understand or control the sources of preemption. The earliest uses of this technique in operating systems that I am aware of are ~25 years old. 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.
- senderista 4mo agoThere is a paper from Sun that anticipated tcmalloc's development of rseq by over a decade: https://dl.acm.org/doi/abs/10.1145/512429.512451 https://dl.acm.org/doi/abs/10.1145/512429.512451
- Veserv 4mo agoYep, it is a fairly old technique with a lot of of general applicability beyond just allowing mutex elision for usage of per-core data structures amidst potential core migration. But apparently using your own expert knowledge and actually explaining things and describing generalizations is worthy of flagging these days.
- senderista 4mo agoI have no idea why your comment was flagged :(
- senderista 4mo agoI'm surprised there was no reference to the librseq library, maintained by the rseq implementer: https://github.com/compudj/librseq 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.
- wmf 4mo agoJustine is writing her own libc and her own malloc so I'm not surprised she wants to use rseq from scratch.
- senderista 4mo agoThat's fine, but I think an article claiming to give an introduction to a technology should at least mention that an essential library exists, and that writing assembly is no longer usually required.
- philipallstar 4mo ago> an article claiming to give an introduction to a technology Is it claiming that?
- dividuum 4mo agoI'm took a brief look and left confused. The list implementation seems completely bog standard with no special code for synchronization whatsoever. I don't see any counter and the rseq syscall seems unused except for feature detection. I don't think that's a viable replacement for any low level code.
- bonzini 4mo agoThe low level interface is documented at https://github.com/compudj/librseq/blob/master/include/rseq/pseudocode.h https://github.com/compudj/librseq/blob/master/include/rseq/..., the list is just an internal implementation detail. 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.
- dan_sbl 4mo ago[flagged]
- brcmthrowaway 4mo ago[flagged]
- yubblegum 4mo ago> chances are the CPU's internal mutexes aren't as good as the ones you've implemented in userspace Anyone with an informed opinion on this statement? It's seems counter intuitive (npi).
- khuey 4mo agoThe author is referring to false sharing (https://en.wikipedia.org/wiki/False_sharing https://en.wikipedia.org/wiki/False_sharing). CPU caches operate at cache line granularity (typically 64 bytes) so writes to one part of the cache line can require synchronization with writes to non-overlapping parts of the same cache line. This can dramatically reduce performance when there are a large number of cores operating on the same cache line. 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.
- yubblegum 4mo agoThanks for the effort but the q wasn't "what is false sharing", The Q is: is it true the CPU mutexes are actually slower than those implemented in userspace?
- khuey 4mo agoThe "CPU mutex" is just the cache coherency mechanism. If you shard your data to avoid triggering it as suggested, then yes, it's much faster. 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.
- yubblegum 4mo agoLet's try this again: 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.
- keyle 4mo ago... bidirectional communication with the kernel happens via shared memory. What could possibly go wrong?
- loeg 4mo agoElaborate? Kernel shared memory interfaces are often reasonable (vdso, io_uring).
- HackerThemAll 4mo agoIt's 32 bytes. Educate yourself before commenting.
- squirrellous 4mo agoIIUC rseq is similar to thread-local data with the additional benefit that it scales with number of CPU cores, not threads. However if you are an application developer and is able to control all the threads in an application, then rseq isn’t that superior. I fully agree that rseq should be more easily available to Linux developers, though.
- smasher164 4mo agoI was having a conversation with someone recently if RSEQ would be a good primitive to build a load-link/store-conditional implementation in user-space. It gives you a critical window, though you still have to deal with spurious restarts, and provide a way for one core to abort another.
- HackerThemAll 4mo agoThe name is so misleading... The first thing I see when hearing "sequence" is the "arithmetic sequence", like 1,2,3,4. Therefore "restartable sequence" is like 1,2,3,4, 1,2,3,4, 1,2,3,4... Closer to SQL's "CREATE SEQUENCE" than "restartable sequence of assembly instructions". I could not comprehend how this can help with lock free data exchange. I've done my homework now.
- NuclearPM 4mo agoPeople who say 10x programmers don’t exist have never heard of Justine.
- 1vuio0pswjnm7 4mo agoWas greenbean ever tested with NetBSD ftp Something like greenbean then ftp -vvd4o/dev/stdout http://127.0.0.1:8080 This is labeled as an error: "fragmented message" 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