Live data from Hacker News

From Rust to reality: The hidden journey of fetch_max

questdb.com

51–60 of 62 posts

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

#51
post #44

Earlier quoted context omitted.

> An example you'll see in say a modern C compiler is that if you write the obvious loop to calculate how many bits are set in an int, the actual machine code on a brand new CPU should be a single population count instruction, C provides neither intrinsics (like Rust) not a dedicated "popcount" feature, so you can't write that but it's obviously what you want here and yup an optimising C compiler will do that. C comp…

The existence of platform specific hacks is not interesting. In reality what happens is that software which has at any point cared about being portable doesn't use them. But yes stdc_count_ones is indeed the intrinsic you'd want here, and only a few years after I stopped writing C, so thanks for mentioning that. std::popcount is C++ but it's also kinda miserable that it took until C++ 20 and yet they still only lande…

Maybe we are just quibbling over semantics but the compiler intrinsic here is '__builtin_popcount'. 'stdc_count_ones' is a standard library element that presumably will be implemented using the intrinsic.

And FWIW all major C/C++ have for a long time have had a an intrinsic for this. In clang it even has the same name, Visual Studio it's something like just '_popcount'. So it has long been easy to roll your own macro that works everywhere.

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

#52

Earlier quoted context omitted.

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.

It doesn't need to be strictly increasing some other thread could be making other arbitrary operations. Still even in that case, as Dylan16807 pointed out, it likely doesn't matter.

> It doesn't need to be strictly increasing some other thread could be making other arbitrary operations

We're talking about collating a maximum, by definition every write to that is an increase.

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

#53

Earlier quoted context omitted.

It doesn't need to be strictly increasing some other thread could be making other arbitrary operations. Still even in that case, as Dylan16807 pointed out, it likely doesn't matter.

> It doesn't need to be strictly increasing some other thread could be making other arbitrary operations We're talking about collating a maximum, by definition every write to that is an increase.

If you are implementing a library function atomic::fetch_max, you cannot assume that every other thread is also performing a fetch_max on that object. There might be little reason for it, but other operations are allowed so the the sequence of modifications might not be strictly increasing (but then again, it doesn't matter for this specific optimization).

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

#54
post #49

Somewhat related: I find annoying that C++ doesn't have fetch_update and that Rust's fetch_update doesn't support LL/SC. Rust fetch_update uses the lowest common denominator, CAS, regardless of platform: https://godbolt.org/z/ncssGnsfx (see the call __aarch64_cas8_acq_rel). In hot loops this can mean double-digit perf loss.

It is very hard to support LL/SC in generalized user code as the specific rules of what cause an LL lease to fail are generally non-portable (possibly not even within an architecture).

It could be implemented with a CAS fallback of course, but it seems a performance trap.

You could add the logic to the compiler to detect which specific code sequences are LL/SC safe, but at that point just providing built-ins for the most common operations is simpler.

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

#55
post #44

Earlier quoted context omitted.

> An example you'll see in say a modern C compiler is that if you write the obvious loop to calculate how many bits are set in an int, the actual machine code on a brand new CPU should be a single population count instruction, C provides neither intrinsics (like Rust) not a dedicated "popcount" feature, so you can't write that but it's obviously what you want here and yup an optimising C compiler will do that. C comp…

The existence of platform specific hacks is not interesting. In reality what happens is that software which has at any point cared about being portable doesn't use them. But yes stdc_count_ones is indeed the intrinsic you'd want here, and only a few years after I stopped writing C, so thanks for mentioning that. std::popcount is C++ but it's also kinda miserable that it took until C++ 20 and yet they still only lande…

__builtin_popcount is not platform specific.

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

#56
post #44

Earlier quoted context omitted.

> An example you'll see in say a modern C compiler is that if you write the obvious loop to calculate how many bits are set in an int, the actual machine code on a brand new CPU should be a single population count instruction, C provides neither intrinsics (like Rust) not a dedicated "popcount" feature, so you can't write that but it's obviously what you want here and yup an optimising C compiler will do that. C comp…

The existence of platform specific hacks is not interesting. In reality what happens is that software which has at any point cared about being portable doesn't use them. But yes stdc_count_ones is indeed the intrinsic you'd want here, and only a few years after I stopped writing C, so thanks for mentioning that. std::popcount is C++ but it's also kinda miserable that it took until C++ 20 and yet they still only lande…

> In reality what happens is that software which has at any point cared about being portable doesn't use them.

I don't think this generalization is actually true. Fast portable software compiles conditionally based on the target platform, picking the fast platform-specific intrinsic, and falls back to a slow but guaranteed portable software implementation. This pattern is widespread in numerical linear algebra, media codecs, data compressors, encryption, graphics, etc.

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

#57
post #51

Earlier quoted context omitted.

The existence of platform specific hacks is not interesting. In reality what happens is that software which has at any point cared about being portable doesn't use them. But yes stdc_count_ones is indeed the intrinsic you'd want here, and only a few years after I stopped writing C, so thanks for mentioning that. std::popcount is C++ but it's also kinda miserable that it took until C++ 20 and yet they still only lande…

Maybe we are just quibbling over semantics but the compiler intrinsic here is '__builtin_popcount'. 'stdc_count_ones' is a standard library element that presumably will be implemented using the intrinsic. And FWIW all major C/C++ have for a long time have had a an intrinsic for this. In clang it even has the same name, Visual Studio it's something like just '_popcount'. So it has long been easy to roll your own macro…

Yes, just semantics. But I don't think I can agree that because you could have ensured this works portably people actually did. That's not been my experience.

Yesterday I watched that "Sea of Thieves" C++ 14 to C++ 20 upgrade story on Youtube, that feels much more like what I've seen - code that shouldn't have worked but it did, kept alive by people whose priority is a working game.

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

#58

Earlier quoted context omitted.

The existence of platform specific hacks is not interesting. In reality what happens is that software which has at any point cared about being portable doesn't use them. But yes stdc_count_ones is indeed the intrinsic you'd want here, and only a few years after I stopped writing C, so thanks for mentioning that. std::popcount is C++ but it's also kinda miserable that it took until C++ 20 and yet they still only lande…

__builtin_popcount is not platform specific.

OK, sure, vendor specific then. C23 does not promise this incantation, it's presumably a GCCism.

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

#59
post #9

This blog sent me into a memory models rabbit hole again. Each time I end up feeling like I'm finally starting to get it, only for a 6 line litmus test with 4 loads and 2 stores to send me crashing back down. It makes me feel a little better reading about the history of memory models in CPUs. If this stuff wasn't intuitive to Intel either, I'm at least in good company in being confused ( https://research.swtch.com/hw…

If you haven't seen it, Mara Bos' "Rust Atomics and Locks"[0] is an excellent book on this topic, even if you aren't particularly interested in Rust. [0]: https://marabos.nl/atomics/

Thank you, it looks lovely!

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

#60
post #40

Earlier quoted context omitted.

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 influe…

Sure, no doubt a non-atomic load would be dangerous to write in C, C++, or Rust rather than in assembly
Post reply on HN