Who says you can’t make a library that does both? Rust makes it pretty easy to conditionally compile code based on architecture.
It could even be possible to make some sort of “ABA primitive” and use that for these sort of data structures. This could well exist: I’ve not looked. These sorts of things really aren’t that common in my experience.
On LR/SC: to any atomics experts listening, isn’t it technically “obstruction-free” (as per the Wikipedia definitions at least) rather than lock-free? (though in practice this makes basically no difference and still counts as lock-free in the C++ (and Rust) sense) Just something that stuck out last time I got sucked into this rabbit hole.
Compare-and-swap and LR/SC are not per se "obstruction-free" or "lock-free".
They are the primitives with which you can implement shared data structures that are "lock-free" or "obstruction-free".
Anything that can be implemented with compare-and-swap can be implemented with LL/SC, and vice-versa.
The only difference between compare-and-swap and LL/SC is how they detect that the memory word has not been modified since the previous reading.
Compare-and-swap just compares the current value with the old value, while LL/SC uses a monitoring circuit implemented in the cache memory controller, which records if any store has happened to that memory location.
Therefore LL/SC is free of the ABA problem, while the existence of the ABA problem has been recognized already since the first moment when compare-and-swap has been invented.
Compare-and-swap has been invented by IBM, who has introduced this instruction in IBM System/370, in 1973. Simultaneously with compare-and-swap, IBM has introduced the instruction compare-double-and-swap, for solving the ABA problem by using a version counter.
Intel has added compare-and-swap renamed as CMPXCHG to 80486 in 1989, and compare-double-and-swap, renamed as CMPXCHG8B, to Pentium in 1993. On x86-64, CMPXCHG8B, i.e. compare-double-and-swap, has become CMPXCHG16B.
LL/SC has been invented in 1987, in the S-1 Advanced Architecture Processor, at the Lawrence Livermore National Laboratory. Then it has been added in 1989 to MIPS II, from where it has spread several years later to most RISC ISAs.
Using either compare-double-and-swap or LL/SC is equivalent, because both are free of the ABA problem.
However there are many cases when the optimistic access to shared data structures that can be implemented with compare-and-swap or LL/SC results in lower performance than access based on mutual exclusion or on dynamic partitioning of the shared data structure (both being implemented with atomic instructions, like atomic exchange or atomic fetch-and-add).
This is why the 64-bit ARM ISA, Aarch64, had to correct their initial mistake of providing only LL/SC, by adding a set of atomic instructions, including atomic exchange and atomic fetch-and-add, in the first revision of the ISA, Armv8.1-A.
> Who says you can’t make a library that does both?
Of course you can. I just meant that the linked article didn't.
> On LR/SC: to any atomics experts listening, isn’t it technically “obstruction-free” (as per the Wikipedia definitions at least) rather than lock-free?
The better criterion IMO is loop-free, which makes it a little easier to understand. Consider the following spin-locking code (with overabundant memory barriers):
do { p = *a; } while (p == 0x1 || !atomic_compare_and_swap(p, 0x1, a));
memory_barrier();
// do stuff that looks at *p
q->next = p;
memory_barrier();
atomic_store(q, a);
Here's the equivalent LL/SC version:
do {
p = ll(a);
memory_barrier();
// do stuff that looks at *p
q->next = p;
memory_barrier();
} while (!sc(q, a));
The pointer-tagging version is also obviously not loop-free. Which is faster, in which cases, and by how much?
The oversimplified answer is that LL/SC is probably slightly faster than spin-locking on most platforms and cases, but pointer-tagging might not be.
My understanding is that all architectures that matter do idiom recognition for ll/sc to guarantee forward progress when ll/sc is used to implement CAS and other common lock-free and wait free patterns, at least as a fallback.
What would you consider the “RISC-V equivalent” of TrustZone? Last time I was curious I didn’t find anything.
(FWIW I agree with the other commenter that these ""security"" features are useless, and feel to me more like check-box compliance than anything else (Why does TrustZone work with function calls? What’s wrong with IPC! Also, what’s wrong with privileged mode?). Just seems like a bit of a waste of silicon really.)
The more and more bit-hacks I see, the more convinced I am that they should be handled by a cleverer compiler. Some intrinsic(s) where you say “do x, y, to these bits” and it just figures out the optimum way of doing it for whatever platform you compile for.
That's a really cool side. Sad that it doesn't allow duplicate indices.
I tried implementing the same thing but with support for duplicates and it was definitely a humbling exercise.
I'm curious if there is any formal mathematical theory for this (shifted-off bits would probably make it less elegant than pure rotation)
that page + the book Hacker's Delight are a big part of the reason I am so convinced of this :)
If compilers/languages/standard libraries provided these bit permutations, and it was just something ~everyone had learned, it would be a lot easier to work with bits without needing to come up with the bitwise ops (or use that generator). In addition it would probably make better use of the hardware: sure, people like to pretend that we’re still programming C for PDP11, but modern hardware supports more operations than C has operators for (RISC-V B extension and co have the right idea <3)
Modern compilers are probably pretty good? but I doubt they are perfect at turning code like that in OP into the best instructions.
It is probably a bit late for C/C++ though. maaaybe possible to get it into LLVM and Rust.
That's more like the opposite, OP wants to tell the compiler what transform to do and have it figure out a solution, but in your example you give the compiler a solution and it works backwards to figure out the intent and rewrite it to a completely different solution.
Most languages do have intrinsics for ROL/ROR at least, which you should generally use instead of relying on optimizer magic. I've certainly run into cases where those magic patterns don't get optimized (looking at you MSVC) but intrinsics always work.
At least in my iOS 18 Passwords app, the passwords are shown in a monospace font that (probably deliberately) differentiates all these (e.g. a slashed zero).
I wouldn’t call it a pet peeve but I understand where you’re coming from with this: but I think the main reason for it is electronic engineers, with little-to-no product design or even mechanical design/CAD background. IMO it’s a shame: it’s sort of like the open source hardware version of the “Blender before it got good UX” problem.
Open hardware so you could build your own for fairly cheap. I bought a clone (is it a clone if the creator never sold them? I'd have preferred to buy it from him...) off aliexpress for ~$50.
It could even be possible to make some sort of “ABA primitive” and use that for these sort of data structures. This could well exist: I’ve not looked. These sorts of things really aren’t that common in my experience.
On LR/SC: to any atomics experts listening, isn’t it technically “obstruction-free” (as per the Wikipedia definitions at least) rather than lock-free? (though in practice this makes basically no difference and still counts as lock-free in the C++ (and Rust) sense) Just something that stuck out last time I got sucked into this rabbit hole.