Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Myths Programmers Believe about CPU Caches (2018)

software.rajivprab.com

Post reply on HN
Print view View original

51–60 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#51

Post by sweetjuly »

mjg59 wrote: post #34
ggm wrote: post #5

My favourite myth is that I still believe it's possible to write code which operates totally out of L1 and L2 cache. Not just tight ASM on bare metal: C code or similar, compiled down, to run under a modern UNIX/POSIX os on a multi-core host. I have never explored HOW this would work, or WHAT I would do to achieve it, but I believe it, implicitly. For it to be true I would have to understand the implications of every…

As mentioned in another comment, this literally happens during system bringup when you don't have working RAM yet - link training involves a lot of state and you can't do it in registers alone, so the cache is configured in such a way that you can use it as RAM (I /think/ this is just a special case of write-back where you never actually do the write?). As long as you're not doing DMA I don't see any reason why you w…

> I /think/ this is just a special case of write-back where you never actually do the write?

Sort of! A typical implementation (from what I've seen, anyways) is that you have a memory mapped region which, when cache-as-RAM is activated, directly indexes into some cache (typically the LLC). From a hardware perspective, it's a full second address decode mode where you essentially just access the data array without performing tag check/write. When coming in to CAR mode, the cache typically needs to flush, but when leaving it really doesn't need to do anything (assuming it didn't update the tag array and left all lines as invalid).

With the size of some modern SoC's LLC, you could fairly easily run DOOM out of CAR. It'll depend on the SoC, but there's no reason why DMA wouldn't work as other agents would still be able to send read and write requests to the CAR memory region.

Re: Myths Programmers Believe about CPU Caches (2018)

#52

Post by flohofwoe »

garfieldandthe wrote: post #45

The central myth is that the average programmer should care. The typical programmer should treat CPU caches as what they are designed to be: mostly transparent. You work in a high level language and leave the tricky details to a library and your compiler. It's only a small minority that should really worry about these things. In my daily work, I see more often premature microoptimizations (in part using the myths fro…

You should still at least care about 'CPU friendly' data layout in memory and data access patterns in your code to make the CPU's life easier, compiler magic won't help all that much there.

This can often trivially give you a 10x, and sometimes a 100x performance difference for real-world single-threaded code, especially if it needs to work on big data sets. Your fancy high level compiler won't magically reshuffle your data in memory to help with prefetching (at least I'm not aware of a language that does).

Most high level languages popular today are "rooted" in the 90's when the latency gap between CPU and memory practically didn't exist and thus don't care about his specific aspect. Explicit control over memory layout is probably also one of the a main reasons why C stood the test of time so well.

Re: Myths Programmers Believe about CPU Caches (2018)

#53

Post by Dylan16807 »

throwawaylinux wrote: post #42
Dylan16807 wrote: post #39

Earlier quoted context omitted.

Fine, with that specific term of art meaning then ignore my second post. I stand by my original statement that you can't trust it to "do much for you". Just replace the last word with "act consistent" or "act ordered". Per-address ordering is nearly useless by itself. And if you had a CPU that didn't guarantee that, you'd observe almost no difference.

Well no, if you don't have a coherent system then your memory operations aren't reliable. You can lose updates or read stale data. Look at what software has to do in incoherent systems, specific flush and invalidate points which is not the same as ordering barriers. Your CPU guarantees a lot, cache coherency to start with. But also a very well defined ordering model and ordering instructions. It's not necessarily tri…

> You can lose updates

A system without cache coherency can still promise that updates won't be lost. There are lots of way to write rules around update propagation, and cache coherency is just one of them.

> or read stale data

Cache coherency doesn't protect you from stale data unless you only read one memory address ever.

> Look at what software has to do in incoherent systems, specific flush and invalidate points which is not the same as ordering barriers.

That depends on the memory model. You could have a system that doesn't guarantee cache coherency in general but works fine if you put in ordinary memory barriers.

Re: Myths Programmers Believe about CPU Caches (2018)

#54

Post by klabb3 »

gpderetta wrote: post #49
klabb3 wrote: post #44

Earlier quoted context omitted.

I’m nowhere near as deep in this rabbit hole. But I recall running/seeing some benchmarks on different memory orderings and the differences were not.. that big, on x86 I believe. Obviously there’s a lot that can go wrong with micro-benchmarks in these incredibly complex systems, but I still got the feeling that memory orderings are perhaps not worth the immense complexity that they introduce, for let’s say the majori…

At leas on x86, acq/rel load/stores vs relaxed is basically free. Seq/cst loads are also free. Seq/cst are relatively fast, but at around 20-30 clock cycles still measurably slower thant everything else. The catch is that x86 only has seq/cst atomic RMW so even if you ask for, say, a relaxed CAS or XADD, you will still get an expensive one. So the c++11 memory model allows you to more easily maintain correctness (and…

> Seq/cst are relatively fast, but at around 20-30 clock cycles

Did you mean to say seq/cst store?

Also, what operation is “set the value to X unconditionally and return me the previous value”? Is that possible with a store or something different? (Golang calls this op atomic swap)

In either case, sounds like the room for optimizing for performance with granular memory models on x86 is even narrower than I thought.

Re: Myths Programmers Believe about CPU Caches (2018)

#55

Post by gpderetta »

klabb3 wrote: post #54
gpderetta wrote: post #49

Earlier quoted context omitted.

At leas on x86, acq/rel load/stores vs relaxed is basically free. Seq/cst loads are also free. Seq/cst are relatively fast, but at around 20-30 clock cycles still measurably slower thant everything else. The catch is that x86 only has seq/cst atomic RMW so even if you ask for, say, a relaxed CAS or XADD, you will still get an expensive one. So the c++11 memory model allows you to more easily maintain correctness (and…

> Seq/cst are relatively fast, but at around 20-30 clock cycles Did you mean to say seq/cst store ? Also, what operation is “set the value to X unconditionally and return me the previous value”? Is that possible with a store or something different? (Golang calls this op atomic swap) In either case, sounds like the room for optimizing for performance with granular memory models on x86 is even narrower than I thought.

> Did you mean to say seq/cst store?

Indeed!

> set the value to X unconditionally and return me the previous value

That would be atomic::exchange that maps to XCHG on x86, which, as all atomic RMW is sequentially consistent.

Incidentally seq-cst stores are also typically lowered to XCHG on x86 as opposed to the more obvious MFENCE+MOV.

There is still room for optimization, as if you can implement your algos with just load/stores and as few strategically placed RMW as you can, it can be a win.

Of course if there is any contention, cache coherence traffic is going to dominate over any atomic cost.

Re: Myths Programmers Believe about CPU Caches (2018)

#56

Post by anonymousDan »

On the related topic of store buffers and write coalescing, can anyone point me to some good articles discussing how this works in practice for merging small writes to the same cache line? I have a workload where we are appending different size payloads (of sizes between 1 and 64 bytes) to an in memory log. One option is to just store each entry in its own cache line. A more space efficient option is to pack each write tightly one after the other. My hypothesis is that due to write coalescing in store buffers this will also be more memory bandwidth efficient since writes to the same cache line will be merged. Is this correct? Note that metadata for each entry (e.g. the size) will be stored separately.

Re: Myths Programmers Believe about CPU Caches (2018)

#57

Post by gpderetta »

Dylan16807 wrote: post #53
throwawaylinux wrote: post #42

Earlier quoted context omitted.

Well no, if you don't have a coherent system then your memory operations aren't reliable. You can lose updates or read stale data. Look at what software has to do in incoherent systems, specific flush and invalidate points which is not the same as ordering barriers. Your CPU guarantees a lot, cache coherency to start with. But also a very well defined ordering model and ordering instructions. It's not necessarily tri…

> You can lose updates A system without cache coherency can still promise that updates won't be lost. There are lots of way to write rules around update propagation, and cache coherency is just one of them. > or read stale data Cache coherency doesn't protect you from stale data unless you only read one memory address ever. > Look at what software has to do in incoherent systems, specific flush and invalidate points…

> You could have a system that doesn't guarantee cache coherency in general but works fine if you put in ordinary memory barriers.

How would that work? In such a system, either you have no caches or memory barriers would need to pessimistically flush all dirty lines to memory and send invalidation and synchronization messages to all other cores. In practice such system, far from being fine, would be so slow to be unusable if barriers had such semantics. Even implementing c++ relaxed semantics would be very expensive.

Re: Myths Programmers Believe about CPU Caches (2018)

#58

Post by gpderetta »

girvo wrote: post #46
Kirby64 wrote: post #11

Earlier quoted context omitted.

For context, the latest 7950x has 64KB of L1 per core, and 1MB L2

The L2 especially is more than enough for FreeRTOS though, thats 3 times the amount of memory my board has.

In the '80s you could run a fully preemptive-multitasking OS with a point-and-click GUI, games and office applications on 1MB of RAM.

Re: Myths Programmers Believe about CPU Caches (2018)

#59

Post by gpderetta »

ninepoints wrote: post #22
monocasa wrote: post #19

Earlier quoted context omitted.

> First, ARM and x86 coherency models differ, so a big disclaimer is needed regarding the protocol. Most ARM processors use the MOESI protocol instead of the MESI protocol. MOESI is called out. > The above are just some of the possible scenarios that can occur. In reality, there are numerous variations of the above design, and no 2 implementations are the same. For example, some designs have an O/F state. However tha…

Thanks I missed that line regarding the O states. Still, a word about write reordering on ARM would probably be useful (unless I missed that also). I understand that synchronization in code vs hardware is different, but the blog explicitly moves out of hardware-land into source code land with references to Java volatile and such.

The blog mentions about java volatiles (but it would also apply to C++ atomic) to explicitly mention that volatile has no cache coherency implications on a typical MESI (and variants) machine. The fences required to maintain language level memory model guarantees act at a level above the L1 cache, once the data reaches L1 (i.e. the coherence point), the fences have done their job.

[I'm ignoring remote fences which are a specialized and not yet mainstream feature]

Re: Myths Programmers Believe about CPU Caches (2018)

#60

Post by automatic6131 »

ChrisMarshallNY wrote: post #13

We worked with the Intel guys, in my last gig. They were incredibly helpful. They were an impressive lot, and they helped us out, quite a bit. They often sent engineers over, for weeks at a time, to help us optimize. The cache thing was a 100X improvement thing, and it came from the oddest places. There's a lot of "that doesn't make sense!" stuff, with preserving caches. I don't remember all the tricks, but we were c…

It seems Intel is full of great engineers. I wonder why their latest products have been behind the competition for the last 5-6 years?
Post reply on HN