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

81–88 of 88 posts

Re: CPU cache-friendly data structures in Go

#81

Post by tapirl »

tapirl wrote: post #17

Source code of the benchmarks? At least, the False Sharing and AddVectors trick don't work on my computer. (I only benchmarked the two. The "Data-Oriented Design" trick is a joke to me, so I stopped benchmarking more.) And I never heard of this following trick. Can anyone explain it? // Force 64-byte alignment for cache lines type AlignedBuffer struct { _ [0]byte // Magic trick for alignment data [1024]float64 } Mayb…

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

Re: CPU cache-friendly data structures in Go

#82

Post by tapirl »

tapirl wrote: post #73
darccio wrote: post #65

Earlier quoted context omitted.

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. Almost all of them are false.

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

Re: CPU cache-friendly data structures in Go

#83

Post by 0x457 »

loeg wrote: post #72
jasonthorsness wrote: post #68

Earlier quoted context omitted.

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

That was true in like, 2011. I'm not sure if it's true anymore.

Pretty sure it started being a thing at Sandy Bridge and never stopped?

Re: CPU cache-friendly data structures in Go

#84

Post by furyofantares »

tapirl wrote: post #80
furyofantares wrote: post #79

Earlier quoted context omitted.

Here's the one that showed a lot more speedup than the article: https://pastebin.com/v9tczpus Looks like the LLM invented somewhat different test for it than the article had. I tried again and have this with the same data structure as in the article: https://pastebin.com/SDdcchZG That gave similar results to the article. All the other tests still give little-to-no speedup on my machine.

Many thanks for providing the source. It also works on my machine. TIL.

I tried the others on my x86 machine and they all do something for me - not nearly as much as the article, but something.

Re: CPU cache-friendly data structures in Go

#85

Post by tapirl »

furyofantares wrote: post #84
tapirl wrote: post #80

Earlier quoted context omitted.

Many thanks for providing the source. It also works on my machine. TIL.

I tried the others on my x86 machine and they all do something for me - not nearly as much as the article, but something.

The "_ [0]byte" trick has no base in my knowledge. For the author's specified example, [1024]float64 will be always allocated on one whole page, aka, always 64-byte aligned.

For "Array of Structs vs Struct of Arrays", using slices as fields is a good idea. If the purpose is to make fields allocated on their respective memory block, just use pointers instead.

Re: CPU cache-friendly data structures in Go

#86

Post by furyofantares »

tapirl wrote: post #85
furyofantares wrote: post #84

Earlier quoted context omitted.

I tried the others on my x86 machine and they all do something for me - not nearly as much as the article, but something.

The "_ [0]byte" trick has no base in my knowledge. For the author's specified example, [1024]float64 will be always allocated on one whole page, aka, always 64-byte aligned. For "Array of Structs vs Struct of Arrays", using slices as fields is a good idea. If the purpose is to make fields allocated on their respective memory block, just use pointers instead.

> The "_ [0]byte" trick has no base in my knowledge. For the author's specified example, [1024]float64 will be always allocated on one whole page, aka, always 64-byte aligned.

You're right - I read the results I had wrong on that one. That one is slower, not faster, on both my M2 and on x86 machine.

Re: CPU cache-friendly data structures in Go

#87

Post by tapirl »

furyofantares wrote: post #86
tapirl wrote: post #85

Earlier quoted context omitted.

The "_ [0]byte" trick has no base in my knowledge. For the author's specified example, [1024]float64 will be always allocated on one whole page, aka, always 64-byte aligned. For "Array of Structs vs Struct of Arrays", using slices as fields is a good idea. If the purpose is to make fields allocated on their respective memory block, just use pointers instead.

> The "_ [0]byte" trick has no base in my knowledge. For the author's specified example, [1024]float64 will be always allocated on one whole page, aka, always 64-byte aligned. You're right - I read the results I had wrong on that one. That one is slower, not faster, on both my M2 and on x86 machine.

My last comment has imprecision and misunderstanding.

> ... [1024]float64 will be always allocated on one whole page, aka, always 64-byte aligned.

if it is allocated on heap and at the start of allocated memory block.

> For "Array of Structs vs Struct of Arrays", using slices as fields is a good idea. If the purpose is to make fields allocated on their respective memory block, just use pointers instead.

I misunderstood it.

It is like row-based database vs. column-based database. Both ways have their respective advantages and disadvantages.

Re: CPU cache-friendly data structures in Go

#88

Post by loeg »

0x457 wrote: post #83
loeg wrote: post #72

Earlier quoted context omitted.

That was true in like, 2011. I'm not sure if it's true anymore.

Pretty sure it started being a thing at Sandy Bridge and never stopped?

I don't think the impact on adjacent cache lines is as severe as it was on Sandy Bridge.
Post reply on HN