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

111–120 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#111

Post by garfieldandthe »

josefx wrote: post #95
brabel wrote: post #71

Earlier quoted context omitted.

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…

Maybe you shouldn't be doing O(n^2) inside a request handler in the first place. This has nothing to do with caches.

And even if you do quadratic operations in your handler, how often do you write a new such handler? Most of the time you work on stuff around that, supporting infra, testing, etc. None of those needs to be cache optimized either.

Re: Myths Programmers Believe about CPU Caches (2018)

#112

Post by throwawaylinux »

Dylan16807 wrote: post #105
gpderetta wrote: post #101

Earlier quoted context omitted.

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…

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

That is not what a release barrier does.

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

That is not a "normal barrier" though, writeback and invalidate operations are software coherency.

> If you had a design a lot like MESI, you wouldn't really need release semantics,

This is not the case. Release barrier can be required even if your cache coherency operations completed in FIFO order, because reordering could be done before cache coherency.

Re: Myths Programmers Believe about CPU Caches (2018)

#113

Post by Dylan16807 »

garfieldandthe wrote: post #108
Dylan16807 wrote: post #98

Earlier quoted context omitted.

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

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

You don't have many variables that fit the description I gave. You're already doing profiling if you can pick them out, and preemptively spacing them would barely take any memory, and it's the kind of problem that's hard to thoroughly test unless you have a 64 core machine sitting around.

> If the operations that you commonly perform on the data structure, like inserting/deleting elements, then of course you should use a linked list

For situations where linked list and array are both usable, then even if you very commonly insert and delete you're usually better off with a data structure that's built on top of fixed-size arrays. Iterating an array is so fast that it makes up for the cost of shifting around a surprisingly large number of elements.

> or whatever container data structure your language provides.

But which one? Languages tend to have a lot.

And the ones that give you a one-size-fits-all data structure usually don't have a built-in linked list anyway.

And I'm not suggesting anything notably fancy.

Re: Myths Programmers Believe about CPU Caches (2018)

#114

Post by flohofwoe »

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

I haven't seen such dramatic speedups in my own code for quite a while since I don't tend to start with a worst case version.

With some googling it's easy to find cases like this where switching from a traditional OOP approach of "unique objects in random heap locations" to a DOD approach gains a 173x speedup overall (it's not just the tight memory layout of course, but also all the code simplifications this enables, like tighter loops and then easier integration of multithreading):

https://medium.com/@jasonbooth_86226/intro-to-jobs-burst-dod...

Basically, search for DOD (Data Oriented Design), ECS (Entity Component System), SoA (Structure of Arrays) for similar optimization stories.

Re: Myths Programmers Believe about CPU Caches (2018)

#115

Post by josefx »

garfieldandthe wrote: post #111
josefx wrote: post #95

Earlier quoted context omitted.

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

Maybe you shouldn't be doing O(n^2) inside a request handler in the first place. This has nothing to do with caches. And even if you do quadratic operations in your handler, how often do you write a new such handler? Most of the time you work on stuff around that, supporting infra, testing, etc. None of those needs to be cache optimized either.

> Maybe you shouldn't be doing O(n^2)

It was mostly meant as a example of millions of operations even at a small scale. Sadly I have seen way too much accidental O(n^3) code and not all of it could be "fixed" trivially.

> This has nothing to do with caches.

Would you rather handle 1000 request per second or 1? Caching has the potential to make an already bad situation so much worse.

> how often do you write a new such handler?

You only need to write one to DoS your server.

Re: Myths Programmers Believe about CPU Caches (2018)

#116

Post by Dylan16807 »

throwawaylinux wrote: post #112
Dylan16807 wrote: post #105

Earlier quoted context omitted.

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…

> 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. That is not what a release barrier does. > 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 lin…

>That is not what a release barrier does.

> That is not a "normal barrier" though, writeback and invalidate operations are software coherency.

I think I was unclear when I said "the cache line". I meant the one containing a releasing store.

Let me try wording it a different way. A store_release requires all previous writes to be ordered before it. This obviously includes other memory addresses, but its own memory address isn't an exception. So even without cache consistency as a general rule, the nature of a release gives you all the ordering you need in this situation.

I'm sorry for mentioning the word "invalidate", because that's the implementation and not the semantics.

> This is not the case. Release barrier can be required even if your cache coherency operations completed in FIFO order, because reordering could be done before cache coherency.

So I meant acquire but I think there's also a clear solution based on exactly what I said.

The lines that could possibly be affected by the FIFO are all in the "Shared but maybe stale" state. Consume turns those into Invalid. So any read that's from after the Consume, reordered before it, should see those lines as Invalid.

Re: Myths Programmers Believe about CPU Caches (2018)

#117

Post by Dylan16807 »

throwawaylinux wrote: post #110
Dylan16807 wrote: post #96

Earlier quoted context omitted.

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

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

Why is most recent according to the observer, and not the core(s) that actually did the writes?

The value in Y caused the value in X. Surely that's worth something in terms of ordering?

Re: Myths Programmers Believe about CPU Caches (2018)

#118

Post by throwawaylinux »

Dylan16807 wrote: post #116
throwawaylinux wrote: post #112

Earlier quoted context omitted.

> 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. That is not what a release barrier does. > 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 lin…

>That is not what a release barrier does. > That is not a "normal barrier" though, writeback and invalidate operations are software coherency. I think I was unclear when I said "the cache line". I meant the one containing a releasing store. Let me try wording it a different way. A store_release requires all previous writes to be ordered before it. This obviously includes other memory addresses, but its own memory add…

> I think I was unclear when I said "the cache line". I meant the one containing a releasing store.

Not sure what you mean by that.

> Let me try wording it a different way. A store_release requires all previous writes to be ordered before it. This obviously includes other memory addresses, but its own memory address isn't an exception. So even without cache consistency as a general rule, the nature of a release gives you all the ordering you need in this situation.

We're talking about cache coherency, not memory consistency. Coherency is not about ordering, it's about ensuring agents don't see stale data.

> So I meant acquire but I think there's also a clear solution based on exactly what I said.

The same goes for acquire though.

> The lines that could possibly be affected by the FIFO are all in the "Shared but maybe stale" state. Consume turns those into Invalid. So any read that's from after the Consume, reordered before it, should see those lines as Invalid.

Implementation of CPU memory pipelines and cache coherency aren't really something you can just get a bit of a feel for and then handwave about.

Re: Myths Programmers Believe about CPU Caches (2018)

#119

Post by gpderetta »

hashmash wrote: post #106
gpderetta wrote: post #65

Earlier quoted context omitted.

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.

Thanks for the clarification. Java was obviously a trailblazer on formally introducing advanced memory models on practical languages, but it did take a few tries to get it correct.

Re: Myths Programmers Believe about CPU Caches (2018)

#120

Post by garfieldandthe »

josefx wrote: post #115
garfieldandthe wrote: post #111

Earlier quoted context omitted.

Maybe you shouldn't be doing O(n^2) inside a request handler in the first place. This has nothing to do with caches. And even if you do quadratic operations in your handler, how often do you write a new such handler? Most of the time you work on stuff around that, supporting infra, testing, etc. None of those needs to be cache optimized either.

> Maybe you shouldn't be doing O(n^2) It was mostly meant as a example of millions of operations even at a small scale. Sadly I have seen way too much accidental O(n^3) code and not all of it could be "fixed" trivially. > This has nothing to do with caches. Would you rather handle 1000 request per second or 1? Caching has the potential to make an already bad situation so much worse. > how often do you write a new suc…

> Would you rather handle 1000 request per second or 1?

Would you rather like to approach this problem by optimizing memory layout which, let's be honest, tends to give you more in the region of 1-10% improvements rather than 10-100x, or would you rather like to try to go from O(n^3) to O(n^2) or O(n log n) or similar?

The real meat is in the complexity class. Cache effects are where you go when there is nothing else to optimize and it actually matters. Preemptively making all your data structures 2-3 as big because of not-actually-necessary padding does not sound right to me, but YMMV.

Post reply on HN