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

21–30 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#21

Post by jcranmer »

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 because oh-gosh-it's-expensive, and if there's no indication of what memory ordering model your library or language is using, it's likely defaulting to sequential consistency.

But don't worry, you don't have to worry about the more complex memory orderings, because 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. Before reading any data that may have been written by a different thread, you need to do an acquire load. After writing any data that may be read by a different thread, you need to do a release store. The basic flow is write then release store, then change thread, then acquire load, then read. Follow this rules, and things stay simple.

There is a theoretical slight relaxation of the above model that works on most hardware called release-consume in the C/C++ memory model. It isn't implemented by any compiler for arcane compiler reasons I won't get into, but the Linux kernel (which implements the memory model itself for $REASONS) does rely heavily on it.

The final major memory ordering is relaxed atomics. Their semantics are... weird. Essentially, you get what the hardware gives you, plus whatever fun the compiler can toss in, and the guarantees are minimal. I can't recommend many cases where you can safely use it, and if you have to ask if you should use it, the answer is no.

Re: Myths Programmers Believe about CPU Caches (2018)

#22

Post by ninepoints »

monocasa wrote: post #19
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…

> 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.

Re: Myths Programmers Believe about CPU Caches (2018)

#23

Post by notacoward »

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…

Oh, you suppose the authors spent their time writing that for no reason? You know better than them? Your explanation is so incomplete I hardly know where to begin. Maybe with the fact that you're talking about local ordering as it may or may not be perturbed by a compiler, while the document is talking about the observed order elsewhere (other processors or main memory). That observed order can vary depending on the processor's ordering model, and to ensure it (e.g. across all modifications to a complex shared data structure) without doing the memory equivalent of an fsync() on every file write (disastrous!) you need memory barriers. All of the bugs I mentioned, all of which were crashes, were related to exactly the distinction you're missing. Yours is the kind of mythology that OP sought to address. Please read the document - particularly the section on CPU memory barriers and anywhere that mentions Alpha - before spreading more misinformation.

Re: Myths Programmers Believe about CPU Caches (2018)

#24

Post by hinkley »

Dylan16807 wrote: post #10

This article gives the impression that everything is the compiler's fault when you end up with conflicting reads in different cores, but that's not right. From the point of view of someone outside the CPU, yes you can say that simultaneous reads might never give different answers. But everything happening at that level barely resembles the original software. Dozens of instructions are happening at any moment, overlap…

Which is why the Java Memory Model exists, and why a number of other languages just copied it.

A lot of problems with threading got sorted out under the auspices of making Java work right on your hardware/operating system.

Re: Myths Programmers Believe about CPU Caches (2018)

#26

Post by jcranmer »

notacoward wrote: post #23
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…

Oh, you suppose the authors spent their time writing that for no reason ? You know better than them? Your explanation is so incomplete I hardly know where to begin. Maybe with the fact that you're talking about local ordering as it may or may not be perturbed by a compiler, while the document is talking about the observed order elsewhere (other processors or main memory). That observed order can vary depending on the…

> Oh, you suppose the authors spent their time writing that for no reason? Your explanation is so incomplete I hardly know where to begin.

No. I am suggesting that you don't need the full rigor of understanding the memory barrier semantics to be able to effectively write multithreaded code correctly. Completeness was never a goal of my explanation; sufficiency was. Furthermore, my focus is on a software memory model, not the hardware memory model.

> Maybe with the fact that doing acquire/release for one value has varying effect (sometimes none) on others, so you'd have to do it separately for all of the many values that might have changed.

You have misinterpreted my words, I think. At no point do I suggest that you should insert an acquire/release for each, individual value. Rather, you need to do an acquire at the beginning of a block of code (wherein you can read and write multiple values) and a release at the end of a block of code, much as you would with a mutex (except it's not necessary that the regions of code actually be mutually excluded from executing on multiple threads). The only requirement is that the store be followed by a release operation that crosses threads to an acquire operation that is followed by a load.

> Then we can move on to the concept of dependent reads, and so on.

I allude to those under the part where I mention "There is a theoretical slight relaxation of the above model that works on most hardware called release-consume in the C/C++ memory model." That you did not pick up on that is perhaps because you yourself are unfamiliar with the release-consume portion of the C/C++ memory model. If you need a refresher, I might point you to the thread where I actually go into why it exists, and why it's not implemented by compilers, here: https://news.ycombinator.com/item?id=36059369. (There's a reason I'm not going into it in a facile explanation!)

> Please read the document before you spread more misinformation.

Oh, do trust me, I have read that document, and far more, on memory models. I am not spreading misinformation. Perhaps my word choice and my writing is inartful or oversimplified in the goal of making the topic more accessible rather than seeking to enshrine comprehensive knowledge in thick tomes that many will give up reading. Perhaps you yourself may not be sufficiently informed as to pick up on the specific terminology that I use, which derives from the dominant memory model in use by, well, everybody.

Re: Myths Programmers Believe about CPU Caches (2018)

#27

Post by jcranmer »

hinkley wrote: post #24
Dylan16807 wrote: post #10

This article gives the impression that everything is the compiler's fault when you end up with conflicting reads in different cores, but that's not right. From the point of view of someone outside the CPU, yes you can say that simultaneous reads might never give different answers. But everything happening at that level barely resembles the original software. Dozens of instructions are happening at any moment, overlap…

Which is why the Java Memory Model exists, and why a number of other languages just copied it. A lot of problems with threading got sorted out under the auspices of making Java work right on your hardware/operating system.

Strictly speaking, the Java Memory Model derives from the data-race-free model of the early '90s. Java was the first programming language to explicitly incorporate it as part of the specification, but the main derivation actually comes from the C++ memory model, which built into it the basic atomic memory model that most derivatives rely on--Java doesn't have the weaker atomics support that C++ added, just sequentially-consistent. Java also introduced some frankly confusing (and incorrect, per my understanding) semantics for what happens in the face of data races that everybody else just shrugged and said "let's make it be UB and call it a day."

Re: Myths Programmers Believe about CPU Caches (2018)

#28

Post by slashdev »

thfuran wrote: post #14
Kirby64 wrote: post #11

Earlier quoted context omitted.

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

And I know we were talking about L1/2, but Epycs can have over 1GB of total L3.

You could boot Windows XP or Linux in that comfortably. Even run an older web browser or computer game. That’s crazy!

Re: Myths Programmers Believe about CPU Caches (2018)

#29

Post by hashmash »

jcranmer wrote: post #27
hinkley wrote: post #24

Earlier quoted context omitted.

Which is why the Java Memory Model exists, and why a number of other languages just copied it. A lot of problems with threading got sorted out under the auspices of making Java work right on your hardware/operating system.

Strictly speaking, the Java Memory Model derives from the data-race-free model of the early '90s. Java was the first programming language to explicitly incorporate it as part of the specification, but the main derivation actually comes from the C++ memory model, which built into it the basic atomic memory model that most derivatives rely on--Java doesn't have the weaker atomics support that C++ added, just sequential…

> Java doesn't have the weaker atomics support that C++ added

Yes it does, but it doesn't have first-class keywords to represent these modes. You have to use the VarHandle class, which is a bit kludgy.

https://docs.oracle.com/en/java/javase/20/docs/api/java.base...

Re: Myths Programmers Believe about CPU Caches (2018)

#30

Post by jcranmer »

hashmash wrote: post #29
jcranmer wrote: post #27

Earlier quoted context omitted.

Strictly speaking, the Java Memory Model derives from the data-race-free model of the early '90s. Java was the first programming language to explicitly incorporate it as part of the specification, but the main derivation actually comes from the C++ memory model, which built into it the basic atomic memory model that most derivatives rely on--Java doesn't have the weaker atomics support that C++ added, just sequential…

> Java doesn't have the weaker atomics support that C++ added Yes it does, but it doesn't have first-class keywords to represent these modes. You have to use the VarHandle class, which is a bit kludgy. https://docs.oracle.com/en/java/javase/20/docs/api/java.base...

Okay, it looks like those were added in Java 9, which was after I stopped following Java (and well after the C++ memory model was largely settled, in 2007).
Post reply on HN