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

41–50 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#41

Post by moonchild »

FridgeSeal wrote: post #35
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…

Doesn’t KDB+ and one of the more esoteric array-based languages (J/Q or such?) essentially claim this?

Sort of (not in the sense meant by the parent), and it's nonsense regardless https://mlochbaum.github.io/BQN/implementation/kclaims.html#...

Re: Myths Programmers Believe about CPU Caches (2018)

#42

Post by throwawaylinux »

Dylan16807 wrote: post #39
throwawaylinux wrote: post #38

Earlier quoted context omitted.

It never presents an incoherent view to software. I'm using coherency as in the term of art, not a colloquial meaning. Every agent observes stores to a location in the same order[*]. Cache coherency says nothing about observed ordering of stores to different locations. [*] Although store forwarding throws a bit of a spanner in that definition, there can still be reordering occurring absent that local reordering.

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 trivial to program for, but that doesn't mean you can't trust it.

Re: Myths Programmers Believe about CPU Caches (2018)

#43

Post by ninepoints »

chrismarlow9 wrote: post #17
ninepoints wrote: post #3

Hmm, I think the discussion is missing a few things needed for a complete picture of the situation. 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. Second, synchronization isn't just because of register volatility and such. Synchronization is needed in general because without the appropriate lock…

Any recommendations for something more thorough to read or watch?

Honestly, the best resources I know are the ISA/architecture manuals directly from each vendor (Intel, AMD, Arm) for the various CPUs and/or GPUs of interest. Prior to that, my experience largely comes from doing (working with lower level code, benchmarks, looking at assembly, profiling hardware counters, etc.).

Re: Myths Programmers Believe about CPU Caches (2018)

#44

Post by klabb3 »

jcranmer wrote: post #21
notacoward wrote: post #18

Dealing with caches, memory ordering, and memory barriers can be truly mind-warping stuff, even for those who have spent years dealing with basic cache coherency before. If you want a challenge, try to absorb all this in one sitting. https://www.kernel.org/doc/Documentation/memory-barriers.txt I kept an earlier version of this close to hand at all times a couple of jobs ago where we were using our own chips with a ve…

You don't need that full documentation. Really, I could simplify what most programmers would need to understand about memory ordering down to this text: There are a few models of cross-thread memory ordering that you can choose between. If you have never been exposed to this field before, the naïve model of memory ordering you probably think is going on is sequential consistency. This is not implemented in hardware b…

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 majority of programmers, even low level folks.

What are your thoughts on this?

Re: Myths Programmers Believe about CPU Caches (2018)

#45

Post by garfieldandthe »

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 from the article) which are entirely unnecessary rather than code that needs to optimize for those things.

Re: Myths Programmers Believe about CPU Caches (2018)

#46

Post by girvo »

Kirby64 wrote: post #11
Tuna-Fish wrote: post #9

Earlier quoted context omitted.

Those numbers are for all cores. No modern CPU has anywhere near that of L1 and L2 per core.

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.

Re: Myths Programmers Believe about CPU Caches (2018)

#47

Post by gpderetta »

jcranmer wrote: post #21
notacoward wrote: post #18

Dealing with caches, memory ordering, and memory barriers can be truly mind-warping stuff, even for those who have spent years dealing with basic cache coherency before. If you want a challenge, try to absorb all this in one sitting. https://www.kernel.org/doc/Documentation/memory-barriers.txt I kept an earlier version of this close to hand at all times a couple of jobs ago where we were using our own chips with a ve…

You don't need that full documentation. Really, I could simplify what most programmers would need to understand about memory ordering down to this text: There are a few models of cross-thread memory ordering that you can choose between. If you have never been exposed to this field before, the naïve model of memory ordering you probably think is going on is sequential consistency. This is not implemented in hardware b…

> You get to pretend everything is sequentially consistent if you write proper synchronization. The easiest way to satisfy proper synchronization is an acquire-release model

But acquire/release give, generally,a partial ordering, not a total order like sequential consistency. That's often enough of course.

Re: Myths Programmers Believe about CPU Caches (2018)

#48

Post by pajko »

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…

This is partly wrong. For example, it's important how the fields are organized in a structure, and only the developer knows what belongs together and only they know the access patterns across threads (or at least should know). This is far from being a micro-optimization.

Re: Myths Programmers Believe about CPU Caches (2018)

#49

Post by gpderetta »

klabb3 wrote: post #44
jcranmer wrote: post #21

Earlier quoted context omitted.

You don't need that full documentation. Really, I could simplify what most programmers would need to understand about memory ordering down to this text: There are a few models of cross-thread memory ordering that you can choose between. If you have never been exposed to this field before, the naïve model of memory ordering you probably think is going on is sequential consistency. This is not implemented in hardware b…

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 your sanity), but for performance you still have to know how to map to the underlying microarchitecture.

Re: Myths Programmers Believe about CPU Caches (2018)

#50

Post by gpderetta »

throwawaylinux wrote: post #38
Dylan16807 wrote: post #36

Earlier quoted context omitted.

It's coherent behind the scenes but it often presents an incoherent view to the software. It's not acting coherent when the rearrangement of memory operations makes you see different orderings from different cores. When a CPU has a loose memory model and is aggressively making use of the reordering capabilities, the cache being coherent internally is basically just an implementation detail. It's not part of the visib…

It never presents an incoherent view to software. I'm using coherency as in the term of art, not a colloquial meaning. Every agent observes stores to a location in the same order[*]. Cache coherency says nothing about observed ordering of stores to different locations. [*] Although store forwarding throws a bit of a spanner in that definition, there can still be reordering occurring absent that local reordering.

Hum I don't see how store forwarding breaks the illusion of total order of stores on a single memory location, at least in 5 minutes of thinking I can't come up with a litmus that would demonstrate it. In fact even c++ relaxed stores and loads preserve this ordering.

I think your definition is correct without the asterisk.

edit: tweaked working

Post reply on HN