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

101–110 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#101

Post by gpderetta »

Dylan16807 wrote: post #97
gpderetta wrote: post #57

Earlier quoted context omitted.

> 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 unu…

> 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. Why would you need to avoid caches or flush to memory? And invalidation and synchronization message are already part of a normal CPU's overhead, so I don't see why restricting some of them to memory barriers would increase…

How would you implement the c++11 memory model in a non-cc system exactly? Let's say you build linked list, spanning a few cachelines and then publish it by storing the address of the first node to into an atomic with release semantics. Another thread load-consumes its address and start traversing it.

On a cc system the only thing the release barrier needs to ensure is that all previous stores commit to L1 (in any order) before the final store. There is typically nothing to do on the consume side as the CPU pipeline preserves causality. Everything else is taken care by plain MESI, which will transfer exactly and on-demand those cache lines that contain the list nodes and no more.

What would the acquire/consume barriers do on a non-cc system? Consider that, generally, neither the CPU nor the compiler actually have an understanding of the list data structure itself.

Re: Myths Programmers Believe about CPU Caches (2018)

#102

Post by CyberDildonics »

jcranmer wrote: post #30
hashmash wrote: post #29

Earlier quoted context omitted.

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

Okay, it seems strange to make a sweeping generalization while assuming java had stagnated.

Re: Myths Programmers Believe about CPU Caches (2018)

#103

Post by winstonprivacy »

CyberDildonics wrote: post #92
winstonprivacy wrote: post #73

Ok, interesting and all but just tell me how I can get 1 ns cross thread access to variables in C++

Ok, that's the latency of the L1 cache and that isn't shared between threads, so you might not want to count on being able to do this.

Exactly. I was referring to that bit at the end of the article:

"In the case of Java volatiles, part of the solution is to force all reads/writes to bypass the local registers, and immediately trigger cache reads/writes instead. As soon as the data is read/written to the L1 cache, the hardware-coherency protocol takes over and provides guaranteed coherency across all global threads. Thus ensuring that if multiple threads are reading/writing to the same variable, they are all kept in sync with one another. And this is how you can achieve inter-thread coordination in as little as 1ns."

Re: Myths Programmers Believe about CPU Caches (2018)

#104

Post by CyberDildonics »

winstonprivacy wrote: post #103
CyberDildonics wrote: post #92

Earlier quoted context omitted.

Ok, that's the latency of the L1 cache and that isn't shared between threads, so you might not want to count on being able to do this.

Exactly. I was referring to that bit at the end of the article: "In the case of Java volatiles, part of the solution is to force all reads/writes to bypass the local registers, and immediately trigger cache reads/writes instead. As soon as the data is read/written to the L1 cache, the hardware-coherency protocol takes over and provides guaranteed coherency across all global threads. Thus ensuring that if multiple thr…

Ok, but why are you asking how to do it? They are saying how to do it, even though it's nonsense.

Re: Myths Programmers Believe about CPU Caches (2018)

#105

Post by Dylan16807 »

gpderetta wrote: post #101
Dylan16807 wrote: post #97

Earlier quoted context omitted.

> 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. Why would you need to avoid caches or flush to memory? And invalidation and synchronization message are already part of a normal CPU's overhead, so I don't see why restricting some of them to memory barriers would increase…

How would you implement the c++11 memory model in a non-cc system exactly? Let's say you build linked list, spanning a few cachelines and then publish it by storing the address of the first node to into an atomic with release semantics. Another thread load-consumes its address and start traversing it. On a cc system the only thing the release barrier needs to ensure is that all previous stores commit to L1 (in any or…

In that example I don't think anything really changes. With cache coherency a release barrier makes sure all previous stores are committed to L1, and by implication any old versions of the cache line have been invalidated. Without cache coherency a release barrier makes sure all previous stores are committed to L1, and explicitly says that any old versions of the cache line have been invalidated.

If you had a design a lot like MESI, you wouldn't really need release semantics, you'd just have an extra "Shared but maybe stale" state instead of just Invalid, and consume would coerce all those lines into Invalid and they'd have to be re-acquired. But re-acquiring those lines is no worse than if you had vanilla MESI. If you had an Owned state that needs to broadcast changes, you could avoid most broadcasts until seeing a release or similar barrier.

In both of these situations you'd probably make the CPU try to sync lines right away, but it could squeeze out some more performance when it's not immediately mandatory.

Re: Myths Programmers Believe about CPU Caches (2018)

#106

Post by hashmash »

gpderetta wrote: post #65
re-thc wrote: post #61

Earlier quoted context omitted.

Before Java 9 it could have been done using Unsafe. VarHandle just provides a slightly higher level construct.

Was the behavior of more relaxed operations fully formalized in the way it fits with the rest of the memory model?

Not with the Unsafe class. It was never intended to be used by anything except the built-in concurrency support classes, and it was just barely good enough. External libraries which made use of the Unsafe class did so by studying how it was used, and then assumed/concluded how it worked. Java 9 formalized everything with the VarHandle class, and it offers much more features than the Unsafe class.

Re: Myths Programmers Believe about CPU Caches (2018)

#107

Post by klabb3 »

jcranmer wrote: post #82
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…

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…

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

Very interesting. Was this overall performance? What type of workload was involved?

Yeah it seems like acq-rel is the only other one worth keeping an eye out for. When using atomics you have different logical ops with a certain happens-before relation between them anyway. Figuring out whether these ops map to acq-rel seems like a reasonable task to take on, given the total effort. The main argument against it is lack of testing infrastructure (since indeed correctness is more important). With something like Loom (the Rust project) it’s significantly easier to prevent subtle bugs. I wish it was more widely available.

Re: Myths Programmers Believe about CPU Caches (2018)

#108

Post by garfieldandthe »

Dylan16807 wrote: post #98
_a_a_a_ wrote: post #81

Earlier quoted context omitted.

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

Sometimes you have some very very high-use variables, with multiple threads each having one and writing to it often. If multiple of those variables are located on the same cache line, control of it will bounce wildly between cores and this can completely trash your performance. The fix there is absolutely trivial: add padding. Sometimes you're iterating through a huge number of objects, and only using a couple fields…

> Sometimes you have some very very high-use variables, with multiple threads each having one and writing to it often.

And how often do you actually write such code? Most people: Between rarely and never. You write single threaded code or use synchronization primitives. Sure if you are writing a library squeezing performance out of some parallel processing problem then this is relevant, but that's a niche scenario.

> The fix there is absolutely trivial: add padding.

Most common case is that this just wastes memory. Don't micro-optimizr before you know that this is actually a problem.

> Another often-trivial one is avoiding linked lists whenever feasible.

Again, not true, depending on your use case. If the operations that you commonly perform on the data structure, like inserting/deleting elements, then of course you should use a linked list or whatever container data structure your language provides. How caches play into this is at most a second order effect in the common case, unless you really want to optimize a tight loop in a performance critical application.

I've seen too many prematurely applied fancy data structures where it turned out that all this extra complexity was entirely unnecessary and just made things harder to maintain.

Re: Myths Programmers Believe about CPU Caches (2018)

#109

Post by garfieldandthe »

pajko wrote: post #48
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.

How many of your structs does your code access million times a second? For most programs, that number is firmly 0.

While you are optimizing your struct layout and decrease you app start time from 1.122765 seconds to 1.122764 seconds, I ship production code at 2x the rate because I only optimize for performance where it matters while otherwise optimizing for maintainability, testability, extensibility, dev fun and actually shipping.

Re: Myths Programmers Believe about CPU Caches (2018)

#110

Post by throwawaylinux »

Dylan16807 wrote: post #96
throwawaylinux wrote: post #67

Earlier quoted context omitted.

> 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. Not without coherency performed in software though, which is the point. > Cache coherency doesn't protect you from stale data unless you only read one memory address ever. It does. Observing updates to different locations in other tha…

> Not without coherency performed in software though, which is the point. How would you do cache coherency in software? I don't follow. > It does. Observing updates to different locations in other than sequential order does not mean the data is stale. I guess that's also colloquial language issue. The data is up to date according to the constraints of the memory model. When you read address X that refers to address Y…

> How would you do cache coherency in software? I don't follow.

Hardware caches which are not coherent require e.g., writeback and flushes to be coherent with other agents.

> When you read address X that refers to address Y, it's impossible to read Y and know it's the version that X refers to (or a more recent version). I would call that Y being "stale, as per the memory model". I'm pretty sure that's a normal use of the word "stale" in the context of memory models?

It isn't, because it's relative. "Most recent" is according to the observer, and if you couldn't previously observe something that is "newer" (within the rules of memory consistency model), then it is not stale.

> Imagine a CPU with a weak memory model, where multithreaded code without memory barriers loses the property of always seeing the same order of accesses to a specific address. That would break some things, but that code was broken anyway.

Not same order of access, same order of stores. If memory location x receives two stores, A and B, and CPU1 sees A, B and CPU2 sees B, A, now one thinks the location contains B and the other thinks it contains A. In the end, all CPUs can see different values at all memory locations. A normal barrier doesn't solve this, the stores are already done.

Post reply on HN