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

81–90 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#81

Post by _a_a_a_ »

flohofwoe wrote: post #52
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 yo…

> This can often trivially give you a 10x, and sometimes a 100x performance difference for real-world single-threaded code

That's one hell of a lot of speed up, can you explain how you managed that? I mean I can certainly believe it but not when you put "trivially" in front of it, I could only conceive of that in very special cases and with very careful coding.

Re: Myths Programmers Believe about CPU Caches (2018)

#82

Post by jcranmer »

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…

As noted elsewhere, x86 itself really doesn't have much difference. But it matters a lot more on other architectures--I caused like a 20-30% regression in JS performance on ARM by changing one atomic variable in the engine to sequentially-consistent instead of release-acquire.

My recommendations boil down to the following:

* If you're ever truly unsure, just stick with sequentially-consistent unless performance is so critical you need to get off of it. Correctness is more important that speed!

* You can use acquire/release if you've got something that smells sufficiently like a lock (there's a clear scope with beginning and end, and most of the memory accesses outside the acquire/release themselves are regular, unsynchronized accesses). Most of this code should probably be hidden in libraries anyways, but this probably should be your basic default if you're working with atomics if there's only one atomic variable in play.

* The other memory orderings I wouldn't recommend at all. Release/consume, even were it implemented by compilers as intended, requires a particular (though common) set of circumstances to work correctly. Relaxed affords no synchronization opportunities, and the one use case I can think of for it involves atomic read-modify-write operations, which I think all hardware makes as strong as an release+acquire anyways.

In short, worrying about sequential consistency versus release/acquire can be helpful, and I think there are simple enough rules-of-thumb to make it worthwhile to summarize it. The other memory orderings, not so much.

Re: Myths Programmers Believe about CPU Caches (2018)

#83

Post by notacoward »

jcranmer wrote: post #79
notacoward wrote: post #76

Earlier quoted context omitted.

> dominant memory model in use by, well, everybody. "...by, well, x86" Fixed that for you.

No, you didn't. It's the C++ memory model, which is borrowed by C, then every compiler IR targeting something in the C/C++ space, and then every other language that decided to support language-level atomics. Your mistake is thinking solely in terms of the hardware memory model. Indeed, if you care only about x86 (and ignore the potential for compiler optimizations), most of the variety provided by the C/C++ memory mo…

So your incomplete explanations are based on a single language model instead of a single processor model? Sorry, that's a distinction without a difference. It's no excuse for misleading people who might use other languages or processors. And stop with the implied insults about my level of knowledge, when you're the one clearly fixated on only one environment. That's both rude and stupid. I've worked on many CPU architectures, on NUMA and COMA systems long before most people even knew such things existed, at many different levels from the first instruction after an exception (or restart) on up. I say that not to make my own appeal to authority, but to refute yours and to underscore that these "irrelevant" details are in fact highly relevant and important to some of us out here in the wider world. I haven't been alone in any of those things. There are still many programmers working in "exotic" environments where these things matter, and we both rely on their work every day. You should at the very least qualify your statements to say that they're only true for application level programmers like yourself.

Re: Myths Programmers Believe about CPU Caches (2018)

#84

Post by jcranmer »

notacoward wrote: post #83
jcranmer wrote: post #79

Earlier quoted context omitted.

No, you didn't. It's the C++ memory model, which is borrowed by C, then every compiler IR targeting something in the C/C++ space, and then every other language that decided to support language-level atomics. Your mistake is thinking solely in terms of the hardware memory model. Indeed, if you care only about x86 (and ignore the potential for compiler optimizations), most of the variety provided by the C/C++ memory mo…

So your incomplete explanations are based on a single language model instead of a single processor model? Sorry, that's a distinction without a difference. It's no excuse for misleading people who might use other languages or processors. And stop with the implied insults about my level of knowledge, when you're the one clearly fixated on only one environment. That's both rude and stupid. I've worked on many CPU archi…

> So your incomplete explanations are based on a single language model instead of a single processor model?

It's the language memory model incorporated by all major programming languages. That you are unaware of this tells me that you are a hardware engineer, not a software engineer.

> I've worked on many CPU architectures

And I've worked on computer architectures where it's not clear how to even translate "volatile" correctly because the memory system is that weird. I didn't bring that up before because I'm not interested in appeal-to-authority until people start accusing me of being an idiot who doesn't know what they talk about. I could bring up more bona fide credentials, but what's the point? You've already dismissed my expertise.

> You should at the very least qualify your statements to say that they're only true for application level programmers like yourself.

I did. Every single message, in fact:

> what most programmers would need to understand about memory ordering

> Furthermore, my focus is on a software memory model, not the hardware memory model.

> It's the C++ memory model

And actually, I would go further and suggest that kernel programmers might be better served by adopting the language memory model offered by their compiler rather than insisting on rolling their own and yelling at the compiler when they mess it up.

Re: Myths Programmers Believe about CPU Caches (2018)

#85

Post by gpderetta »

jcranmer wrote: post #80
gpderetta wrote: post #47

Earlier quoted context omitted.

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

The data-race-free theorem states that, in the absence of data races, acquire/release is indistinguishable from sequential consistency. Define data races to be UB, as C/C++ do, and you get to the state that acquire/release lets you pretend everything (except atomic operations themselves) is sequentially consistent.

My understanding is that that only applies to programs that use mutex lock/unlock operations (which do have acquire/release semantics), but not to programs that use acq/rel memory operations in general. For example: https://www.hboehm.info/c++mm/sc_proof.html which contains the the SC proof for lock operations that you mention, but also a counterexample for acq/rel atomics.

Re: Myths Programmers Believe about CPU Caches (2018)

#86

Post by notacoward »

jcranmer wrote: post #84
notacoward wrote: post #83

Earlier quoted context omitted.

So your incomplete explanations are based on a single language model instead of a single processor model? Sorry, that's a distinction without a difference. It's no excuse for misleading people who might use other languages or processors. And stop with the implied insults about my level of knowledge, when you're the one clearly fixated on only one environment. That's both rude and stupid. I've worked on many CPU archi…

> So your incomplete explanations are based on a single language model instead of a single processor model? It's the language memory model incorporated by all major programming languages. That you are unaware of this tells me that you are a hardware engineer, not a software engineer. > I've worked on many CPU architectures And I've worked on computer architectures where it's not clear how to even translate "volatile"…

> You've already dismissed my expertise.

That's pretty rich, since you were the one who jumped in to dismiss others'.

> you are a hardware engineer, not a software engineer

Incorrect. I've merely worked close to the hardware enough to understand why these things matter. Someone has to support the abstraction on which people like you depend, which requires understanding both the abstraction and the domain where it doesn't exist yet. BTW that's why kernel folks don't rely on your abstraction; that would be a circular dependency.

I suggest that this whole fracas could have been avoided if you weren't so prone to make assumptions (including that one about me), over-generalize from your own experience, and meet any disagreement with ever-increasing levels of condescension. I'm sure you're good at what you do, but try to accept that others are also good at what they do and got that way by learning about things you consider irrelevant or exotic. All I was trying to do before you decided to play "I'm smarter" was share some of that information for the next generation of system programmers.

Re: Myths Programmers Believe about CPU Caches (2018)

#87

Post by jcranmer »

notacoward wrote: post #86
jcranmer wrote: post #84

Earlier quoted context omitted.

> So your incomplete explanations are based on a single language model instead of a single processor model? It's the language memory model incorporated by all major programming languages. That you are unaware of this tells me that you are a hardware engineer, not a software engineer. > I've worked on many CPU architectures And I've worked on computer architectures where it's not clear how to even translate "volatile"…

> You've already dismissed my expertise. That's pretty rich, since you were the one who jumped in to dismiss others'. > you are a hardware engineer, not a software engineer Incorrect. I've merely worked close to the hardware enough to understand why these things matter. Someone has to support the abstraction on which people like you depend, which requires understanding both the abstraction and the domain where it doe…

> That's pretty rich, since you were the one who jumped in to dismiss others'.

Where did I do that? You were the one to accuse me of "you suppose the authors spent their time writing that for no reason?", to which I directly responded that no, I did not. My goal was to produce a smaller, more concise comment that could be reasonably offered up as something that "every programmer should know" (with particular emphasis on the word "every"), which by its very nature, ought to be incomplete.

Re: Myths Programmers Believe about CPU Caches (2018)

#88

Post by hinkley »

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…

Uh, this is not the history I recall at all.

Why is Hanz Boehm referring to memory model fixes and the JMM in the C++11 spec (Java started tackling this problem in 2004, see Goetz) if Java copied C++?

Re: Myths Programmers Believe about CPU Caches (2018)

#89

Post by layer8 »

automatic6131 wrote: post #60
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?

They are still the king of single-thread performance.

Re: Myths Programmers Believe about CPU Caches (2018)

#90

Post by jcranmer »

gpderetta wrote: post #85
jcranmer wrote: post #80

Earlier quoted context omitted.

The data-race-free theorem states that, in the absence of data races, acquire/release is indistinguishable from sequential consistency. Define data races to be UB, as C/C++ do, and you get to the state that acquire/release lets you pretend everything (except atomic operations themselves) is sequentially consistent.

My understanding is that that only applies to programs that use mutex lock/unlock operations (which do have acquire/release semantics), but not to programs that use acq/rel memory operations in general. For example: https://www.hboehm.info/c++mm/sc_proof.html which contains the the SC proof for lock operations that you mention, but also a counterexample for acq/rel atomics.

The original data-race-free models are based on acquire/release semantics that underlie the C++ memory model (https://pages.cs.wisc.edu/~markhill/papers/topds93_drf1.pdf), so the use of acquire/release atomics should provide the same guarantees as mutex lock/unlock.

However, the sequential consistency guarantee doesn't necessarily apply to atomics themselves, and I think the difference between the data-race-free-0 and data-race-free-1 models is whether not they would extend the guarantee to the release-acquire atomic operations.

Post reply on HN