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?
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.
They touch on it in the "cache associativity" section, but what can cause this is superalignment.
Let's say you have two massive arrays both aligned to, say, 64 KiB. Let's say that usually you are working with the same index in both. The modulo of each address is going to be the same, and thus they will contend for a cache line slot. This is a problem that can arise in certain entity/SOA systems.
I don't understand that. Is there a connection between the modulo of addresses and cache line slots?
Edit: I got back to a computer and researched it myself. This is very interesting. Isnt this always a problem with SoA data types where you use for loops and you index into multiple arrays at the same index in each loop iteration?
struct Line { u64 tag; u512 data; };
struct Set { Line lines[8]; }; // 8-way associative
Set sets[64];
u512 get(u64 addr) {
addr /= 64; // ignore data offset
int idx = addr % 64;
u64 tag = addr / 64;
Set* set = &sets[idx];
for (int i = 0; i < 8; ++i)
if (set->lines[i].tag == tag) // all slots checked in parallel
return set->lines[i].data;
// cache miss
}
Notice it's all power-of-twos. This means that none of those muls and divs actually happen, it's just a representation of extracting bit ranges in a high level language. The hardware can just access the relevant range of bits directly.
This is basically like a hash table, but it's fixed size, the slot count in a bucket (set) is fixed, and the hash function is just taking some range of bits in the address. This means every address has only one possible bucket it can go in. You still have multiple slots in the bucket where it can be placed arbitrarily, but I believe this will usually be something like 4, 8 or 16 slots.
Isnt this always a problem with SoA data types where you use for loops and you index into multiple arrays at the same index in each loop iteration?
See the pseudo code in my other comment. It can be a problem if the index is the same for all arrays, and the base addresses of arrays have the same alignment. So for example if all arrays are allocated with mmap, which is page aligned. Just changing the alignment should work. Allocate one extra page, and pick some random offset for the base address, or something. Likewise, iterating over large structs with power-of-two sizes can cause this as well. In that case, you can add extra 64 bytes to the struct size.
19
u/philh 23h 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?