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

Making Sense of Acquire-Release Semantics

davekilian.com

Post reply on HN
Print view View original

51–60 of 72 posts

Re: Making Sense of Acquire-Release Semantics

#51

Post by gpderetta »

moonchild wrote: post #34
gpderetta wrote: post #31

Earlier quoted context omitted.

Note that writing 64 bits and reading 32 (or viceversa) is not a way to get around fences on x86. It is explicitly documented as begin undefined. In most cases it will fail to store-forward that will stall and act as an implicit fence, but in some cases the CPU can do partial store forwarding, breaking it. AFAIK this trick does work on SPARC though.

It's not documented as being undefined; it's simply not documented at all. Intel's latest uarch does partial store forwarding. There was a paper from a few years ago trying to define semantics for mixed-size accesses (not for x86 though) https://www.cl.cam.ac.uk/~pes20/popl17/mixed-size.pdf I don't think the parent was talking about this, though; they were just talking about using a single large physical location, wh…

Ah, right, it was about guaranteed total order on all stores in a single memory location.

Re colocation and x86, IIRC the intel memory model has wordings regarding read and writes to a a memory location having to be of the same size to take advantage of the memory model guarantees.

Re: Making Sense of Acquire-Release Semantics

#52

Post by MaxBarraclough »

JonChesterfield wrote: post #21
mevric wrote: post #19

Earlier quoted context omitted.

I am curious to understand how the following is achieved? Is there a material on this? "storing two uint32 as a uint64"

Put them next to each other, 8 byte align the first one, use a compiler mechanism to disable alias analysis, do the uint64 store. Attribute((may_alias)) is the local override, fno-strict-aliasing the global one. I think C++ can now do "these bytes are now that type", called something like start_lifetime_as. C probably can't, though using a union might be legitimate. The language rules in this area are a mess.

There's no need to flirt with undefined behaviour and non-standard compiler flags. Just convert both uint32_t values to uint64_t type, then combine them into a single uint64_t value using bitwise shift then bitwise inclusive OR.

Rob Pike has blogged about this kind of thing. [0]

Perhaps also of interest: both C and C++ provide a (portable and standard) means of determining whether atomic operations on uint64_t are assured to be lock-free. [1][2] (Assuming of course that the uint64_t type exists - it's in the standard but it's optional.)

[0] https://commandcenter.blogspot.com/2012/04/byte-order-fallac... ( discussion: https://news.ycombinator.com/item?id=3796378 )

[1] https://en.cppreference.com/w/c/atomic/atomic_is_lock_free

[2] https://en.cppreference.com/w/cpp/atomic/atomic_is_lock_free

Re: Making Sense of Acquire-Release Semantics

#53

Post by [deleted] »

toast0 wrote: post #22
zevv wrote: post #3

Well written article, nice and to the point. Do recommend. Decades ago I declared myself too stupid to use shared memory with threading; I have learned to avoid this whenever possible, or abstract away the memory access under a safe layer as soon as possible. One of the greatest decisions of my career. Memory model semantics is one of the parts of systems programming that is generally poorly understood; I have had lo…

> Decades ago I declared myself too stupid to use shared memory with threading; I have learned to avoid this whenever possible, or abstract away the memory access under a safe layer as soon as possible. One of the greatest decisions of my career. This probably qualifies you to do shared memory threading, when it is needed. Such as debugging those abstraction layers. Knowing you don't understand it puts you in the rig…

[deleted]

Re: Making Sense of Acquire-Release Semantics

#54

Post by [deleted] »

gpderetta wrote: post #33
ajross wrote: post #24

Earlier quoted context omitted.

> What moonchild meant To spell it out: I know very well what moonchild meant, and am no stranger to lockless algorithm design or memory ordering semantics. It was a turn of phrase riffing on the point that "memory ordering semantics are APIs" and thus should have been designed with an eye toward clarity and comprehension for the working programmers who need to use them. Acquire/release was intended to make the job o…

I think it is just a generational difference. I learned lock-free programming during the standardization of the C++0x memory model and I do find acq/rel a simpler model to understand and analyse algorithms, while thinking in term of reorderings never clicked for me.

[deleted]

Re: Making Sense of Acquire-Release Semantics

#55

Post by klabb3 »

alfiedotwtf wrote: post #37

I’ve read so much through the years on this, and I feel like it’s our Emperor’s Clothes - people pretend to understand, but does anyone actually understand this magic? Like not theoretically-superficially but in practice, or am I just too dumb to see the King’s new attire?

Mozilla had this famous sign 8ft up on the wall that said “you must be this tall to write multi-threaded code”[1].

A lot of people will claim to be able to master it. The track record shows that even the superhuman domain experts make mistakes frequently, as it’s almost impossible to reason about, verify, debug and importantly maintain the invariants as code evolves. And good luck predicting performance implications on different CPUs and workloads. In either case, for software development it doesn’t really matter if there is such a hypothetical person: because nobody else is.

In practice it’s similar to protecting against crypto vulns: don’t roll your own, use trusted libs with very few hard-to-misuse data structures and operations, sometimes rely on lang/compiler features, and runtime analysis tooling.

Personally I think we eventually need an overhaul in language design, perhaps new concurrent control flow constructs and operations. Just look at the C code shown.. it’s not even “code” in the sense that one line does some logical operation scoped to the current function. No, it’s “markers” that tells compiler and CPU to flush internal caches, change their optimizations as a thread-global “operation”. And the post is introductory, SPSC which is much simpler, doesn’t cover thread parking, MESI, compiler reordering etc. It’s a red flashing sign that the abstractions are all whack, frankly. It’s the anti-thesis of a neat, modularized Russian dolls we typically enjoy with single threaded code, including C. Now, these things are still critical, they work and it’s the best we got. It’s a genuinely hard-hard problem, which is quite humbling given how prevalent, studied and important concurrency is to virtually every programming domain.

[1]: https://bholley.net/blog/2015/must-be-this-tall-to-write-mul...

Re: Making Sense of Acquire-Release Semantics

#56

Post by alfiedotwtf »

klabb3 wrote: post #55
alfiedotwtf wrote: post #37

I’ve read so much through the years on this, and I feel like it’s our Emperor’s Clothes - people pretend to understand, but does anyone actually understand this magic? Like not theoretically-superficially but in practice, or am I just too dumb to see the King’s new attire?

Mozilla had this famous sign 8ft up on the wall that said “you must be this tall to write multi-threaded code”[1]. A lot of people will claim to be able to master it. The track record shows that even the superhuman domain experts make mistakes frequently, as it’s almost impossible to reason about, verify, debug and importantly maintain the invariants as code evolves. And good luck predicting performance implications…

LOL nice! Ok, glad it’s not just me then. It’s actually one of the reasons why I flipped to Rust

Re: Making Sense of Acquire-Release Semantics

#57

Post by Veserv »

liblfds-temp wrote: post #49
liblfds-temp wrote: post #46

> See how we added a new fence() call to put()? That fixes the reordering problem we’ve described at length. Now if the CPU gets bored waiting for entries[i] to be read into the cache, and tries to pull up the tail++ line so it happens sooner, bonk!, the tail++ line hits that fence and stops moving. We’ve forced the entry to be written before the tail is bumped. Problem solved! I may be completely wrong, it's a compl…

A thread which performs a write, has a fence, and then performs another write, will at the time of the second write due to the fence guarantee the first write has completed. However, "completed" is misleading. The write will still not be seen by readers. "Complete" really means "the writer has done all the work he can do, which is necessary but insufficient". For a reader to see the write, the readers must issue a re…

You do not need a load barrier to observe stores from other cores. You need the load barrier so your own core does not reorder loads otherwise you could see wacky loads even if the stores are totally ordered.

As a example, suppose we have totally ordered stores, but loads can be reordered freely. Suppose X is 0 and Y is 0, then we store X to 1 then store Y to 1. Therefore, Y can only be 1 after X is 1. But, if you can load out of order, then you can load Y prior to the store, then load X after the store and see Y is 0 and X is 1 even though the store ordering guarantees Y is 1 only after X is 1.

Re: Making Sense of Acquire-Release Semantics

#58

Post by JonChesterfield »

MaxBarraclough wrote: post #52
JonChesterfield wrote: post #21

Earlier quoted context omitted.

Put them next to each other, 8 byte align the first one, use a compiler mechanism to disable alias analysis, do the uint64 store. Attribute((may_alias)) is the local override, fno-strict-aliasing the global one. I think C++ can now do "these bytes are now that type", called something like start_lifetime_as. C probably can't, though using a union might be legitimate. The language rules in this area are a mess.

There's no need to flirt with undefined behaviour and non-standard compiler flags. Just convert both uint32_t values to uint64_t type, then combine them into a single uint64_t value using bitwise shift then bitwise inclusive OR. Rob Pike has blogged about this kind of thing. [0] Perhaps also of interest: both C and C++ provide a (portable and standard) means of determining whether atomic operations on uint64_t are as…

If you do the loads as uint32, you lose the single atomic operations on two different values which was the whole point of this exercise.

Using a single uint64 as the memory type works, but you no longer have two different names fields and have to pack/unpack them by hand.

There's no ub if you use the compiler extension, just totally clear code that does the right thing

Re: Making Sense of Acquire-Release Semantics

#59

Post by moonchild »

gpderetta wrote: post #51
moonchild wrote: post #34

Earlier quoted context omitted.

It's not documented as being undefined; it's simply not documented at all. Intel's latest uarch does partial store forwarding. There was a paper from a few years ago trying to define semantics for mixed-size accesses (not for x86 though) https://www.cl.cam.ac.uk/~pes20/popl17/mixed-size.pdf I don't think the parent was talking about this, though; they were just talking about using a single large physical location, wh…

Ah, right, it was about guaranteed total order on all stores in a single memory location. Re colocation and x86, IIRC the intel memory model has wordings regarding read and writes to a a memory location having to be of the same size to take advantage of the memory model guarantees.

total order on all accesses to a given location—loads from a single location can't be reordered w.r.t. each other either

i don't remember seeing any wording relating to mixed-size accesses in the intel manual (not withstanding that the official models are ... ambiguous, to say the least, compared with what 3rd-party researchers have done)

Re: Making Sense of Acquire-Release Semantics

#60

Post by gpderetta »

moonchild wrote: post #59
gpderetta wrote: post #51

Earlier quoted context omitted.

Ah, right, it was about guaranteed total order on all stores in a single memory location. Re colocation and x86, IIRC the intel memory model has wordings regarding read and writes to a a memory location having to be of the same size to take advantage of the memory model guarantees.

total order on all accesses to a given location—loads from a single location can't be reordered w.r.t. each other either i don't remember seeing any wording relating to mixed-size accesses in the intel manual (not withstanding that the official models are ... ambiguous, to say the least, compared with what 3rd-party researchers have done)

For a total store order to be meaningful of course it implies that loads are also non visibly reordered. If a store falls in the forest but nobody is around to load it, was it really ordered :)
Post reply on HN