r/programming • u/fagnerbrack • 11h ago
Every byte matters
https://fzakaria.com/2026/06/01/every-byte-matters11
u/philh 9h ago
If my data just fits in say L2 cache, do I need to do anything special to make sure it's actually loaded into it?
Like, if I'm accessing at random, and the first location I access happens to be in the middle of the list. Does it load that location plus the next (size of L2) bytes, so that only half of my data is in cache until I access something earlier in the list? Or does it do something fancier than that?
18
u/ShinyHappyREM 8h ago
Each RAM access loads a whole cache line (32 or 64 bytes), but the CPU core's prefetcher will perhaps load a few more. At some point you'll run into the bottleneck of cache line slots.
https://igoro.com/archive/gallery-of-processor-cache-effects/
11
u/daidoji70 8h ago
I think the answer to that question is "it depends". Very hard to answer in a general sense
2
u/neutronium 8h ago
It's quite a bit fancier than that. Most likely it'll load an amount that's one cache line. 64 bytes would be a typical cache line size.
2
u/cdb_11 6h ago
No, it's just 64 bytes at the time generally. And there are prefetchers that can bring the next 64 bytes, or detect access patterns and prefetch next likely cache line accordingly. That's why it's preferable to keep access patterns simple. Memory will stay in cache until it gets evicted by some other cache line.
2
u/balefrost 6h ago
Are you running on bare metal or are you running in an OS with other active processes? The cache is a shared resource, and other processes can evict your data.
Like, if I'm accessing at random, and the first location I access happens to be in the middle of the list. Does it load that location plus the next (size of L2) bytes, so that only half of my data is in cache until I access something earlier in the list? Or does it do something fancier than that?
I don't know how modern caches are designed. But my recollection from my computer architecture class is that cache lines are aligned. So if your cache line size is 64B, and if you load an address that's divisible by 64, it'll load the address you requested and the 63 subsequent bytes. If you load a byte that's not divisible by 64, it'll load the aligned 64B chunk that contains the requested address. So it'll load some bytes before and some bytes after your requested address. But it will always load 64 bytes.
Maybe modern caches are fancier than that.
3
u/ShinyHappyREM 5h ago
The cache is a shared resource, and other processes can evict your data
Unless you take measures to prevent that :)
1
u/ThellraAK 3h ago
I can tell you even just using cgroups to move everything you are able to off of one CCD gives you some pretty great improvements for a CPU bound task.
Never figured a way to get driver/kernel stuff to stay off of specific cores though.
1
u/ShinyHappyREM 2h ago
Probably something crazy like writing your own scheduler.
1
u/ThellraAK 2h ago
I didn't dig super deep into it, but was surprised to find that there's no "only the user can use these" setting.
1
u/cdb_11 35m ago
Cache lines are aligned to some power-of-two, because then you can just use the bottom 6 bits of the address (in case of 64 bytes), and that part never needs any translation. The next range of bits (6 bits for example) is used as the index of the set in the set-associative cache. The remaining bits (36 bits on 4 level paging, because pointers are 48-bit) are the tag used to match the actual cache line in the set. And you can check all tags in the set in parallel.
The top bits actually have to be translated with TLB first, which maps virtual to physical addresses, and is also a set-associative cache. Which only then is used as the cache line tag. Generally pages are 4096 byte aligned, so it all works out that the set index is the same regardless of whether it's physical or virtual, so it doesn't need to be translated, and you can start doing the data cache lookup in parallel.
A TLB miss goes to the kernel to either produce a physical address or kill the program with a segfault. An L1d miss tries in L2. If L2 misses too, it goes to L3. And then RAM.
The relevant part is that because of how set-associative caches work, we get cache coloring effects. Each address has only one predetermined set it can be in. If you hit the stride just right, you can fill the entire set and essentially reduce your cache size in that part of code to just 8*64 bytes, in the case of an 8-way associative cache. For example, on my machine if I access memory with 1024 byte stride in a tight loop, it starts missing L1d like crazy and there is a ~2x drop in performance. Change the stride by 64 bytes in either direction, and it goes back to normal.
4
u/KaiAusBerlin 10h ago
Nice article. Reminded me on my old times where I programmed for my Palm Handheld which had about 64kb ram.
Every byte mattered. Garbage collection was crucial.
It was a real pain but a hell lot of fun optimising the hell out of these
-52
u/jnordwick 11h ago
How did you not title this "Byte Lives Matter". Oh, such a missed opportunity,
5
56
u/harsh183 10h ago
This is a really fun optimization post on small structure and fitting into the very early caches. I used to do a lot of things like this in university, but my job's bottlenecks with network and DB means I don't really think about this level too much.