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

21–30 of 62 posts

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

#21

Post by Arnavion »

yshui wrote: post #3

That's a cool find. I wonder if LLVM also does the other way around operation, where it pattern matches handwritten CAS loops and transform them into native ARM64 instructions.

I checked Godbolt, with RISC-V instead of ARM since I'm more familiar with that, and it doesn't look like it.

https://gcc.godbolt.org/z/b5s4WjnTG

(amomax is the atomic fetch-max instruction. lr and sc are load-reserved and store-conditional instructions; sc is like a regular store except it only succeeds if the address was not modified since the previous lr that accessed it. IOW the assembly is basically one-to-one with the C source.)

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

#23

Post by adgjlsfhk1 »

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?

This depends heavily on what concurrency optimizations your processor implements (and unfortunately this is the sort of thing that doesn't get doccumented and is somewhat hard to test).

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

#24

Post by Arnavion »

>Hold on. This wasn't a wrapper around a loop pattern - this was a first-class atomic operation, sitting right there next to fetch_add and fetch_or. Java doesn't have this. C++ doesn't have this. How could Rust just... have this?

C++26 (work-in-progress) does have std::atomic::fetch_max . Not implemented in any toolchains yet, though.

https://en.cppreference.com/w/cpp/atomic/atomic/fetch_max

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p04...

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

#25

Post by bilkow »

Arnavion wrote: post #24

>Hold on. This wasn't a wrapper around a loop pattern - this was a first-class atomic operation, sitting right there next to fetch_add and fetch_or. Java doesn't have this. C++ doesn't have this. How could Rust just... have this? C++26 (work-in-progress) does have std::atomic ::fetch_max . Not implemented in any toolchains yet, though. https://en.cppreference.com/w/cpp/atomic/atomic/fetch_max https://www.open-std.org…

That info is included later in the article:

> PS: After conducting this journey I learned that C++26 adds fetch_max too!

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

#26

Post by anematode »

adgjlsfhk1 wrote: post #23
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?

This depends heavily on what concurrency optimizations your processor implements (and unfortunately this is the sort of thing that doesn't get doccumented and is somewhat hard to test).

I did a little unscientific test here on an Apple M4 Pro with n threads spamming atomic operations with pseudorandom values on one memory location (the worst case). Used inline asm to make sure there was no funny business going on.

  atomic adds
  n = 1 ->  333e6 adds/second
  n = 2 ->  174e6
  n = 4 ->   95e6
  n = 8 ->   63e6

  atomic maxs
  n = 1 ->  161e6 maxs/second
  n = 2 ->   59e6
  n = 4 ->   39e6
  n = 8 ->   27e6

  atomic maxs with preceding check
  n = 1 ->  929e6 maxs/second
  n = 2 -> 1541e6
  n = 4 -> 3494e6
  n = 8 -> 5985e6
So evidently the M4 doesn't do this optimization. Of course if your distribution is different you'd get different results, and this level of contention is unrealistic, but I don't see why you'd EVER not do a check before running atomic max. I also find it interesting that atomic max is significantly slower than atomic add

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

#27

Post by thequux »

anematode wrote: post #26
adgjlsfhk1 wrote: post #23

Earlier quoted context omitted.

This depends heavily on what concurrency optimizations your processor implements (and unfortunately this is the sort of thing that doesn't get doccumented and is somewhat hard to test).

I did a little unscientific test here on an Apple M4 Pro with n threads spamming atomic operations with pseudorandom values on one memory location (the worst case). Used inline asm to make sure there was no funny business going on. atomic adds n = 1 -> 333e6 adds/second n = 2 -> 174e6 n = 4 -> 95e6 n = 8 -> 63e6 atomic maxs n = 1 -> 161e6 maxs/second n = 2 -> 59e6 n = 4 -> 39e6 n = 8 -> 27e6 atomic maxs with precedin…

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.

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

#28

Post by Jweb_Guru »

markcjeffrey wrote: post #19

Related: fetch_max is an instance of what the following SPAA 2013 paper calls an atomic "priority update" or atomic "write-with-max". This type of atomic operation can have much lower contention than its counterparts like atomic increment. https://doi.org/10.1145/2486159.2486189 https://jshun.csail.mit.edu/contention.pdf

One of the most practically important papers out there, I wish it were better known (but fortunately I think the "right" people know about it).

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

#29

Post by anematode »

thequux wrote: post #27
anematode wrote: post #26

Earlier quoted context omitted.

I did a little unscientific test here on an Apple M4 Pro with n threads spamming atomic operations with pseudorandom values on one memory location (the worst case). Used inline asm to make sure there was no funny business going on. atomic adds n = 1 -> 333e6 adds/second n = 2 -> 174e6 n = 4 -> 95e6 n = 8 -> 63e6 atomic maxs n = 1 -> 161e6 maxs/second n = 2 -> 59e6 n = 4 -> 39e6 n = 8 -> 27e6 atomic maxs with precedin…

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
Post reply on HN