4 ms·

Memory Access Patterns Are Important (2012)

97 points by wanderer42 10y ago

joshbaptiste 10y ago
Martin's videos on lock-free algorithms are very informative and gives great insight on how to push the JVM to the extreme. http://www.infoq.com/author/Martin-Thompson#Presentations http://www.infoq.com/author/Martin-Thompson#Presentations
malingo 10y ago
This kind of article stands in interesting contrast to the recent post on "non-programmers' solutions to programming problems." On that post, jbclements commented [0] that we are reaching / have reached a point where "the conversation shifts from 'how can I meet the machine's needs?' to 'how can the machine meet my (programming) needs?'" The idea of "the machine meeting my programming needs" still requires a programming platform that has been designed with a great deal of mechanical sympathy. [0] https://news.ycombinator.com/item?id=11509543 https://news.ycombinator.com/item?id=11509543
chris_va 10y ago
One critical thing I wish I could go back and remind my younger self: The cache is shared across processes. The net result is that cache latency/hit rate is highly dependent on what else is using the machine. CPU bound tasks (like, say search engine backends) tend to leave extra storage space (say for things like image serving). Streaming images out of a machine can completely thrash the cache without using many cores. When your net latency is based on the slowest percentile to come back, one badly co-scheduled process can ruin your entire cluster capacity.
- corysama 10y ago
  This comes up within a single process as well. Algo A might be faster than Algo B. But, if it gets that speed by completely filling your L3 cache with short-term data, it might make your process slower as a whole.
- packetslave 10y ago
  Intel finally added cache partitioning in Broadwell, which lets you restrict parts of the cache to certain cores. Combining that with pinning tasks to cores can help with cache thrashing.
  - bogomipz 10y ago
    Is that enabled by default? Turned on in the BIOS or early boot?
- bogomipz 10y ago
  Can you explain what you mean by "tend to leave extra space". Do you mean they don't use all available cache lines in L1? Instruction cache, data cache?
drudru11 10y ago
In the old days, mechanical sympathy was called RTFM
- oldmanjay 10y ago
  There are a lot more manuals these days, and they are way longer. Also it turns out that a lot of code from those old days was crap, so maybe RTFM was inadequate.
  - hinkley 10y ago
    Most of those manuals were shitty to begin with. You end up having to read the entire thing to properly understand a part of the functionality that got its own chapter. And don't get me started on the toy examples. The happy path is the least useful example you can use. I would stumble on that by myself.
    - drudru11 10y ago
      Seriously, I should have been more specific. If you take a comp. arch. class, then you get the generalization. After that, you can just read the relevant part of a manual.
  - drudru11 10y ago
    Your right, maybe we should read 1000 blog posts instead :-b Seriously, I should have been more specific. If you take a comp. arch. class, then you get the generalization. After that, you can just read the relevant part of a manual. Not all code written in the past ignored the hierarchy. The linux kernel itself had many tunings for this.
- newobj 10y ago
  RTFM for which flavor of machine? Mostly works when you control your own bare metal server, other scenarios, not so much.
  - drudru11 10y ago
nulltype 10y ago
If main memory is so slow, would it be better to treat cache as memory and handle it directly in code rather than try to trick it into doing what we want?
- chris_va 10y ago
  __builtin_prefetch sort of works in x86, but you'll probably end up doing more harm than good when second guessing the automated cache.
  - nulltype 10y ago
    Right, I'd like to avoid that complexity entirely, just get direct access to things rather than hinting what I want.
- newobj 10y ago
  The cache is a shared resource, so I'm not sure how you would propose to "handle it directly", other than literally having a MMU/virtual memory layer on top of it, and try to provide some guarantees about coherence. But given how small it is, without allowing for hard pins, I suspect that the entire cache would be thrashed pretty badly across processes and it will just degrade back to what happens today; it's useful/coherent for short/co-located bursts and not much else.
  - nulltype 10y ago
    Well imagine I could address memory on the CPU die like a register but say 1MB of memory, located right next to the normal place you put a cache. It does not have to be coherent I think. Process thrashing sounds like an issue though. I imagine if the address space is across all CPU cores then the software can pin to a core so that the access is local. Remote access to another CPU will be slow, but I'm not sure how great it is with caches anyway.
- corysama 10y ago
  https://en.wikipedia.org/wiki/Scratchpad_memory https://en.wikipedia.org/wiki/Scratchpad_memory On the original PlayStation, the scratchpad was a PITA. You had to weigh the speedup against the cost of manually copying in and out the the pad. A modern implementation would copy via DMA like the PS3's Cell processors. Still a PITA, but at least the payoff for the effort can be quite good.
alexhutcheson 10y ago
I did a similar project a couple years ago to benchmark the effects of different memory access patterns. The whitepaper [0] includes some graphs for how performance changes as you add more threads on different cores. [0] http://stoneridgetechnology.com/wp-content/uploads/2014/12/ComputevsMemory.pdf http://stoneridgetechnology.com/wp-content/uploads/2014/12/C...
amelius 10y ago
See also Ulrich Drepper's "What every programmer should know about memory" [1], mentioned in one of the comments. [1] https://people.freebsd.org/~lstewart/articles/cpumemory.pdf https://people.freebsd.org/~lstewart/articles/cpumemory.pdf

97 points by wanderer42 10y ago

Martin's videos on lock-free algorithms are very informative and gives great insight on how to push the JVM to the extreme. http://www.infoq.com/author/Martin-Thompson#Presentations http://www.infoq.com/author/Martin-Thompson#Presentations

malingo 10y ago

This kind of article stands in interesting contrast to the recent post on "non-programmers' solutions to programming problems." On that post, jbclements commented [0] that we are reaching / have reached a point where "the conversation shifts from 'how can I meet the machine's needs?' to 'how can the machine meet my (programming) needs?'" The idea of "the machine meeting my programming needs" still requires a programming platform that has been designed with a great deal of mechanical sympathy. [0] https://news.ycombinator.com/item?id=11509543 https://news.ycombinator.com/item?id=11509543

chris_va 10y ago

One critical thing I wish I could go back and remind my younger self: The cache is shared across processes. The net result is that cache latency/hit rate is highly dependent on what else is using the machine. CPU bound tasks (like, say search engine backends) tend to leave extra storage space (say for things like image serving). Streaming images out of a machine can completely thrash the cache without using many cores. When your net latency is based on the slowest percentile to come back, one badly co-scheduled process can ruin your entire cluster capacity.

corysama 10y ago
This comes up within a single process as well. Algo A might be faster than Algo B. But, if it gets that speed by completely filling your L3 cache with short-term data, it might make your process slower as a whole.
packetslave 10y ago
Intel finally added cache partitioning in Broadwell, which lets you restrict parts of the cache to certain cores. Combining that with pinning tasks to cores can help with cache thrashing.
- bogomipz 10y ago
  Is that enabled by default? Turned on in the BIOS or early boot?
bogomipz 10y ago
Can you explain what you mean by "tend to leave extra space". Do you mean they don't use all available cache lines in L1? Instruction cache, data cache?

drudru11 10y ago

In the old days, mechanical sympathy was called RTFM

oldmanjay 10y ago
There are a lot more manuals these days, and they are way longer. Also it turns out that a lot of code from those old days was crap, so maybe RTFM was inadequate.
- hinkley 10y ago
  Most of those manuals were shitty to begin with. You end up having to read the entire thing to properly understand a part of the functionality that got its own chapter. And don't get me started on the toy examples. The happy path is the least useful example you can use. I would stumble on that by myself.
  - drudru11 10y ago
    Seriously, I should have been more specific. If you take a comp. arch. class, then you get the generalization. After that, you can just read the relevant part of a manual.
- drudru11 10y ago
  Your right, maybe we should read 1000 blog posts instead :-b Seriously, I should have been more specific. If you take a comp. arch. class, then you get the generalization. After that, you can just read the relevant part of a manual. Not all code written in the past ignored the hierarchy. The linux kernel itself had many tunings for this.
newobj 10y ago
RTFM for which flavor of machine? Mostly works when you control your own bare metal server, other scenarios, not so much.
- drudru11 10y ago

nulltype 10y ago

If main memory is so slow, would it be better to treat cache as memory and handle it directly in code rather than try to trick it into doing what we want?

chris_va 10y ago
__builtin_prefetch sort of works in x86, but you'll probably end up doing more harm than good when second guessing the automated cache.
- nulltype 10y ago
  Right, I'd like to avoid that complexity entirely, just get direct access to things rather than hinting what I want.
newobj 10y ago
The cache is a shared resource, so I'm not sure how you would propose to "handle it directly", other than literally having a MMU/virtual memory layer on top of it, and try to provide some guarantees about coherence. But given how small it is, without allowing for hard pins, I suspect that the entire cache would be thrashed pretty badly across processes and it will just degrade back to what happens today; it's useful/coherent for short/co-located bursts and not much else.
- nulltype 10y ago
  Well imagine I could address memory on the CPU die like a register but say 1MB of memory, located right next to the normal place you put a cache. It does not have to be coherent I think. Process thrashing sounds like an issue though. I imagine if the address space is across all CPU cores then the software can pin to a core so that the access is local. Remote access to another CPU will be slow, but I'm not sure how great it is with caches anyway.
corysama 10y ago
https://en.wikipedia.org/wiki/Scratchpad_memory https://en.wikipedia.org/wiki/Scratchpad_memory On the original PlayStation, the scratchpad was a PITA. You had to weigh the speedup against the cost of manually copying in and out the the pad. A modern implementation would copy via DMA like the PS3's Cell processors. Still a PITA, but at least the payoff for the effort can be quite good.

alexhutcheson 10y ago

I did a similar project a couple years ago to benchmark the effects of different memory access patterns. The whitepaper [0] includes some graphs for how performance changes as you add more threads on different cores. [0] http://stoneridgetechnology.com/wp-content/uploads/2014/12/ComputevsMemory.pdf http://stoneridgetechnology.com/wp-content/uploads/2014/12/C...

amelius 10y ago

See also Ulrich Drepper's "What every programmer should know about memory" [1], mentioned in one of the comments. [1] https://people.freebsd.org/~lstewart/articles/cpumemory.pdf https://people.freebsd.org/~lstewart/articles/cpumemory.pdf