New cache design speeds up processing time by 15% | Hacker News Reader

New cache design speeds up processing time by 15%

arstechnica.com

94 pointssrikar18 comments

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

That is a profoundly awesome column. Thanks for forwarding it!

Indeed, THAT is who you cover a somewhat dry topic.

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.

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

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

While the book is ostensibly about games, there's relatively little game-specific about it.

If nanoseconds were seconds is a must read https://plus.google.com/app/basic/stream/z13uuj5a0qjhfv43r23...

Also Grace Hopper's nanosecond illustration http://highscalability.com/blog/2012/3/1/grace-hopper-to-pro...

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

Which is also far from the truth, which is any part of this pipeline can be fast or slow, depending on what you're using it for.

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

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.

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?

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.

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.

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.

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

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.

I think your figures are a bit off - iirc latency for direct access to RAM is generally in the 300 cycle range.

These numbers are a bit too pessimistic. But I agree that many programmers miss the importance of the memory wall.

Reply on news.ycombinator.com