Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

CPU cache-friendly data structures in Go

skoredin.pro

Post reply on HN
Print view View original

61–70 of 88 posts

Re: CPU cache-friendly data structures in Go

#61

Post by another_twist »

ardanur wrote: post #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 mu…

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

Re: CPU cache-friendly data structures in Go

#62

Post by nasretdinov »

OutOfHere wrote: post #35
nasretdinov wrote: post #24

Earlier 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?

Well, essentially Go doesn't have a separate async keyword because all goroutines run asynchronously under the hood. In the beginning the advised (and default) way of running Go code was GOMAXPROCS=1, essentially ensuring there is no actual parallelism, just asynchronous code. Since then, of course, around Go 1.5, the default switched to number of cores, making goroutines both async and parallel

Re: CPU cache-friendly data structures in Go

#63

Post by pjmlp »

OutOfHere wrote: post #21

If you are worrying about cache structure latencies in Go, maybe you should just be using Rust or Zig instead that implicitly handle this better.

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.

Re: CPU cache-friendly data structures in Go

#64

Post by mappu »

jandrewrogers wrote: post #42
gethly wrote: post #6

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

Some languages like Odin, ISPC, and Jai all have annotations that can automatically transform AoS to SoA. A key benefit is you can easily experiment to see if this helps your application, without doing a major refactor.

In https://github.com/golang/go/issues/64926 it was a bridge-too-far for the Go developers (fair enough) but maybe it could still happen one day.

Re: CPU cache-friendly data structures in Go

#65

Post by darccio »

furyofantares wrote: post #55

I waited half a day to post this, I think we aren't supposed to question if articles are LLM written - but this one really triggered my LLM-radar, while also being very well received. 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.)

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.

Re: CPU cache-friendly data structures in Go

#66

Post by danudey »

loeg wrote: post #47
danudey wrote: post #32

Earlier quoted context omitted.

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?

Maybe the point isn't narrower lines in L1 but wider lines in L2? Implicitly bringing in more data to the L2 cache but allowing the CPU to pick smaller chunks of it into L1 cache to work on. Something like a forced prefetch or something? Honestly no idea.

Re: CPU cache-friendly data structures in Go

#67

Post by danudey »

mtklein wrote: post #36
danudey wrote: post #30

Earlier quoted context omitted.

I could imagine some kind of compiler declaration in C that would do something like specify break points - sort of like page breaks - for structs, or tell the compiler to automatically pad structs out so that components are on page boundaries, cache line boundaries, etc. Sort of "If we're not properly aligned, add whatever padding you think is best here". I guess this is largely provided by std::hardware_destructive_…

I think this is _Alignas/alignas. struct foo { _Alignas(64) float x,y; _Alignas(64) int z; }; _Static_assert(sizeof(struct foo) == 192, "");

The example I linked uses alignas, but the key is knowing what value to pass. std::hardware_destructive_interference_size tells you what the current/target hardware's correct align value is, which is the challenge.

Re: CPU cache-friendly data structures in Go

#68

Post by jasonthorsness »

0x457 wrote: post #54
loeg wrote: post #45

Earlier quoted context omitted.

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

Yes, without repr(C) order and padding isn't guaranteed. You would use https://docs.rs/crossbeam-utils/latest/crossbeam_utils/struc... or similar to force fields not being on the same cache line.

huh TIL

"On modern Intel architectures, spatial prefetcher is pulling pairs of 64-byte cache lines at a time, so we pessimistically assume that cache lines are 128 bytes long."

Re: CPU cache-friendly data structures in Go

#69

Post by kbolino »

I don't see this mentioned anywhere else, but Go may start experimenting with rearranging struct fields at some point. The marker type structs.HostLayout has been added in Go 1.24 to indicate that you want the struct to follow the platform's layout rules (think of it like #[repr(C)] in Rust). This may become necessary to ensure the padding actually sits between the two falsely shared fields. You could combine it with the padding technique like this:

  type PaddedExample struct {
    _       structs.HostLayout
    Field1  int64
    _       [56]byte
    Field2  int64
  }

Re: CPU cache-friendly data structures in Go

#70

Post by furyofantares »

furyofantares wrote: post #60
ayuhito wrote: post #59

Earlier quoted context omitted.

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

> Are people supposed to be obligated to post such a report nowadays? No, typically when I ask questions it's optional. > I enjoyed the article and found it really interesting, but seeing these types of comments always kind of puts a damper on it afterwards. That is why I waited half a day, and until after there were lots of comments praising the article. Still, I'm sorry if it put a damper on it for you. Also the wh…

> But I didn't get that this time,

Actually, I take it back. I did think I was wasting my time when I noticed it was written by an LLM. But then I came back to HN an saw only praise and decided to wait a bit to see if people kept finding it useful before commenting.

I was somewhat excited by the prospect of this article being useful, but I've started to come around to my initial impression after another day. I don't really trust it.

Post reply on HN