Structure of arrays makes a lot of sense, reminds me of how old video games worked under the hood. It seems very difficult to work with though. I'm so used to packing things into neat little objects. Maybe I just need to tough it out.
CPU cache-friendly data structures in Go
41–50 of 88 posts
Re: CPU cache-friendly data structures in Go
#42Most of this should be handled by the compiler already. But it is only 2025, I guess we're just not ready for it.
How would that even work? The layout of data structures are constrained by many invariants not visible to the compiler (see also: auto-vectorization). It would be more work and boilerplate to add sufficient annotations to a data structure to enable the compiler to safely modify the layout than just using the layout you want.
Re: CPU cache-friendly data structures in Go
#43"Data Oriented Design" is more than just for performant code.
You can and perhaps should also use it to reason about and design software in general. All software is just the transformation of data structures. Even when generating side-effects is the goal, those side-effects consume data structures.
I generally always start a project by sketching out data structures all the way from the input to the output. May get much harder to do when the input and output become series of different size and temporal order and with other complexities in what the software is supposed to be doing.
Re: CPU cache-friendly data structures in Go
#44This is a really dense whirlwind summary of some common performance pitfalls. It's a nice overview in a sort of terse way. The same optimizations / patterns apply in other languages as well.
Re: CPU cache-friendly data structures in Go
#45If you are sweating this level of performance, are larger gains possible by switching to C, C++, Rust? How is Rust for micro-managing memory layouts?
You need to do the exact same kinds of thing in C/C++/Rust. I believe Rust struct layout is not guaranteed to match program order unless you use an annotation forcing it (repr(C)). (So to answer the question: it's great; as good as any other language for micromanaging layout.)
Re: CPU cache-friendly data structures in Go
#46> False Sharing : "Pad for concurrent access: Separate goroutine data by cache lines" This is worth adding in Go race detector's mechanism to warn developer
Most modern processor architecture CPU cache line sizes are 64 bytes, but not all of them. Once you start to put performance optimizations like optimizing for cache line size, you're fundamentally optimizing for a particular processor architecture. That's fine for most deployments, since the vast majority of deployments will go to x86_64 or arm64 these days. But Go supports PowerPC, Sparc, RISCV, S390X... I don't kno…
On which architecture are cache lines not 64 bytes? It's almost universal.
Re: CPU cache-friendly data structures in Go
#47Earlier quoted context omitted.
Most modern processor architecture CPU cache line sizes are 64 bytes, but not all of them. Once you start to put performance optimizations like optimizing for cache line size, you're fundamentally optimizing for a particular processor architecture. That's fine for most deployments, since the vast majority of deployments will go to x86_64 or arm64 these days. But Go supports PowerPC, Sparc, RISCV, S390X... I don't kno…
Something like C++17's `std::hardware_destructive_interference_size` would be nice; being able to just say "Align this variable to whatever the cache line size is on the architecture I'm building for". If you use these tricks to align everything to 64-byte boundaries you'll see those speedups on most common systems but lose them on e.g. Apple's ARM64 chips, and POWER7, 8, and 9 chips (128 byte cache line), s390x (256…
Apple arm64 supposedly has 64-byte L1 cache line size and 128-byte L2? How does that work? Presumably the lines are independent in L1, but can different cores have exclusive access to adjacent lines? What's the point of narrower lines in L1?
Re: CPU cache-friendly data structures in Go
#48Earlier quoted context omitted.
Not necessarily: you can go quite far with Go alone. It also makes it trivial to run "green threads" code, so if you need both (decent) performance and easy async code then Go still might be a good fit. Despite Go being pretty high level GC language on the surface it actually allows you to control stuff like struct layout, CPU affinity, etc, which typically matter more for performance than just a programming language…
In what way does Go have async?
Aren't goroutines by their nature asynchronous? Am I misunderstanding what you mean by 'async'?
Re: CPU cache-friendly data structures in Go
#49Earlier quoted context omitted.
In what way does Go have async?
Aren't goroutines by their nature asynchronous? Am I misunderstanding what you mean by 'async'?
Asynchronous is a programming style; it does NOT apply to Go. The goroutines run in parallel. Also, don't use complicated words when simple words will do.
Re: CPU cache-friendly data structures in Go
#50Earlier quoted context omitted.
Most modern processor architecture CPU cache line sizes are 64 bytes, but not all of them. Once you start to put performance optimizations like optimizing for cache line size, you're fundamentally optimizing for a particular processor architecture. That's fine for most deployments, since the vast majority of deployments will go to x86_64 or arm64 these days. But Go supports PowerPC, Sparc, RISCV, S390X... I don't kno…
Something like C++17's `std::hardware_destructive_interference_size` would be nice; being able to just say "Align this variable to whatever the cache line size is on the architecture I'm building for". If you use these tricks to align everything to 64-byte boundaries you'll see those speedups on most common systems but lose them on e.g. Apple's ARM64 chips, and POWER7, 8, and 9 chips (128 byte cache line), s390x (256…
Only landed in clang last year: https://github.com/llvm/llvm-project/pull/89446