4 ms·

New cache design speeds up processing time by 15%

94 points by srikar 13y ago

solarexplorer 13y ago
Link to the paper: http://people.csail.mit.edu/devadas/pubs/acc-hpca14.pdf http://people.csail.mit.edu/devadas/pubs/acc-hpca14.pdf
valarauca1 13y ago
Cache misses are a major problem many people don't think about or shy away from because you just need to assume they'll happen. Missing L1 cache costs between 10-60 cycles, your 10x that for L2. Access to the direct RAM because you also missed L3? you start dealing in 100,000+ processor cycles of hang. Glad to see were moving forward.
- solarexplorer 13y ago
  These numbers are a bit too pessimistic. But I agree that many programmers miss the importance of the memory wall.
- FooBarWidget 13y ago
  That's easy to say, but try and debug/optimize CPU caching! The available tools are extremely primitive and hard to use. It's very hard to gain visibility into what parts of your code is causing caching problems, why, and what you can do about it. Practical, comprehensive, useful literature about CPU cache optimization is also almost nonexistent. The L1 cache is so small, I don't even know how to optimize for it in general-purpose software. It's not too hard if you have very narrow use cases, e.g. if you're doing heavy matrix calculations on small localities at a time. But I'm writing an HTTP server, and a single read() into a 16 KB buffer already blows my entire L1 cache. Great, how do I optimize that?
  - Someone 13y ago
    As you say, the L1 cache is small. That means you only have to be concerned about it in small time frames (the register set is even smaller, and you don't try to keep stuff in registers across read() calls, either) That read() will block. In the typical HTTP server, that means other code will run and fill the L1 cache with its data. There's nothing you can do about it in a HTTP server. And, pedantic: thatread() should use DMA to move in the data, in which case it needn't hit the L1 cache.
  - solarexplorer 13y ago
    > a single read() into a 16 KB buffer already blows my entire L1 cache If you do I/O, memory latency is probably not your worst problem. In this case you should focus on I/O throughput, e.g. non-blocking read operations and/or multithreading. Multithreading can also help you to better utilize your memory bandwidth, but in this case it's unlikely that you are bound by memory bandwidth or latency.
  - rayiner 13y ago
    It's rarely worthwhile to try and optimize for caching if you're doing disk I/O in your critical loops anyway. To the extent you do optimize for caching, focus less on the particular size of things and more on packing data tightly and accessing it in predictable sequential patterns. This might involve, say, changing a tree structure into an array structure or changing an array of structs into a structure of arrays. Try not to jump around between data structures so the prefetchers can do their work. This means thinking about each cycle of your algorithm, and trying to reduce the number of distinct "streams" of data that need to be prefetched.
  - stephencanon 13y ago
    1. Open your favorite sampling profiler (vtune, zoom, instruments, whatever) 2. Set it up to sample every N cache misses. Good choices of N absent extra information are usually prime (why? to avoid artifacts where cache misses are divided evenly among M locations, with M|N) numbers between ~1000 and ~1000000. 3. Exercise your program under typical workload. If the resulting data is too coarse-grained, decrease N. If your program is running too slowly because of sampling overhead, increase N. 4. You now have a detailed accounting of what call stacks and instructions triggered cache misses. Starting with the worst offenders, re-arrange your algorithms to maximize the amount of data reuse. This isn't trivial, but I’d say it’s a very long way from primitive.
- AlisdairO 13y ago
  I think your figures are a bit off - iirc latency for direct access to RAM is generally in the 300 cycle range.
- rayiner 13y ago
  Memory is not 100,000+ processor cycles. Haswell is probably under 100 clocks for a main memory read that hits the TLB, and maybe two or three times that for one that misses in the TLB: http://www.cs.gmu.edu/~rcarver/cs310/CacheMemory.pdf http://www.cs.gmu.edu/~rcarver/cs310/CacheMemory.pdf.
habosa 13y ago
I just recently took an advanced computer architecture course, and I was stunned by how little I knew about how computers ~actually~ work. Most people think "memory is fast, disk is slow" but the reality is "high-level caches are fast, other caches are slow, memory is really slow, and stay the hell away from disk". You're always taught to think in terms of memory but the good news is that very intelligent cache designers have made accessing memory directly a relatively infrequent event, and that's one of the only reasons our processors get to do any work at all.
- SixSigma 13y ago
  If nanoseconds were seconds is a must read https://plus.google.com/app/basic/stream/z13uuj5a0qjhfv43r23rdrubguulz1qxw04 https://plus.google.com/app/basic/stream/z13uuj5a0qjhfv43r23... Also Grace Hopper's nanosecond illustration http://highscalability.com/blog/2012/3/1/grace-hopper-to-programmers-mind-your-nanoseconds.html http://highscalability.com/blog/2012/3/1/grace-hopper-to-pro...
- tinco 13y ago
  Ulrich Drepper wrote a terrible paper titled "What every programmer should know about memory"[1]. It covers basically everything involving memory. It's much too long and really only is relevant for programmers who want (need) to make optimal use of memory. I wouldn't recommend it, but every time someone realises how slow some memory things are compared to other memory things, I guess it's obligatory to link it. So here, don't read it ;) 1] http://www.akkadia.org/drepper/cpumemory.pdf http://www.akkadia.org/drepper/cpumemory.pdf
  - munificent 13y ago
    If you want a friendlier introduction to the topic with some basic patterns to optimize for it, I wrote a chapter in my book on game programming about caching: http://gameprogrammingpatterns.com/data-locality.html http://gameprogrammingpatterns.com/data-locality.html While the book is ostensibly about games, there's relatively little game-specific about it.
- coldtea 13y ago
AceJohnny2 13y ago
Reminds me of the hilarious column by James Mickens, "The Slow Winter", on how these kinds of improvements used to be easy: "“I wish that we could predict branches more accurately,” and you’d think, “maybe we can leverage three bits of state per branch to implement a simple saturating counter,” and you’d laugh and declare that such a stupid scheme would never work, but then you’d test it and it would be 94% accurate, and the branches would wake up the next morning and read their newspapers and the headlines would say OUR WORLD HAS BEEN SET ON FIRE." PDF: https://www.usenix.org/system/files/1309_14-17_mickens.pdf https://www.usenix.org/system/files/1309_14-17_mickens.pdf
- gumby 13y ago
  That is a profoundly awesome column. Thanks for forwarding it!
  - MetaCosm 13y ago
    Indeed, THAT is who you cover a somewhat dry topic.

94 points by srikar 13y ago

Link to the paper: http://people.csail.mit.edu/devadas/pubs/acc-hpca14.pdf http://people.csail.mit.edu/devadas/pubs/acc-hpca14.pdf

valarauca1 13y ago

Cache misses are a major problem many people don't think about or shy away from because you just need to assume they'll happen. Missing L1 cache costs between 10-60 cycles, your 10x that for L2. Access to the direct RAM because you also missed L3? you start dealing in 100,000+ processor cycles of hang. Glad to see were moving forward.

solarexplorer 13y ago
These numbers are a bit too pessimistic. But I agree that many programmers miss the importance of the memory wall.
FooBarWidget 13y ago
That's easy to say, but try and debug/optimize CPU caching! The available tools are extremely primitive and hard to use. It's very hard to gain visibility into what parts of your code is causing caching problems, why, and what you can do about it. Practical, comprehensive, useful literature about CPU cache optimization is also almost nonexistent. The L1 cache is so small, I don't even know how to optimize for it in general-purpose software. It's not too hard if you have very narrow use cases, e.g. if you're doing heavy matrix calculations on small localities at a time. But I'm writing an HTTP server, and a single read() into a 16 KB buffer already blows my entire L1 cache. Great, how do I optimize that?
- Someone 13y ago
  As you say, the L1 cache is small. That means you only have to be concerned about it in small time frames (the register set is even smaller, and you don't try to keep stuff in registers across read() calls, either) That read() will block. In the typical HTTP server, that means other code will run and fill the L1 cache with its data. There's nothing you can do about it in a HTTP server. And, pedantic: thatread() should use DMA to move in the data, in which case it needn't hit the L1 cache.
- solarexplorer 13y ago
  > a single read() into a 16 KB buffer already blows my entire L1 cache If you do I/O, memory latency is probably not your worst problem. In this case you should focus on I/O throughput, e.g. non-blocking read operations and/or multithreading. Multithreading can also help you to better utilize your memory bandwidth, but in this case it's unlikely that you are bound by memory bandwidth or latency.
- rayiner 13y ago
  It's rarely worthwhile to try and optimize for caching if you're doing disk I/O in your critical loops anyway. To the extent you do optimize for caching, focus less on the particular size of things and more on packing data tightly and accessing it in predictable sequential patterns. This might involve, say, changing a tree structure into an array structure or changing an array of structs into a structure of arrays. Try not to jump around between data structures so the prefetchers can do their work. This means thinking about each cycle of your algorithm, and trying to reduce the number of distinct "streams" of data that need to be prefetched.
- stephencanon 13y ago
  1. Open your favorite sampling profiler (vtune, zoom, instruments, whatever) 2. Set it up to sample every N cache misses. Good choices of N absent extra information are usually prime (why? to avoid artifacts where cache misses are divided evenly among M locations, with M|N) numbers between ~1000 and ~1000000. 3. Exercise your program under typical workload. If the resulting data is too coarse-grained, decrease N. If your program is running too slowly because of sampling overhead, increase N. 4. You now have a detailed accounting of what call stacks and instructions triggered cache misses. Starting with the worst offenders, re-arrange your algorithms to maximize the amount of data reuse. This isn't trivial, but I’d say it’s a very long way from primitive.
AlisdairO 13y ago
I think your figures are a bit off - iirc latency for direct access to RAM is generally in the 300 cycle range.
rayiner 13y ago
Memory is not 100,000+ processor cycles. Haswell is probably under 100 clocks for a main memory read that hits the TLB, and maybe two or three times that for one that misses in the TLB: http://www.cs.gmu.edu/~rcarver/cs310/CacheMemory.pdf http://www.cs.gmu.edu/~rcarver/cs310/CacheMemory.pdf.

habosa 13y ago

I just recently took an advanced computer architecture course, and I was stunned by how little I knew about how computers ~actually~ work. Most people think "memory is fast, disk is slow" but the reality is "high-level caches are fast, other caches are slow, memory is really slow, and stay the hell away from disk". You're always taught to think in terms of memory but the good news is that very intelligent cache designers have made accessing memory directly a relatively infrequent event, and that's one of the only reasons our processors get to do any work at all.

SixSigma 13y ago
If nanoseconds were seconds is a must read https://plus.google.com/app/basic/stream/z13uuj5a0qjhfv43r23rdrubguulz1qxw04 https://plus.google.com/app/basic/stream/z13uuj5a0qjhfv43r23... Also Grace Hopper's nanosecond illustration http://highscalability.com/blog/2012/3/1/grace-hopper-to-programmers-mind-your-nanoseconds.html http://highscalability.com/blog/2012/3/1/grace-hopper-to-pro...
tinco 13y ago
Ulrich Drepper wrote a terrible paper titled "What every programmer should know about memory"[1]. It covers basically everything involving memory. It's much too long and really only is relevant for programmers who want (need) to make optimal use of memory. I wouldn't recommend it, but every time someone realises how slow some memory things are compared to other memory things, I guess it's obligatory to link it. So here, don't read it ;) 1] http://www.akkadia.org/drepper/cpumemory.pdf http://www.akkadia.org/drepper/cpumemory.pdf
- munificent 13y ago
  If you want a friendlier introduction to the topic with some basic patterns to optimize for it, I wrote a chapter in my book on game programming about caching: http://gameprogrammingpatterns.com/data-locality.html http://gameprogrammingpatterns.com/data-locality.html While the book is ostensibly about games, there's relatively little game-specific about it.
coldtea 13y ago

AceJohnny2 13y ago

Reminds me of the hilarious column by James Mickens, "The Slow Winter", on how these kinds of improvements used to be easy: "“I wish that we could predict branches more accurately,” and you’d think, “maybe we can leverage three bits of state per branch to implement a simple saturating counter,” and you’d laugh and declare that such a stupid scheme would never work, but then you’d test it and it would be 94% accurate, and the branches would wake up the next morning and read their newspapers and the headlines would say OUR WORLD HAS BEEN SET ON FIRE." PDF: https://www.usenix.org/system/files/1309_14-17_mickens.pdf https://www.usenix.org/system/files/1309_14-17_mickens.pdf

gumby 13y ago
That is a profoundly awesome column. Thanks for forwarding it!
- MetaCosm 13y ago
  Indeed, THAT is who you cover a somewhat dry topic.