What's up with this new memory_order_consume memory order?(devblogs.microsoft.com)
devblogs.microsoft.com
What's up with this new memory_order_consume memory order?
https://devblogs.microsoft.com/oldnewthing/20230427-00/?p=108107
6 comments
> the DEC Alpha seems like it should have some sort of cheap fast atomics, but you can't cheaply do Acquire-Release so how about we invent something else ?
consume was not invented for Alpha. rather consume should have less overhead than acquire on any platform that needs additional memory barriers to implement acquire semantics (on most platforms consume requires no barriers at all since memory ordering is enforced as a side-effect of dependency ordering. Alpha is an exception to this, i.e. consume does require a barrier on Alpha).
it's also worth noting that rcu_dereference in linux is based on the same idea as consume (using dependencies to enforce memory ordering) the the basic idea is definitely useful. it's more that the C++ standard's specification of consume turned out to be unimplementable in practice
consume was not invented for Alpha. rather consume should have less overhead than acquire on any platform that needs additional memory barriers to implement acquire semantics (on most platforms consume requires no barriers at all since memory ordering is enforced as a side-effect of dependency ordering. Alpha is an exception to this, i.e. consume does require a barrier on Alpha).
it's also worth noting that rcu_dereference in linux is based on the same idea as consume (using dependencies to enforce memory ordering) the the basic idea is definitely useful. it's more that the C++ standard's specification of consume turned out to be unimplementable in practice
> consume was not invented for Alpha. rather consume should have less overhead than acquire on any platform that [emphasis mine] needs additional memory barriers to implement acquire semantics
Um... which platform?[1] Probably the biggest reason that memory ordering semantics are such a mess, and lockless algorithms such an infeasible disaster, is the propensity of people to argue about this stuff in generic terms, using language and concepts from egghead standards writers instead of examples of real machines. Out of order execution is an engineering technique for physical devices. We should talk about the machines first, and the abstractions later.
It's like going to the mechanic with a leaky valve and having the explanation come back in terms of cycle efficiencies and isentropic losses. It's not actually helpful to understanding the problem unless you already understand the theory. And you won't ever learn the theory unless you see the problem it's solving.
[1] It's a serious question, btw. I genuinely don't know what the target hardware is for "consume" myself, and suspect this is just a pet theory that snuck into the standard.
Um... which platform?[1] Probably the biggest reason that memory ordering semantics are such a mess, and lockless algorithms such an infeasible disaster, is the propensity of people to argue about this stuff in generic terms, using language and concepts from egghead standards writers instead of examples of real machines. Out of order execution is an engineering technique for physical devices. We should talk about the machines first, and the abstractions later.
It's like going to the mechanic with a leaky valve and having the explanation come back in terms of cycle efficiencies and isentropic losses. It's not actually helpful to understanding the problem unless you already understand the theory. And you won't ever learn the theory unless you see the problem it's solving.
[1] It's a serious question, btw. I genuinely don't know what the target hardware is for "consume" myself, and suspect this is just a pet theory that snuck into the standard.
>Um... which platform?
In practice all non-TSO machines that need a load-load barrier for acquire but no barrier for data dependencies (i.e. loads through pointers). Notably this includes ARM and POWER. These architectures still needed relatively expensive fences on the release path.
On TSO machines (SPARC, x86 for example) acquire loads and release stores are free.
Alpha was the strange outlier that also needed a barrier for the dependent load path.
But acquire and release are such a sweet spot for programming that ARM (and apparently POWER) have since added cheap (although not free) acquire load/release stores.
Far from being a mess, the C++11 memory model (and acquire/release in particular) has been an unmitigated success that has allowed writing, discussing and proving the correctness of very practical lock free algorithms on real hardware while not resorting to the expensive SEQ-CST model. Also since it inception, all relevant architectures have formalized their memory model and made sure that they can implement acq/rel efficiently.
In practice all non-TSO machines that need a load-load barrier for acquire but no barrier for data dependencies (i.e. loads through pointers). Notably this includes ARM and POWER. These architectures still needed relatively expensive fences on the release path.
On TSO machines (SPARC, x86 for example) acquire loads and release stores are free.
Alpha was the strange outlier that also needed a barrier for the dependent load path.
But acquire and release are such a sweet spot for programming that ARM (and apparently POWER) have since added cheap (although not free) acquire load/release stores.
Far from being a mess, the C++11 memory model (and acquire/release in particular) has been an unmitigated success that has allowed writing, discussing and proving the correctness of very practical lock free algorithms on real hardware while not resorting to the expensive SEQ-CST model. Also since it inception, all relevant architectures have formalized their memory model and made sure that they can implement acq/rel efficiently.
The point of memory_order_consume is to be able to omit the load barrier on architectures with weak memory orderings that don't need them for data-dependent operations on the load. This is basically every architecture other than Alpha (which would still need the barrier with memory_order_consume) and x86 and SPARC (which don't need the barrier with memory_order_acquire). ARM and PPC, for example, fall into this category.
> Um... which platform?
most platforms with weaker-than-x86 memory models need additional barriers for acquires e.g. on ARM you need LDAR
> Probably the biggest reason that memory ordering semantics are such a mess
are they though? release/acquire semantics are actually intuitive once you get used to them and are very well suited for pointer-based lockfree data structures. consume is maybe more subtle but it's mostly an optimization on top of acquire, so not very difficult conceptually
most platforms with weaker-than-x86 memory models need additional barriers for acquires e.g. on ARM you need LDAR
> Probably the biggest reason that memory ordering semantics are such a mess
are they though? release/acquire semantics are actually intuitive once you get used to them and are very well suited for pointer-based lockfree data structures. consume is maybe more subtle but it's mostly an optimization on top of acquire, so not very difficult conceptually
Are memory ordering semantics a mess? I implemented simulators for x86, ARM and C++ memory models and the documentation for all three was fantastic.
What's part of it is a mess?
I'm also not sure I understand your point about physical machines. Surely what we care about are the guarantees each platform gives.
There are plenty of cases where the documented worst case is worse than you'll ever be able to replicate - for now. Sticking to the contract means you're safe on next year's machines, too.
What's part of it is a mess?
I'm also not sure I understand your point about physical machines. Surely what we care about are the guarantees each platform gives.
There are plenty of cases where the documented worst case is worse than you'll ever be able to replicate - for now. Sticking to the contract means you're safe on next year's machines, too.
To be glib, the part that answers the question "Who needs consume and why is it there?". As pointed out, Chen answers this incorrectly in the linked article. An upthread poster pointed out (correctly, though they skipped the justification) that Alpha needs this, but was then corrected (incorrectly, AFAICT, though I'm willing to be educated) that this feature was not for Alpha.
To be more serious: anyone who's ever tried to implement a lockless algorithm knows how hard this stuff is even if you have a clear and unambiguous set of tools to use to do it. And the C++ memory model is, as mentioned, kinda ambiguous.
At the end of the day, in practice these problems are solved on real hardware with real tools that look like "MFENCE" or "DSB" (either directly, or because you're reading the generated assembly trying to figure out how it's going wrong). That's exactly the opposite of the way a good abstraction is supposed to work.
To be more serious: anyone who's ever tried to implement a lockless algorithm knows how hard this stuff is even if you have a clear and unambiguous set of tools to use to do it. And the C++ memory model is, as mentioned, kinda ambiguous.
At the end of the day, in practice these problems are solved on real hardware with real tools that look like "MFENCE" or "DSB" (either directly, or because you're reading the generated assembly trying to figure out how it's going wrong). That's exactly the opposite of the way a good abstraction is supposed to work.
I'm just not sure what consume and the Alpha have to do with each other. Consume is an attempt to give you a lightweight load when all you want are guarantees related to a dependent load. And the Alpha is the only machine I'm aware of where dependent loads don't give you any guarantees.
As far as lockless algorithms go - using something like Loom for Rust greatly simplifies correctness. It has a relatively complete implementation of the C++ memory model, and will catch bizarre edge cases you'd struggle to ever replicate on a real CPU. There are also solvers for C++ that help you do similar reasoning.
For _performance_, on the other hand, it's the wild west. I experimented with pairing my home grown system similar to Loom with a MESI cache simulator, testing cache behaviour with lockless algorithms banging on the same cache lines. It showed some promise, but was quite difficult to make ergonomic for the consumer.
As far as lockless algorithms go - using something like Loom for Rust greatly simplifies correctness. It has a relatively complete implementation of the C++ memory model, and will catch bizarre edge cases you'd struggle to ever replicate on a real CPU. There are also solvers for C++ that help you do similar reasoning.
For _performance_, on the other hand, it's the wild west. I experimented with pairing my home grown system similar to Loom with a MESI cache simulator, testing cache behaviour with lockless algorithms banging on the same cache lines. It showed some promise, but was quite difficult to make ergonomic for the consumer.
> I'm just not sure what consume and the Alpha have to do with each other.
This seems like semantic evasion? Consume exists[1] precisely so that you can write code using the C++ memory model that works correctly on a superscalar Alpha chip (not the 21064/21164, those are in-order). Saying that it doesn't have anything to do with alpha seems really strained. If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else.
[1] Again, AFAIK. Lots of folks in this thread, including you, seem to be implying that other such hardware exists. But I'm not aware of it. And my broader point is that this kind of "standards first" discussion obscures understanding.
This seems like semantic evasion? Consume exists[1] precisely so that you can write code using the C++ memory model that works correctly on a superscalar Alpha chip (not the 21064/21164, those are in-order). Saying that it doesn't have anything to do with alpha seems really strained. If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else.
[1] Again, AFAIK. Lots of folks in this thread, including you, seem to be implying that other such hardware exists. But I'm not aware of it. And my broader point is that this kind of "standards first" discussion obscures understanding.
> Consume exists[1] precisely so that you can write code using the C++ memory model that works correctly on a superscalar Alpha chip (not the 21064/21164, those are in-order).
No, you have it wrong. Consume exists so that you can write code that works correctly on all chips other than Alpha, x86, and SPARC.
> If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else.
That's patently false. For the semantics to work correctly, you still need to identify the memory operations that generate synchronization edges. Unannotated loads, by definition, can't generate those edges. Relaxed atomics are sufficient from a hardware perspective, but it ignores the effect of the compiler. The problem with consume--why it's never worked--is that it relies on the compiler preserving data dependencies expressed in the source language, which runs into the issue of a) defining what exactly constitutes a data dependence (hardware implementations don't exactly agree!) and b) this turns out to be a lot more difficult to do than originally anticipated.
To even have a hope of being able to correctly reason about the need to not have a load barrier in these places, you need a big, flashing neon sign to the compiler saying "this is special with special semantics, please pay attention." That sign is memory_order_consume.
No, you have it wrong. Consume exists so that you can write code that works correctly on all chips other than Alpha, x86, and SPARC.
> If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else.
That's patently false. For the semantics to work correctly, you still need to identify the memory operations that generate synchronization edges. Unannotated loads, by definition, can't generate those edges. Relaxed atomics are sufficient from a hardware perspective, but it ignores the effect of the compiler. The problem with consume--why it's never worked--is that it relies on the compiler preserving data dependencies expressed in the source language, which runs into the issue of a) defining what exactly constitutes a data dependence (hardware implementations don't exactly agree!) and b) this turns out to be a lot more difficult to do than originally anticipated.
To even have a hope of being able to correctly reason about the need to not have a load barrier in these places, you need a big, flashing neon sign to the compiler saying "this is special with special semantics, please pay attention." That sign is memory_order_consume.
I don't think that's correct? Can you give an example of an algorithm on x86 or ARM that requires a consume barrier to operate correctly? It's a noop. Dependent loads on those hardware architectures do not reorder, and by definition dependent loads can't be reordered by the compiler (because you can't write time travel code that executes a load before the instruction that loads its pointer!).
Consume does not AFAICT act as a memory clobber or optimization barrier to the compiler.
Consume does not AFAICT act as a memory clobber or optimization barrier to the compiler.
> Consume does not AFAICT act as a memory clobber or optimization barrier to the compiler.
This is your confusion. It is precisely an optimization barrier. Specifically, it's an acquire barrier, but only for certain data-dependent subsequent loads. Compilers universally treat it as a global acquire barrier because it turns out that it's too difficult to ensure that language-level data dependencies translate to hardware-level data dependencies.
On x86, the hardware never needs acquire barriers, so the relaxation to an acquire barrier has no effect. However, although the hardware doesn't need acquire barriers, the compiler still needs to know where those exist in the program so that it doesn't reorder the loads anyways. Meanwhile, on Alpha, the hardware still needs an acquire barrier in the case where there's a data dependency. So in both the ultra-weak and the rather strong memory models, translating memory_order_consume as memory_order_acquire has no actual difference to the hardware outcomes.
This is why memory_order_consume is really for ARM et al--the compiler still needs to know about the existence of the barrier, but the hardware doesn't need the barrier. And this is why there's still efforts going on to fix memory_order_consume; the people who work on ARM and the like want to get to the point where they can write these codes without having the compiler emit acquire barriers.
This is your confusion. It is precisely an optimization barrier. Specifically, it's an acquire barrier, but only for certain data-dependent subsequent loads. Compilers universally treat it as a global acquire barrier because it turns out that it's too difficult to ensure that language-level data dependencies translate to hardware-level data dependencies.
On x86, the hardware never needs acquire barriers, so the relaxation to an acquire barrier has no effect. However, although the hardware doesn't need acquire barriers, the compiler still needs to know where those exist in the program so that it doesn't reorder the loads anyways. Meanwhile, on Alpha, the hardware still needs an acquire barrier in the case where there's a data dependency. So in both the ultra-weak and the rather strong memory models, translating memory_order_consume as memory_order_acquire has no actual difference to the hardware outcomes.
This is why memory_order_consume is really for ARM et al--the compiler still needs to know about the existence of the barrier, but the hardware doesn't need the barrier. And this is why there's still efforts going on to fix memory_order_consume; the people who work on ARM and the like want to get to the point where they can write these codes without having the compiler emit acquire barriers.
> It is precisely an optimization barrier. Specifically, it's an acquire barrier, but only for certain data-dependent subsequent loads.
I don't understand what that means. Compiler barriers are about changing the ordering of instructions. "DEpendent" loads have defined ordering already, you can't issue a load before loading the pointer register you're dereferencing!
I have to ask again: can you give me an example from any toolchain and any architecture other than Alpha where a consume generates a detectable difference in the generated code?
I don't understand what that means. Compiler barriers are about changing the ordering of instructions. "DEpendent" loads have defined ordering already, you can't issue a load before loading the pointer register you're dereferencing!
I have to ask again: can you give me an example from any toolchain and any architecture other than Alpha where a consume generates a detectable difference in the generated code?
Compiler optimizations need not preserve data dependencies. For example, consider this fragment of code:
This is also why compilers have generally ignored memory_order_consume, by-the-by. Supporting consume 'properly' (i.e., other than strengthening it into a memory_order_acquire) requires suppressing optimizations that do not preserve data dependencies, but consume leaks out too much to the point that it's basically not possible to prove that the dependency isn't part of a consume chain, and the optimization is too beneficial to be worth turning off entirely.
if (i == 3) {
y = x[i];
}
if (i == 3) {
y = x[3];
}
This is also why compilers have generally ignored memory_order_consume, by-the-by. Supporting consume 'properly' (i.e., other than strengthening it into a memory_order_acquire) requires suppressing optimizations that do not preserve data dependencies, but consume leaks out too much to the point that it's basically not possible to prove that the dependency isn't part of a consume chain, and the optimization is too beneficial to be worth turning off entirely.
The article has an explicit example of how a compiler can break the dependency by adding speculation (for example after PGO). In practice it is unlikely that a plain load through a pointer will break, but consume allows for more complex dependencies beyond pointer dereferences.
consume obviously doesn't need a barrier on arm or x86, but it still needs a source level annotation. relaxed is not enough as the compiler could otherwise break the required dependency (for example by introducing a speculation). In fact consume is in practice not implemented optimally by compilers because it is very very hard to guarantee that the data dependency is not broken in all cases.
I.e. the quirks of Alpha have no bearing on the existence of consume. A different annotation between relaxed and acquire would still needed to specifically capture the semantics of data dependencies (that's the theory at least, in practice even consume and the [[carries_dependency]] annotations are not enough).
I.e. the quirks of Alpha have no bearing on the existence of consume. A different annotation between relaxed and acquire would still needed to specifically capture the semantics of data dependencies (that's the theory at least, in practice even consume and the [[carries_dependency]] annotations are not enough).
No, approximately nobody cares about Alpha. consume exists so that many algorithms can be implemented cheaply on ARM and POWER without requiring an expensive load-load barrier on the consumer side by relying on data dependencies. For example the Linux kernel makes use of data-dependencies to make RCU cheap on these machines.
Still, in practice because of a mixture of being hard to implement[1] and x86 dominating compiler development, most compilers gave up and just implemented consume as an acquire.
[1] to make consume work, compilers need to make sure that data dependencies are propagated everywhere they are needed and this is very hard.
edit: also in-order machines are very much capable of the kind of reordering that require memory barriers. IIRC the lack of data dependency of alpha was a quirk due to its banked cache setup, not because of pipeline reordering. In fact data-dependences is specifically the kind of reordering that an OoO engine can't do.
Still, in practice because of a mixture of being hard to implement[1] and x86 dominating compiler development, most compilers gave up and just implemented consume as an acquire.
[1] to make consume work, compilers need to make sure that data dependencies are propagated everywhere they are needed and this is very hard.
edit: also in-order machines are very much capable of the kind of reordering that require memory barriers. IIRC the lack of data dependency of alpha was a quirk due to its banked cache setup, not because of pipeline reordering. In fact data-dependences is specifically the kind of reordering that an OoO engine can't do.
> consume exists so that many algorithms can be implemented cheaply on ARM and POWER without requiring an expensive load-load barrier on the consumer side
No? Those algorithms can be implemented cheaply already on every architecture BUT Alpha! You just don't use a barrier there, because none is needed. The only reason we're even talking about consume is becasue alpha exists and requires a barrier instruction on dependent loads. No alpha, no consume. QED.
Again I repeat: the attempt to obscure this and pretend that features like "consume" are first class theoretic entities unconnected to hardware is IMHO really, really hurting people's ability to understand this subject. It's not like that, it's a hack. Call it a hack to support a legacy architecture and then people will understand why it's there. Pretend that all possible[1] designs for ordering synchronization would require "consume" and you'll have everyone tied up in arguments like this trying to understand what it's for.
[1] Which is impossible, obviously. I do much of my day job on an architecture with an incoherent cache where NONE of these silly toys work to solve ordering issues, because they're aimed at a different layer of the stack.
No? Those algorithms can be implemented cheaply already on every architecture BUT Alpha! You just don't use a barrier there, because none is needed. The only reason we're even talking about consume is becasue alpha exists and requires a barrier instruction on dependent loads. No alpha, no consume. QED.
Again I repeat: the attempt to obscure this and pretend that features like "consume" are first class theoretic entities unconnected to hardware is IMHO really, really hurting people's ability to understand this subject. It's not like that, it's a hack. Call it a hack to support a legacy architecture and then people will understand why it's there. Pretend that all possible[1] designs for ordering synchronization would require "consume" and you'll have everyone tied up in arguments like this trying to understand what it's for.
[1] Which is impossible, obviously. I do much of my day job on an architecture with an incoherent cache where NONE of these silly toys work to solve ordering issues, because they're aimed at a different layer of the stack.
With memory_order_acquire, you need a load-load barrier on the read side of RCU on ARM; with memory_order_consume, assuming an optimal implementation you do not. On alpha you need a barrier either way. Hence consume improves performance on ARM (and other similar architectures), but doesn't help Alpha.
edit: to be more explicit, you can't formally implement RCU with relaxed + a compiler barrier, although in practice it might work most of the time.
edit: to be more explicit, you can't formally implement RCU with relaxed + a compiler barrier, although in practice it might work most of the time.
I see, I think I'm never going to get this straight, so expect me to screw it up the next time I try to summarise as well, sorry.
According to a comment in the blog post, the sementic had changed in C++20:
> If your compiler predates C++20, however, the consume memory order is almost certainly treated as acquire (legal, just not faster). C++17 temporarily discouraged the use of the consume order because the semantics were impossible to use correctly, and thus all compilers were implementing it as acquire. > > The revisions in C++20 took some very smart people a lot of effort, and changed the definitions subtly so that you can use consume and get weaker memory ordering than acquire without immediately invoking our good friend UB.
> If your compiler predates C++20, however, the consume memory order is almost certainly treated as acquire (legal, just not faster). C++17 temporarily discouraged the use of the consume order because the semantics were impossible to use correctly, and thus all compilers were implementing it as acquire. > > The revisions in C++20 took some very smart people a lot of effort, and changed the definitions subtly so that you can use consume and get weaker memory ordering than acquire without immediately invoking our good friend UB.
That is what the comment says, but, it doesn't seem to match reality. "To verify comments I saw on Raymond Chen's blog" isn't enough justification for me to pay ISO's fees for the actual ISO C++ 20 standard document, but the draft the committee members work from still says of Consume:
> Implementations have found it infeasible to provide performance better than that of memory_order :: acquire.
I suspect that the comment is well-meant but is referring to some proposal that may have been made at some point in the last say five years, and which isn't in the ISO standard. Plenty of people have proposed that Consume could be fixed, but there are big gaps between proposing a fix, agreeing it among all interested parties and writing that fix into the standard, and actually shipping compilers with working Consume memory order.
> Implementations have found it infeasible to provide performance better than that of memory_order :: acquire.
I suspect that the comment is well-meant but is referring to some proposal that may have been made at some point in the last say five years, and which isn't in the ISO standard. Plenty of people have proposed that Consume could be fixed, but there are big gaps between proposing a fix, agreeing it among all interested parties and writing that fix into the standard, and actually shipping compilers with working Consume memory order.
If Consume is discouraged, what should you use instead for the read side of RCU style algorithms?
Acquire is too heavy, and Relaxed is too relaxed, even if it often works on non-Alpha CPUs in practice, it assumes the compiler doesn't get too clever with speculative prefetch and reuse optimisations.
Do we really still need to use Linux's compiler-specific `rcu_dereference` in performant code just because Consume isn't implemented?
Acquire is too heavy, and Relaxed is too relaxed, even if it often works on non-Alpha CPUs in practice, it assumes the compiler doesn't get too clever with speculative prefetch and reuse optimisations.
Do we really still need to use Linux's compiler-specific `rcu_dereference` in performant code just because Consume isn't implemented?
Yeah, compilers were never really into it anyways. Most of them just lowered it to an acquire so there wasn't any point in using it.
I don't remember who said it. But some C++ Guru on some online talk (Herb Sutter, Pikus, etc etc.) was saying that 'consume' was pushed by ARM and PowerPC chipmakers as sufficient for C++11. And these chipmakers were somewhat biased by how POWER7 and ARMv7 worked.
Alas, it seems like consume was too complicated for compiler writers to take full advantage of. So in practice, acquire is used instead. And then in ARMv8 and POWER9, acquire was added to those instruction sets. Acquire isn't the default, but we do have accelerated assembly language support for the acquire model.
So moving forward, acquire seems to be the sweetspot model. I guess consume exists for a hypothetical future C++ compiler that tries to optimize multithreaded ARMv7 or something, a relatively small niche in practice as current C++ compilers don't support consume and future processors have moved on to the acquire model.
Alas, it seems like consume was too complicated for compiler writers to take full advantage of. So in practice, acquire is used instead. And then in ARMv8 and POWER9, acquire was added to those instruction sets. Acquire isn't the default, but we do have accelerated assembly language support for the acquire model.
So moving forward, acquire seems to be the sweetspot model. I guess consume exists for a hypothetical future C++ compiler that tries to optimize multithreaded ARMv7 or something, a relatively small niche in practice as current C++ compilers don't support consume and future processors have moved on to the acquire model.
Yes, I believe that consume will be consigned to the annals of history. Acq/rel is such a sweet spot that in retrospect it should have been the default (for load and stores respectively) instead of seq_cst.
Seq_cst is still how programmers think how computers work before they study memory reorderings.
Because that's how typical programmers think, it is the default. Relaxed, consume, and acquire are invented for the people who are trying to save those precious nanoseconds by cutting out a potential memory barrier from the resulting code.
In the pre-C++11 days, I would just shove full barriers everywhere in my code defensively, cause I didn't really understand memory models. Seq_cst is basically that behavior (a full memory barrier between important operations) which is always correct but maybe a bit slow.
Because that's how typical programmers think, it is the default. Relaxed, consume, and acquire are invented for the people who are trying to save those precious nanoseconds by cutting out a potential memory barrier from the resulting code.
In the pre-C++11 days, I would just shove full barriers everywhere in my code defensively, cause I didn't really understand memory models. Seq_cst is basically that behavior (a full memory barrier between important operations) which is always correct but maybe a bit slow.
Using seq_cst everywhere is probably so slow that you'd be better off not using atomics at all; just use a mutex library that internally uses acquire/release to protect regular non-atomic variables.
Its a bad idea to use a mutex inside of interrupt code.
seq_cst / atomics / barriers are for writing lock-free code, which is fully compatible with interrupts and other system-call level details. Its about correctness, not about speed.
--------
I had a discussion elsewhere where people seem to think that these constructs are for speed. They... really aren't. Atomics are about lock-free code, and lock-free code might be slower than locked-code/mutex code.
Lock-free code is about forward progress in all conditions. Sometimes its faster, but its an independent axis as far as software design is concerned.
I guess acquire is faster than seq_cst, and consume/relaxed would be even faster than acquire. But correctness comes first, and proving correctness in consume-style code is seemingly too difficult in practice. So acquire is where the sweet spot seems to be... at least with today's tech and understanding of multithreaded issues.
seq_cst / atomics / barriers are for writing lock-free code, which is fully compatible with interrupts and other system-call level details. Its about correctness, not about speed.
--------
I had a discussion elsewhere where people seem to think that these constructs are for speed. They... really aren't. Atomics are about lock-free code, and lock-free code might be slower than locked-code/mutex code.
Lock-free code is about forward progress in all conditions. Sometimes its faster, but its an independent axis as far as software design is concerned.
I guess acquire is faster than seq_cst, and consume/relaxed would be even faster than acquire. But correctness comes first, and proving correctness in consume-style code is seemingly too difficult in practice. So acquire is where the sweet spot seems to be... at least with today's tech and understanding of multithreaded issues.
The whole construct of atomics is for speed. I've never seen an argument against it. On the contrary, there are plenty of misguided arguments for speed that doesn't hold in reality; badly written atomics is often slower than mutex.
Lock-free code by itself doesn't guarantee forward progress. I've seen way too much atomic code where the author sprinkles a seemingly infinite loop that only breaks when compare_exchange_strong succeeds. How would you reason that those loops will in fact terminate? When you use a mutex, there are no loops anywhere. Afraid of deadlocks making in mutex code? There are many good deadlock detection tools that you can use without directly reasoning about each section of atomic code. That's infinitely better in terms of productivity.
Lock-free code by itself doesn't guarantee forward progress. I've seen way too much atomic code where the author sprinkles a seemingly infinite loop that only breaks when compare_exchange_strong succeeds. How would you reason that those loops will in fact terminate? When you use a mutex, there are no loops anywhere. Afraid of deadlocks making in mutex code? There are many good deadlock detection tools that you can use without directly reasoning about each section of atomic code. That's infinitely better in terms of productivity.
> Afraid of deadlocks making in mutex code?
No. You literally cannot use a mutex in interrupt service routines.
If you fail to understand why, then you don't understand fundamental OS and/or device driver issues and need to study up on that a bit more. This isn't something you use userland tools to solve either.
You're arguing for a methodology in a use case where its literally impossible to use mutexes and/or locking. The only reasonable software engineering decision here is to write lock-free code with guarantees of forward progress in these situations.
Its not easy. A lot of people mess it up. But that's what you have to do. No one ever said kernel hacking was easy. Someone has to write this code, and whoever does will likely use a lock-free methodology. This is where atomics and barriers shine.
> Lock-free code by itself doesn't guarantee forward progress.
I don't think you understand what lock-free code means. It literally means code that has guarantees for forward progress.
Its very difficult to write lock-free code. Very, very difficult. But the methodology is well known and well documented. (https://preshing.com/20120612/an-introduction-to-lock-free-p...)
You use these guarantees of forward progress (ex: on a 128-core computer, if all are doing compare_exchange_strong at the same time, then 1x of them will succeed, and 127x of them will fail. This is guaranteed, _SOMEONE_ succeeds and makes forward progress with lock-free primitives like compare_exchange_strong).
That means that if all 128x threads/cores call "compare_exchange_strong" 1x each, then after 128x calls every thread will have succeeded (ie: worst case, one thread will have to call it 128x times).
No. This isn't sufficient to have lock-free code yet. You now need to prove that you don't deal with live-lock issues or other such complex issues that come up (and you'll only get here in the first place if you wrote your memory-barriers correctly and lined everything else up perfectly).
But its a start. And with enough effort, study, sweat and tears, you'll be able to write a lock-free something and have a good functioning interrupt service routine.
No. You literally cannot use a mutex in interrupt service routines.
If you fail to understand why, then you don't understand fundamental OS and/or device driver issues and need to study up on that a bit more. This isn't something you use userland tools to solve either.
You're arguing for a methodology in a use case where its literally impossible to use mutexes and/or locking. The only reasonable software engineering decision here is to write lock-free code with guarantees of forward progress in these situations.
Its not easy. A lot of people mess it up. But that's what you have to do. No one ever said kernel hacking was easy. Someone has to write this code, and whoever does will likely use a lock-free methodology. This is where atomics and barriers shine.
> Lock-free code by itself doesn't guarantee forward progress.
I don't think you understand what lock-free code means. It literally means code that has guarantees for forward progress.
Its very difficult to write lock-free code. Very, very difficult. But the methodology is well known and well documented. (https://preshing.com/20120612/an-introduction-to-lock-free-p...)
You use these guarantees of forward progress (ex: on a 128-core computer, if all are doing compare_exchange_strong at the same time, then 1x of them will succeed, and 127x of them will fail. This is guaranteed, _SOMEONE_ succeeds and makes forward progress with lock-free primitives like compare_exchange_strong).
That means that if all 128x threads/cores call "compare_exchange_strong" 1x each, then after 128x calls every thread will have succeeded (ie: worst case, one thread will have to call it 128x times).
No. This isn't sufficient to have lock-free code yet. You now need to prove that you don't deal with live-lock issues or other such complex issues that come up (and you'll only get here in the first place if you wrote your memory-barriers correctly and lined everything else up perfectly).
But its a start. And with enough effort, study, sweat and tears, you'll be able to write a lock-free something and have a good functioning interrupt service routine.
Ah I had a reading comprehension fail. I never noticed in your first sentence you said interrupt code. Well then I do not profess to understand much about that.
> Lock-free code by itself doesn't guarantee forward progress.
I think we have some definition differences here. What I have seen and have alluded to previously when you use tools like compare_exchange_strong is that the underlying machine does not guarantee forward progress. When you have 128 cores calling compare_exchange_strong at the same time, yes 1 of them will succeed and 127 of them will fail. But there is no guarantee that for a particular core, it will eventually succeed; it could always be among the 127 failing ones. I often see that on NUMA systems where many cores running on a single CPU are competing against one core running on a remote CPU. Due to the way hardware works, that remote CPU consistently takes longer to do each atomic operation, leading it to always fail.
So no, after 128x calls not every thread will succeed.
> Lock-free code by itself doesn't guarantee forward progress.
I think we have some definition differences here. What I have seen and have alluded to previously when you use tools like compare_exchange_strong is that the underlying machine does not guarantee forward progress. When you have 128 cores calling compare_exchange_strong at the same time, yes 1 of them will succeed and 127 of them will fail. But there is no guarantee that for a particular core, it will eventually succeed; it could always be among the 127 failing ones. I often see that on NUMA systems where many cores running on a single CPU are competing against one core running on a remote CPU. Due to the way hardware works, that remote CPU consistently takes longer to do each atomic operation, leading it to always fail.
So no, after 128x calls not every thread will succeed.
> So no, after 128x calls not every thread will succeed.
I don't think you understand the situation I setup. Lemme try again from first principles.
-----------
In general, as long as you have proven that there is a *FINITE* amount of work to do, then when you prove forward progress (ie: at least one thread makes progress), you prove forward progress for the whole system.
Even if the "slowest-thread" loses every single time, eventually the 127x other threads run out of work, and the final thread can finally call compare_exchange_strong by itself. When it is the only thread calling the atomic, it will succeed (no one else can contradict, because everyone else has run out of work and is out of the loop).
Its as simple as "finite work" + "forward progress" == "eventual completion". Even in an imbalanced system where thread #128 is 128x slower than thread#1 and "loses the race" every single time... eventually thread#1 runs out of work (it succeeded so many times, its done). And the other threads get to finally run.
-------
Writing code that guarantees forward progress is the hard part however.
I don't think you understand the situation I setup. Lemme try again from first principles.
-----------
In general, as long as you have proven that there is a *FINITE* amount of work to do, then when you prove forward progress (ie: at least one thread makes progress), you prove forward progress for the whole system.
Even if the "slowest-thread" loses every single time, eventually the 127x other threads run out of work, and the final thread can finally call compare_exchange_strong by itself. When it is the only thread calling the atomic, it will succeed (no one else can contradict, because everyone else has run out of work and is out of the loop).
Its as simple as "finite work" + "forward progress" == "eventual completion". Even in an imbalanced system where thread #128 is 128x slower than thread#1 and "loses the race" every single time... eventually thread#1 runs out of work (it succeeded so many times, its done). And the other threads get to finally run.
-------
Writing code that guarantees forward progress is the hard part however.
In a general RPC system (which is where I have the most experience with) there cannot be finite amount of total work. What is finite is the rate of incoming work. If a thread finishes work early, the load balancer gives it more work. On the other hand if a thread doesn't make progress due to badly written atomics, or even an unfair mutex, that thread is stuck processing that one request indefinitely, which then reduces the rate of incoming work.
That said, your comment is very illuminating and I thank you for it. I'm glad we've resolved our definitional and perspective differences.
That said, your comment is very illuminating and I thank you for it. I'm glad we've resolved our definitional and perspective differences.
Yeah, the math for your situation is Queuing Theory, btw. A somewhat unrelated subject.
I'd say lock-free programming doesn't necessarily help that problem. Performance improvements are one of the keys, as the faster your code executes, the "shorter the queues get" because you're processing everyone faster in the system.
Queuing Theory is one of the weirder maths in Comp. Sci. I have mixed opinions on whether or not its really worth studying, as it covers very obvious truths. (The faster your code executes, the shorter lines get. Etc. etc.). I've seen the arguments that Queuing Theory is a lot of "obvious math" that you'll keep solving over-and-over again in parallel systems / code optimization however, so might as well formalize the concepts.
-----------
Queuing Theory is that all systems can be modeled as queues (aka: lines), where people stand in line waiting to be served. And "servers", who serve these people waiting in line. When someone is served, they move on to another queue / line up and wait for the next server to serve them.
You then do a bunch of math to see how long these lines get (ie: representing how much RAM you need to save all of these jobs) in a variety of random-distributions (poisson arrival times, etc. etc.).
I'd say lock-free programming doesn't necessarily help that problem. Performance improvements are one of the keys, as the faster your code executes, the "shorter the queues get" because you're processing everyone faster in the system.
Queuing Theory is one of the weirder maths in Comp. Sci. I have mixed opinions on whether or not its really worth studying, as it covers very obvious truths. (The faster your code executes, the shorter lines get. Etc. etc.). I've seen the arguments that Queuing Theory is a lot of "obvious math" that you'll keep solving over-and-over again in parallel systems / code optimization however, so might as well formalize the concepts.
-----------
Queuing Theory is that all systems can be modeled as queues (aka: lines), where people stand in line waiting to be served. And "servers", who serve these people waiting in line. When someone is served, they move on to another queue / line up and wait for the next server to serve them.
You then do a bunch of math to see how long these lines get (ie: representing how much RAM you need to save all of these jobs) in a variety of random-distributions (poisson arrival times, etc. etc.).
The thing is, seq-cst does not guarantee correctness, far from it. And you write down a proof, using the happen-before rules, the acquire/release edges are fairly obvious. So I don't think seq-cst buys you a significant amount of safety.
All the (C++) defaults are wrong, of course.
But in this case I believe the choice to have a default was itself the error. I have been persuaded that either you know which Ordering you need, and thus you should specify what you meant - or else you should not be using these APIs at all. If you aren't confident of the correct Ordering, you are not in fact confident your algorithm is correct, so don't do it.
But in this case I believe the choice to have a default was itself the error. I have been persuaded that either you know which Ordering you need, and thus you should specify what you meant - or else you should not be using these APIs at all. If you aren't confident of the correct Ordering, you are not in fact confident your algorithm is correct, so don't do it.
You are not wrong; still an std::atomic variant that defaulted to mo_release on assignment, mo_acquire on load and mo_aq_rel on RMW would have covered 99% of my use cases.
Then again, I usually target x86 where these defaults are optimal, in other architectures relaxing RMWs further has benefits.
Then again, I usually target x86 where these defaults are optimal, in other architectures relaxing RMWs further has benefits.
> The consume memory order is not used much.
That's because no compiler implements it, it just becomes an acquire in practice. Nobody has figured out how to maintain all the necessary invariants across all optimization passes.
That's because no compiler implements it, it just becomes an acquire in practice. Nobody has figured out how to maintain all the necessary invariants across all optimization passes.
memory_order_consume has been around since C++11, but discouraged.
If you want a good overview of what it is supposed to do,
https://preshing.com/20140709/the-purpose-of-memory_order_co...
goes into more detail with lots of examples and motivation.
If you want a good overview of what it is supposed to do,
https://preshing.com/20140709/the-purpose-of-memory_order_co...
goes into more detail with lots of examples and motivation.
So consume was added as a more surgical version of acquire. I see why that's useful. Why didn't they also add a surgical version of release? Wouldn't that also be useful in the same situations where consume is useful?
consume was implemented because real architectures provide data dependency on the load path (i.e. a load of a pointer value is never reordered past the a load of the pointed value). No architecture provides such a guarantee on the store path, unless , like TSO, provides it for all stores, so no point in specifying it in the standard.
Thanks, that makes sense
> Note that an acquire load of p would have prohibited this reordering, since acquire loads block all future memory access, even if unrelated to the value being acquired.
I don't really get this part. The docs for acquire say:
> memory_order_acquire A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load. All writes in other threads that release the same atomic variable are visible in the current thread
The prefetch is already ordered before the load in the same thread.
I don't really get this part. The docs for acquire say:
> memory_order_acquire A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load. All writes in other threads that release the same atomic variable are visible in the current thread
The prefetch is already ordered before the load in the same thread.
`sample_consume_allowed` is an example of a transformation that the compiler is permitted to apply to the original function `sample_consume`. if the original function had used `acquire` instead of `consume` then the reordering of the v2 load before the p load wouldn't've been allowed
Thank you, makes sense now
For a while the ISO documents claimed Consume was "Temporarily discouraged" and I believe now they just admit you'll get Acquire instead. Because Rust follows the C++ 11 Model (as revised) for lack of anything better, it deliberately does not mention Consume ordering either. https://doc.rust-lang.org/core/sync/atomic/enum.Ordering.htm...