4 ms·

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

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.

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.