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

From Rust to reality: The hidden journey of fetch_max

questdb.com

Post reply on HN
Print view View original

31–40 of 62 posts

Re: From Rust to reality: The hidden journey of fetch_max

#31

Post by SkiFire13 »

trws wrote: post #8
jerrinot wrote: post #4

Hi, author here. My superpower is spending unreasonable amounts of time researching things with no practical purpose. Occasionally I blog about it - as a warning to others.

I liked the article. I saw your PS that we added it to the working draft for c++26, we also made it part of OpenMP as of 5.0 I think. It’s sometimes a hardware atomic like on arm, but what made the case was that it’s common to implement it sub-optimally even on x86 or LL-SC architectures. Often the generic cas loop gets used, like in your lambda example, but it lacks an early cutout since you can ignore any input val…

> but it lacks an early cutout since you can ignore any input value that’s on the wrong side of the op by doing a cheap atomic read or just cutting out of the loop after the first failed CAS if the read back shows it can’t matter.

I believe this is a bit trickier than that, you would also need at least some kind of atomic barrier to preserve the ordering semantics of the successful update case.

Re: From Rust to reality: The hidden journey of fetch_max

#32

Post by adwn »

anematode wrote: post #18
trws wrote: post #8

Earlier quoted context omitted.

I liked the article. I saw your PS that we added it to the working draft for c++26, we also made it part of OpenMP as of 5.0 I think. It’s sometimes a hardware atomic like on arm, but what made the case was that it’s common to implement it sub-optimally even on x86 or LL-SC architectures. Often the generic cas loop gets used, like in your lambda example, but it lacks an early cutout since you can ignore any input val…

Curious: even with hardware atomics, wouldn't it be a good idea to first perform a non-atomic load to check for whether the store might be necessary (which would require the cache line to be locked), then only run the atomic max if it might change the value?

Yes, this can make sense if

- the value is often doesn't require an update, and

- there's contention on the cache line, i.e., at least two cores frequently read or write that cache line.

But there are important details to consider:

1) The probing load must be atomic. Both the compiler and the processor in general are allowed to split non-atomic loads into two or more partial loads. Only atomic loads – even with relaxed ordering – are guaranteed to not return intermediate or mixed values from other atomic stores.

2) If the ordering on the read part of the atomic read-modify-write operation is not relaxed, the probing load must reflect this. For example, an acq-rel RMW op would require an acquire ordering on the probing read.

Re: From Rust to reality: The hidden journey of fetch_max

#34

Post by anematode »

adwn wrote: post #32
anematode wrote: post #18

Earlier quoted context omitted.

Curious: even with hardware atomics, wouldn't it be a good idea to first perform a non-atomic load to check for whether the store might be necessary (which would require the cache line to be locked), then only run the atomic max if it might change the value?

Yes, this can make sense if - the value is often doesn't require an update, and - there's contention on the cache line, i.e., at least two cores frequently read or write that cache line. But there are important details to consider: 1) The probing load must be atomic. Both the compiler and the processor in general are allowed to split non-atomic loads into two or more partial loads. Only atomic loads – even with relax…

Thanks for your insights. (2) makes sense to me, but for (1), on ARM64 can an aligned 64-bit store really tear in a 64-bit non-atomic load? The spec says "A write that is generated by a store instruction that stores a single general-purpose register and is aligned to the size of the write in the instruction is single-copy atomic" (B2.2.1)

Re: From Rust to reality: The hidden journey of fetch_max

#35

Post by ibraheemdev »

anematode wrote: post #29
thequux wrote: post #27

Earlier quoted context omitted.

I think that this can change the semantics though; with the preceding check you can miss the shared variable being decremented from another thread. In some cases, such as if the shared value is monotonic, this is done, but not in the general case.

With a relaxed ordering I'm not sure if that's right, since the ldumax would have no imposed ordering relation with the (atomic) decrement on another thread and so could very well have operated on the old value obtained by the non-atomic load

It does make a difference of course if you're running fetch_max from multiple threads, adding a load fast-path introduces a race condition.

Re: From Rust to reality: The hidden journey of fetch_max

#36

Post by jerrinot »

delifue wrote: post #16

When reading I expected it to mention that each thread maintain thread local max and periodically sync to a global atomic can improve performance

I expect candidates to suggest similar optimisations, but I felt it was unnecessary for the article itself.

Re: From Rust to reality: The hidden journey of fetch_max

#37

Post by [deleted] »

ibraheemdev wrote: post #35
anematode wrote: post #29

Earlier quoted context omitted.

With a relaxed ordering I'm not sure if that's right, since the ldumax would have no imposed ordering relation with the (atomic) decrement on another thread and so could very well have operated on the old value obtained by the non-atomic load

It does make a difference of course if you're running fetch_max from multiple threads, adding a load fast-path introduces a race condition.

[deleted]

Re: From Rust to reality: The hidden journey of fetch_max

#38

Post by gpderetta »

anematode wrote: post #29
thequux wrote: post #27

Earlier quoted context omitted.

I think that this can change the semantics though; with the preceding check you can miss the shared variable being decremented from another thread. In some cases, such as if the shared value is monotonic, this is done, but not in the general case.

With a relaxed ordering I'm not sure if that's right, since the ldumax would have no imposed ordering relation with the (atomic) decrement on another thread and so could very well have operated on the old value obtained by the non-atomic load

All operations on a single memory location are always totally ordered in a CC system, no matter how relaxed the memory model is.

Also am I understanding it correctly that n is the number of threads in your example? Don't you find it suspicious that the number of operations goes up as the thread count goes up?

edit: ok, you are saying that under heavy contention the check avoids having to do the store at all. This is racy, and whether this is correct or not, would be very application specific.

edit2: I thought about this a bit, and I'm not sure i can come up with a scenario where the race matters...

edit3: ... as long as all threads are only doing atomic_max operations on the memory location, which an implementation can't assume.

Re: From Rust to reality: The hidden journey of fetch_max

#39

Post by masklinn »

ibraheemdev wrote: post #35
anematode wrote: post #29

Earlier quoted context omitted.

With a relaxed ordering I'm not sure if that's right, since the ldumax would have no imposed ordering relation with the (atomic) decrement on another thread and so could very well have operated on the old value obtained by the non-atomic load

It does make a difference of course if you're running fetch_max from multiple threads, adding a load fast-path introduces a race condition.

Does it tho? Assuming no torn reads/writes at those sizes, given the location should be strictly increasing are there situations where you could read a higher-than-stored value which would cause skipping a necessary update?

Afaik on all of x86, arm, and riscv an atomic load of a word sized datum is just a regular load.

Re: From Rust to reality: The hidden journey of fetch_max

#40

Post by adwn »

anematode wrote: post #34
adwn wrote: post #32

Earlier quoted context omitted.

Yes, this can make sense if - the value is often doesn't require an update, and - there's contention on the cache line, i.e., at least two cores frequently read or write that cache line. But there are important details to consider: 1) The probing load must be atomic. Both the compiler and the processor in general are allowed to split non-atomic loads into two or more partial loads. Only atomic loads – even with relax…

Thanks for your insights. (2) makes sense to me, but for (1), on ARM64 can an aligned 64-bit store really tear in a 64-bit non-atomic load? The spec says "A write that is generated by a store instruction that stores a single general-purpose register and is aligned to the size of the write in the instruction is single-copy atomic" (B2.2.1)

> […] on ARM64 […]

Well, if you target a specific architecture, then of course you can assume more guarantees than in general, portable code. And in general, a processor might distinguish between non-atomic and relaxed-atomic reads and writes – in theory.

But more important, and relevant in practice, is the behavior of the compiler. C, C++, and Rust compilers are allowed to assume that non-atomic reads aren't influenced by concurrent writes, so the compiler is allowed to split non-atomic reads into smaller reads (unlikely) or even optimize the reads away if it can prove that the memory location isn't written to by the local thread (more likely).

Post reply on HN