CPU Cache-Friendly Data Structures in Go

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 know enough about them, but I wouldn't be surprised if they weren't all 64-byte CPU cache lines. I can understand how a language runtime that is designed for architecture independence has difficulty with that.

For low-level small things tests can help. Go has good benchmarking built-in and you can use a tool that passes/fails based on statistically-significant regressions, benchstat (https://pkg.go.dev/golang.org/x/perf/cmd/benchstat).

That's just one prompt away!

Honestly I don't think there's much in here that's Go-specific other than the syntax itself. I've seen basically the same tricks used in C or C++.

Was there any particular part that felt like it needed more explanation?

Not really, virtually all these patterns involve tradeoffs that require understanding the data access patterns.

I don't want my compiler adding more padding than bare minimum to every struct. I don't want it transforming an AoS to SoA when I choose AoS to match data access patterns. And so on...

At best Go could add some local directives for compiling these optimizations, but these code changes are really minimal anyways. I would rather see the padding explicitly than some abstract directive.

    struct foo {
        _Alignas(64) float x,y;
        _Alignas(64) int     z;
    };
    _Static_assert(sizeof(struct foo) == 192, "");

or at least Linter should catch this

https://golangci-lint.run/docs/linters/

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.

I'm not sure if golang has the same fundamental issues in common use, but in e.g. C you don't want the compiler reordering your structs or adding arbitrary padding because that makes it incompatible with other in-memory representations - e.g. if you're using shared memory with another process that hasn't received the same optimizations, if you're loading raw data into memory/using mmap, etc.

Likewise, one of the examples is moving from an array of structs to a struct of arrays; that's a lot more complex of a code reorganization than you'd want a compiler doing.

It would be good to have a static analyzer that could suggest these changes, but, at least in many cases, you don't want them done automatically.

Do compiler ( GCC / llvm ) actually do that?

Are you thinking of some sort of annotation the compiler could read and handle?

Because if a compiler starts automatically padding all my structures to put all of the members on their own cache line I'm going to be quite peeved. It would be easy for it to do, yes, but it would be wrong 99%+ of the time.

A far more trenchant complaint is that Go won't automatically sort struct members if necessary to shrink them and you have to apply a linter to get that at linting time if you want it.

`runtime.LockOSThread()` will pin the current goroutine to the os thread that its currently running on

Interesting! Did you find out a way to bench this with the built in benchmarking suite?

I can't find any claim anywhere else about the [0]byte trick, and in fact my own experiments in the playground show that it doesn't do anything.

If you embed an AlignedBuffer in another struct type, with smaller fields in front of it, it doesn't get 64-byte alignment.

If you directly allocate an AlignedBuffer (as a stack var or with new), it seems to end up page-aligned (the allocator probably has size classes) regardless of the presence of the [0]byte field.

https://go.dev/play/p/Ok7fFk3uhDn

Example output (w is a wrapper, w.b is the field in the wrapper, x is an allocated int32 to try to push the heap base forward, b is an allocated AlignedStruct):

  &w   = 0xc000126000
  &w.b = 0xc000126008
  &x   = 0xc00010e020
  &b   = 0xc000138000

Take out the [0]byte field and the results look similar.

sorry, the False Sharing tick works. See https://news.ycombinator.com/item?id=45547441

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 of choice. There's a reason why e.g. VictoriaMetrics is still in Go even though they could've easily chosen any other language too

    Asynchronous is a programming style; it does NOT apply to Go.

    Also, don't use complicated words when simple words will do.

News for most folks, even writing C does not help, if neither of these advices are taken into account on how to lay out structures, nor algorithms are written with mechanical sympathy in mind.

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.)

Good programmers worry about the algorithms. Great ones worry about the data structures and the relationships between them. If memory serves, it was Kernighan.

> I'd love to know how much LLM was used to write this if any, and how much effort went into it as well (if it was LLM-assisted.)

Are people supposed to be obligated to post such a report nowadays?

I enjoyed the article and found it really interesting, but seeing these types of comments always kind of puts a damper on it afterwards.

The structure reads as LLM written. I don't mind this unless the content is utterly wrong. I was actually learning about cache-friendly data structures and I'm really interested in that cache-friendly Robin Hood hashing but now I worry it's a hallucination.

None of the tricks in this article get verified. It is totally solemn drivel.

Interesting and surprisingly, there are numerous praising comments here.