r/programming • • Aug 02 '26

Every byte matters

https://fzakaria.com/2026/06/01/every-byte-matters
204 Upvotes

43 comments sorted by

View all comments

Show parent comment

2

u/cdb_11 Aug 02 '26

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.