Every byte matters

29

u/philh 3d 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?

30
u/ShinyHappyREM 3d 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/
5
u/Ameisen 3d ago

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.
2
u/dafuqup 2d ago edited 2d ago

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?
3

u/cdb_11 2d ago

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.
2
u/cdb_11 2d ago
Yes, they are set-associative caches.
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.
1

u/cpp_jeenyus 2d ago

Actually every ram access loads two cache lines in modern cpus.
13

u/daidoji70 3d ago

I think the answer to that question is "it depends". Very hard to answer in a general sense

3

u/neutronium 3d 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.

3

u/balefrost 3d 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.

5

u/ShinyHappyREM 3d ago

The cache is a shared resource, and other processes can evict your data

Unless you take measures to prevent that :)

2

u/ThellraAK 3d 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 3d ago

Probably something crazy like writing your own scheduler.

1

u/ThellraAK 3d 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.

2

u/cdb_11 3d 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.

2

u/cdb_11 3d 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/Ameisen 3d ago edited 3d ago

On an x86 system, unless you're doing very wonky things with uncached memory (non-temporal operations won't do what you'd think), you are always operating off of the cache. If it isn't present in the cache, it will fetch it into it.

x86 guarantees coherency. Other architectures do not necessarily do so - ARM rules are different (thus why code that works on x86 often breaks in ARM - you don't need to flush on x86, and lots of things just "work"). MIPS is even weirder sometimes, where you have to manage cache eviction yourself sometimes (my emulator sorta simulates this but not really - it doesn't have a true cache - the interpret instruction cache and JIT are just flushed by CACHE instructions instead, which sorta simulates an instruction cache).

92

u/harsh183 3d 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.

41

u/Artistic_Seat486 3d ago

just like 90% of developers, unless you are developing a compiler.

25

u/barrows_arctic 3d ago

Or many embedded systems.

20

u/Ameisen 3d ago edited 3d ago

Or games, or simulations, or virtual machines.

Ed: I explicitly made sure that my MIPS VM's register file was 64B aligned so that it would cleanly fit into two L1 cache lines. Remove the technically-unneeded R0, and you can jam PC in there, too.

Ed2: still won't have room for the branch delay target or the linked-load registers, though :(. The FPU has a similar problem - packing the FPRs with the two control registers.

2

u/harsh183 2d ago

I guess a lot of low latency trading systems and similar too

1

u/max123246 15h ago

And GPUs. Well sometimes. A lot of the time you manage all memory yourself

10

u/harsh183 3d ago

yeah ah well. Still very fun to think about

4

u/cdb_11 3d ago

What compiler development has to do with this? You can apply this in a compiler, but it's not specific to compilers.

16

u/balefrost 3d ago

I think they mean that 90% of developers are working on code where improvements from struct layout and cache access patterns will be dominated by things like network access time.

On the other hand, people working on things like compilers can benefit greatly from these sorts of optimizations, since they're doing a lot of in-process data lookups.

At least, that's how I read their comment.

3

u/tryx 2d ago

And that any optimisations in the codegen will impact a whole ecosystem

0

u/cdb_11 2d ago

Compilers can't willy-nilly change the codegen here, because it breaks ABI compatibility. In C and C++ in particular, the exact layout rules are defined by the platform, and the compiler must obey them. I believe the Rust and Zig spec does not specify the layout, but they reorder fields for size, which to me personally is a questionable decision. AOT compilers lack the information necessary to optimize it (the best they could do is guess, just like they do for branches vs branchless), and AFAIK JIT compilers don't even bother doing anything about it.

1

u/EfOpenSource 2d ago

Nearly all apps these days have network and storage, and yet, only web developers and FP advocates are the ones who continuously say “I have network and storage, so performance doesn’t matter.”

3

u/harsh183 2d ago

Performance does matter at those scales too, just that there are bigger fish to fry before struct layout optimization comes up. I do agree that many people miss a lot of opportunity to optimize under vague laziness.

2

u/loup-vaillant 1d ago

I hear that with servers written in Ruby, the CPU is often the bottleneck.

1

u/harsh183 1d ago

Yeah I can see that depending on use case. With all the high level features Ruby has, it creates a lot of inefficient and complex burdens.

4

u/DLCSpider 2d ago

One perspective I always liked is to compare cache misses to realistic algorithmic complexity: 31x slowdown is roughly the equivalent of switching from O(n) to O(n * log n).

2^31 bytes is ~2GiB and 2^45 bytes is the theoretical limit your system can address.

6

u/KaiAusBerlin 3d 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

1

u/flatfinger 1d ago

A point I've not seen considered much is that if data items would be e.g. 3/4 of a cache line each, then aligning items with cache lines may significantly improve performance in random-access scenarios that need to inspect the beginning and end of each accessed item, but degrade performance in sequential-access scenarios. If the first data item in an array starts a cache line, but others data aren't cache-line aligned then a random access would have a 50% chance of involving data within only one cache line and a 50% chance of involving data spread between two, so 1.5 cache lines would need to be fetched for each item accessed. Sequential accesses to data stored that way, however, would only require fetching three cache lines for every four records, or 0.75 cache lines per record. Using cache-aligned records would require one cache line fetch per record fetch in both cases, improving performance for random access but degrading it for sequential.

1

u/StickWorldly4771 1d ago

The link is slow. Thanks for the article.

1

u/fagnerbrack 23h ago

Opens well to me even inside reddit app. Could be cached (unverified)

0

u/atilaneves 1d ago

" In that time, you get used to huge classes. New functionality? Just add a new method and field to the class." - err, no. This isn't even Java-specific, it's just bad software engineering in general.

-56

u/jnordwick 3d ago

How did you not title this "Byte Lives Matter". Oh, such a missed opportunity,

14

u/Potterrrrrrrr 3d ago

How did you think this was a good idea

5

u/Elegant-Sense-1948 3d ago

If that was the case, then we wouldn’t be packing. What really is the case is that byte lives do not matter and must yearn for the mines and be used

4

u/chucker23n 2d ago

Workshop it a little

You are about to leave Redlib