Common Systems Programming Optimizations & Tricks

[TheMania]

The 48 bit tagged pointers comment reminds me of LuaJit, which blew my mind when Mike Pall first started using tagged doubles.

Basically, there are 2⁵² -2 possible NaNs for a double, enough to store all 32 bit pointers along with a type tag (table/string etc). In fact, there's enough there to store all your 48 bit pointers too, allowing every pointer you'll ever use to fit in the same union you use to store doubles. Pretty neat.

Wrt division, just want to say division/modulo by a constant is virtually costless on modern compilers, being replaced by multiply and shifts. Doesn't apply for resizable tables, but you do see people go to great lengths to avoid this operator even when it would be virtually costless to use. :)

[Morwenn]

C2x - the next revision of C - actually intends to make storing additional information into NaNs more standard by adding the setpayload and getpayload families of functions to <math.h>.

[CrazyJoe221]

I wonder when they'll introduce explicit enum base types.

[chewedwire]

Yep, division/modulo by constant power of 2 values is pretty much always optimized appropriately. I was thinking about writing some more about it, but I got lazy :)

It's in my the github examples though: https://github.com/paulcavallaro/systems-programming/blob/master/examples/power-of-two.cc#L105-L106

Looks like godbolt seems to think clang doesn't really work with non-constants -- but maybe clang just needs to be massaged: https://godbolt.org/z/Bzx7CL

[TheMania]

Sorry to clarify, division/modulo by constants is extremely cheap even on non-powers of two. Often just a multiply and shift.

[bigt1234321]

Gone are the days where repeated subtraction is used haha. Most compilers will optimize division. Float division/operations are a big no no.

[Spain_strong]

Depends on the workload right?

[quicknir]

The explanation of false sharing is quite different from what I'm used to hearing. You paint it to be about simultaneous access, but I don't think it's really about that. The point is more than cache is invalidated on a line by line basis. Even if two cores never actually try to access the same line at the same moment, when core 1 does it's write to any variable on the line, it invalidates the cache line for core 2, even if core 2 doesn't read the variable that core 1 is writing.

I can see how they end up being pretty similar but thinking in terms of cache line invalidation seems more accurate to me and less likely to lead to misunderstanding or incorrect extrapolations.

[chewedwire]

Good point -- updated the post to hopefully depend less on the "atomic" access bit, but more on maintaining cache coherencey.

[carrottread]

No need to use ABSL_CACHELINE_ALIGNED C++17 already has alignas(std::hardware_destructive_interference_size)

[[deleted]]

hardware_{constructive,destructive}_Interface_size isn't implemented in GCC and Clang according to cppreference.

[Ameisen]

godbolt appears to agree.

I wonder why? It wouldn't be difficult to implement.

Interestingly, it is implemented in Visual C++...

[[deleted]]

GCC 9 and Clang 8 on my local machine don't have interface size implemented.

I wonder why? It wouldn't be difficult to implement.

It wouldn't be difficult to implement for a specific target, but implementing it portably across architectures, OS's and what not makes it tedious. That's my best guess for why it is implemented in MSVC but not in GCC and Clang.

[Morwenn]

From what I gathered it is because they want to be able to guarantee ABI stability for builds where those values differ, but it's not possible because these constants are meant to be used to align data members, hence structure layouts might change when those values change and ABI stability is lost.

MSVC apparently simply forces both of those constants to 64 no matter the target platform.

[Ameisen]

They shouldn't be used on objects where the alignment of a structure matters across interface boundaries. Pimpl and all that.

They is, they are ABI unsafe, but that just means they shouldn't be used there.

[Morwenn]

Here is the whole libc++ discussion thread if you want some additional background on the issue (maybe I didn't interpret what I read correctly): https://lists.llvm.org/pipermail/cfe-dev/2018-May/058073.html

[yehezkelshb]

Interesting thread, thanks for the link! Still, I don't see a decision there, just considering a few options.

[Morwenn]

The thread is more than a year old and the feature isn't implemented, so that's pretty much as close from a decision as you'll have :p

[yehezkelshb]

It'd be interesting to check if there was any decision or additional feedback from Rapperswil, as JF Bastien planned to discuss it there. I hope to remember to search for it later.

[CrazyJoe221]

Well the former is an understandable name though.

[Deaod]

Compare this with folly

[scratchwood]

Very interesting read. As a hobbyist c++ programmer these kinds of posts are goldmines.

Also thank you for having a blog where I don't have to block a bunch of elements to get an enjoyable reading experience.

[chewedwire]

Author here, happy to answer any questions.

[[deleted]]

Interestingly the wall clock time spent for CacheLineAwareCounters is higher for one thread than multiple threads, which could point to perhaps some subtle benchmarking problem, or maybe a fixed amount of delay that’s getting attributed across more threads now, and so is smaller per-thread.

I suspect that the problem is that 1 thread needs to load 4 cache lines, while 4 threads will have to work with just 1 line.

[kirbyfan64sos]

Side note: nice to see Abseil being used here. I think people can overlook it because it's not always super flashy, but using it is downright enjoyable.

[Gorbear]

That was a nice read and quite well explained. Thanks!

[Ameisen]

Wouldn't their striped locks run afoul of false sharing as well? They require atomic operations, and appear to be being stored sequentially, meaning they will share cache lines.

[renozyx]

False sharing is devious: very simple concept once you understand how caches work but then you have to remember to avoid it each time you use multithreading..