Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Restartable Sequences

justine.lol

Post reply on HN
Print view View original

41–50 of 82 posts

Re: Restartable Sequences

#41

Post by za_creature »

yubblegum wrote: post #38
khuey wrote: post #35

Earlier quoted context omitted.

The "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.

Let'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…

I'm not a systems guy, but you're probably right. A mutex requires an atomic variable which triggers the same cache coherency mechanism under contention.

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.

Re: Restartable Sequences

#42

Post by bryanlarsen »

crote wrote: post #27
bryanlarsen wrote: post #14

Earlier quoted context omitted.

That doesn't really explain it though, IMO. IIUC, it's a sequence of instructions that either runs to completion atomically or doesn't. If it is interrupted by anything the kernel jumps you to the abort/retry vector you set with a guarantee that the last instruction in the sequence was not executed. (Based on my reading of the LWN article rwmj posted).

> it's a sequence of instructions that either runs to completion atomically or doesn't 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 ins…

Yes, it's either atomic or the last instruction is guaranteed not to have run. I made this a little harder to read by inserting another clause in the sentence.

Re: Restartable Sequences

#44

Post by Veserv »

senderista wrote: post #12
Veserv wrote: post #5

Restartable 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 preemp…

There 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

Yep, 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.

Re: Restartable Sequences

#45

Post by loeg »

khuey wrote: post #2

Maybe 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.

I wouldn't read it too literally. I read it as jokingly rationalizing an obviously overkill self-indulgent purchase.

Re: Restartable Sequences

#46

Post by mota7 »

yubblegum wrote: post #38
khuey wrote: post #35

Earlier quoted context omitted.

The "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.

Let'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…

If you have two threads on different cores that write to the same cacheline, the CPU has to enforce write ordering. The way it does this is for one of the cores to acquire a write lock on the cacheline. The actual implementation of this is via some variant of the MESI protocol that results in the cacheline on one core going to an Exclusive state, while copies of the cacheline on every other core becomes Invalid.

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.

Re: Restartable Sequences

#47

Post by loeg »

keyle wrote: post #39

... bidirectional communication with the kernel happens via shared memory. What could possibly go wrong?

Elaborate? Kernel shared memory interfaces are often reasonable (vdso, io_uring).

Re: Restartable Sequences

#48

Post by senderista »

Veserv wrote: post #44
senderista wrote: post #12

Earlier quoted context omitted.

There 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

Yep, 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.

I have no idea why your comment was flagged :(

Re: Restartable Sequences

#49

Post by [deleted] »

yubblegum wrote: post #38
khuey wrote: post #35

Earlier quoted context omitted.

The "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.

Let'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…

[deleted]

Re: Restartable Sequences

#50

Post by khuey »

mota7 wrote: post #46
yubblegum wrote: post #38

Earlier quoted context omitted.

Let'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…

If you have two threads on different cores that write to the same cacheline, the CPU has to enforce write ordering. The way it does this is for one of the cores to acquire a write lock on the cacheline. The actual implementation of this is via some variant of the MESI protocol that results in the cacheline on one core going to an Exclusive state, while copies of the cacheline on every other core becomes Invalid. MESI…

> The point is that with RSEQ, you can write a _different_ algorithm that's faster than an implementation relying on hardware mediated MESI.

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.

Post reply on HN