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

91–100 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#91

Post by jcranmer »

hinkley wrote: post #88
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…

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++?

C++ extended the Java memory model to include atomics, and everyone else copied the C++ atomics memory model.

Basically, it goes:

* Original data-race-free model (early 90s)

* Java 5 memory model (~2004-5) [first incorporated into the programming language, as I'm aware]

* C++0x memory model (finalized 2007-2008, IIRC) [added atomics]

* Compilers build their internal intrinsics on top of C++0x, sans consume

* Everyone else adopts either the C++ memory model as is, or without consume

(Sibling comment notes that Java 9 backports the atomics from C++).

Re: Myths Programmers Believe about CPU Caches (2018)

#92

Post by CyberDildonics »

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.

Re: Myths Programmers Believe about CPU Caches (2018)

#93

Post by gpderetta »

jcranmer wrote: post #90
gpderetta wrote: post #85

Earlier quoted context omitted.

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…

To clarify, you are saying that there is a model that guarantees DRF-SC even if the atomic operations are not themselves SC? Aside from the fact that I'm not sure such guarantee would be useful or even meaningful, I think you can extend Bohem counterexample to add non-atomic cells (and conditional reads) and show SC violations.

My understanding of the C++ memory model since the early standardization discussions was that DRF-SC is only generally guaranteed[1] if the acquire/release operations themselves were SC and can't be easily recovered otherwise.

I.e.: full SC requires all operations to be SC, DRF-SC requires, in addition of no data races, only the synchronization edges to be SC.

I suspect that's what the drf-1 model in the paper you have linked specifies. But it will take me a bit to digest it and I'll readily admit that I might be wrong (thanks for the paper BTW).

[1] so aside the lock/unlock special case.

Re: Myths Programmers Believe about CPU Caches (2018)

#94

Post by jcranmer »

gpderetta wrote: post #93
jcranmer wrote: post #90

Earlier quoted context omitted.

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…

To clarify, you are saying that there is a model that guarantees DRF-SC even if the atomic operations are not themselves SC? Aside from the fact that I'm not sure such guarantee would be useful or even meaningful, I think you can extend Bohem counterexample to add non-atomic cells (and conditional reads) and show SC violations. My understanding of the C++ memory model since the early standardization discussions was t…

This is at the penumbra of my knowledge of memory ordering, so it's entirely possible that I'm completely incorrect here, especially because confirming correctness requires spending a lot of time making sure that the various papers are all using the same definitions for the various words.

Re: Myths Programmers Believe about CPU Caches (2018)

#95

Post by josefx »

brabel wrote: post #71
pajko wrote: post #48

Earlier quoted context omitted.

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.

If I do it wrong, are we talking about my application (say, some web app) becoming noticeably slower? Or we would need to be running several million operations per second before anything a user could notice the difference? I suspect only very high end games, image processing apps and that kind of thing would ever need to care about the order of fields in a struct... perhaps the author of my web server as well, but ev…

> are we talking about my application (say, some web app) becoming noticeably slower? Or we would need to be running several million operations per second before anything a user could notice the difference?

If you have an algorithm with quadratic or higher complexity somewhere you will be in the millions even if you only have a few thousand entries to deal with. Now the worst case cache miss (down to ram) is modeled as roughly 1000 cycles. Put that right in the middle of that O(n^2) algorithm and your web app will be able to handle 1 request per second on a good day.

Note: that calculation is extremely simplified

Re: Myths Programmers Believe about CPU Caches (2018)

#96

Post by Dylan16807 »

throwawaylinux wrote: post #67
Dylan16807 wrote: post #53

Earlier quoted context omitted.

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

> 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, 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?

> What property of cache coherency could you lose and still have it working?

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.

Normal memory barrier semantics could force certain accesses to be viewed in the same order, including important accesses that would normally be enforced by cache coherency. You don't need it to be enforced twice. The code will run fine.

Re: Myths Programmers Believe about CPU Caches (2018)

#97

Post by Dylan16807 »

gpderetta wrote: post #57
Dylan16807 wrote: post #53

Earlier quoted context omitted.

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

In other words, assume you still have a cache coherency protocol, but you're lazy about certain states in the absence of memory barriers, so the default behavior is not always coherent.

Re: Myths Programmers Believe about CPU Caches (2018)

#98

Post by Dylan16807 »

_a_a_a_ wrote: post #81
flohofwoe wrote: post #52

Earlier quoted context omitted.

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.

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 out of each object. If you rearrange the data so each field is stored in a different arena, you can cut the number of memory accesses by a huge amount, and let prefetching work a lot better. That's usually not as trivial but it's simple work.

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

Re: Myths Programmers Believe about CPU Caches (2018)

#99

Post by rsaxvc »

_a_a_a_ wrote: post #81
flohofwoe wrote: post #52

Earlier quoted context omitted.

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.

Ages ago had a mathematician shard image processing across cores.

Started with a pair of loops for each image, foreach col, foreach row.

Problem: C++ 2d arrays are row-col not col-row.

Halfway through multi-threaded performance was much worse than single threaded.

Eventually we switched to row-col processing, single-threaded was fast enough, back to two loops per image.

Re: Myths Programmers Believe about CPU Caches (2018)

#100

Post by _a_a_a_ »

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…

Avoid cache line ping-pong, don't waste cache, and make accesses as spatially predictable as possible. Okay, I can see where you're coming from, thanks.
Post reply on HN