How much linear memory access is enough? • Hacker News Board

Re: How much linear memory access is enough?

#11

Post by corysama » Sat, Apr 11, 2026, 10:29 PM UTC

01HNNWZ0MV43FF wrote: post #6

This is good data, but I'm not sure what the actionable is for me as a Grug Programmer. It means if I'm doing very light processing (sums) I should try to move that to structure-of-arrays to take advantage of cache? But if I'm doing something very expensive, I can leave it as array-of-structures, since the computation will dominate the memory access in Amdahl's Law analysis? This data should tell me something about o…

Even in code where performance is a serious concern, you don't need to feel guilty about using a data structure that is an array of pointers to 4 kbyte chunks or a tree of such chunks. 4K is linear enough that using a completely flat array probably won't be significantly faster.

Re: How much linear memory access is enough?

#12

Post by senderista » Sat, Apr 11, 2026, 11:05 PM UTC

This kind of empirical analysis is helpful for things like sizing B-tree pages or unrolled linked list chunks.

Re: How much linear memory access is enough?

#13

Post by throwaway81523 » Sun, Apr 12, 2026, 5:32 AM UTC

PhilipTrettner wrote: post #2

I looked into this because part of our pipeline is forced to be chunked. Most advice I've seen boils down to "more contiguity = better", but without numbers, or at least not generalizable ones. My concrete tasks will already reach peak performance before 128 kB and I couldn't find pure processing workloads that benefit significantly beyond 1 MB chunk size. Code is linked in the post, it would be nice to see results o…

Doesn't it depend what you're doing? xz data compression or some video codecs? Retrograde chess analysis (endgame tablebases)? Number Field Sieve factorization in the linear algebra phase?

Re: How much linear memory access is enough?

#14

Post by PhilipTrettner » Sun, Apr 12, 2026, 6:14 AM UTC

sweetjuly wrote: post #10

I wonder how much of the cost is coming from the cache misses vs the more frequent indirections/ILP drop? For example, I wonder what this test looks like if you don't randomize the chunks but instead just have the chunks in work order? If you still see the perf hit, that suggests the cost is not from the cache misses but rather the overhead of needing to switch chunks more often.

that's a bit what the "repeated" scenario (roughly middle of the post) measures. It's not in work order but it is the same order every time, so caches work. And there you see that the working set size matters.

Note that the base setup has zero cache reuse because each run touches a completely different and cold part of memory. (that makes the result more of an upper bound on the needed chunk size)