Speed memory access by arranging data to take advantage of CPU caching

I&#x27;ve recently been using <a href="http://halide-lang.org/" rel="nofollow">http:&#x2F;&#x2F;halide-lang.org&#x2F;</a>, a language designed to separate the specification of an algorithm from the order of the computations and the layout of the data in memory. It allows you to first get an algorithm working and then quickly try a huge number of permutations of the options for data layout, parallelism, and vectorization. You can get incredible speedups vs. a naive series of C for loops.

If you are interested in seeing specific data on the effect caching has on memory bandwidth, you might want to check out this paper I wrote back in 2011[1].<p>Some of my findings:<p>- Effective bandwidth is approximately 6x greater for data that fits in L1, 4.3x greater if it fits in L2, and 2.9x greater if it fits in L3.<p>- Contention for shared L3 cache can limit the speedup you get from parallelization. For instance, running two threads for a data set that fits in L3 results in a speedup of only 1.75x, rather than 2x. Four threads on one four-core processor results in a speedup of only 2x vs the single-threaded program.<p>- It takes relatively few operations for programs to become compute-bound rather than memory bound. If 8 or more &quot;add&quot; operations were performed per data access, we found that the effects of caching disappeared almost completely, and the program&#x27;s execution was limited by processor rather than the memory bottleneck.<p>The specific magnitude of these results is machine-dependent, but I would expect the general relationships to hold for other machines with a similar cache hierarchy.<p>[1] <a href="http://www.stoneridgetechnology.com/uploads/file/ComputevsMemory.pdf" rel="nofollow">http:&#x2F;&#x2F;www.stoneridgetechnology.com&#x2F;uploads&#x2F;file&#x2F;ComputevsMe...</a>

First I heard of this sort of thing was from DICE&#x27;s presentation on &quot;Data Oriented Design&quot; <a href="http://dice.se/publications/introduction-to-data-oriented-design/" rel="nofollow">http:&#x2F;&#x2F;dice.se&#x2F;publications&#x2F;introduction-to-data-oriented-de...</a><p>I think they&#x27;d differ from the author here that this isn&#x27;t an optimization to go to when performance starts to suffer, but a design that you have to start using from the beginning, because it&#x27;s a big change to refactor everything to this style.

The best cache-aware programming lesson I ever received was in the CS61C course at Berkeley -- building a cache-blocking algorithm to run a matrix multiplication function using the cache as efficiently as possible. We unrolled loops so that the size of each iteration was exactly the size of one cache block, and saw instantly the increase in FLOpS.<p>Then we did some OpenMP parallelization. That was cool.<p>Nice post!

Martin Thompson has a blog and a series of talks on &quot;Mechanical Sympathy&quot; -- being in tune with the machine to extract performance, like a race car driver.<p>&quot;How to get 100K TPS with 1ms latency&quot;: <a href="http://www.infoq.com/presentations/LMAX" rel="nofollow">http:&#x2F;&#x2F;www.infoq.com&#x2F;presentations&#x2F;LMAX</a><p>Blog: <a href="http://mechanical-sympathy.blogspot.in" rel="nofollow">http:&#x2F;&#x2F;mechanical-sympathy.blogspot.in</a>

If you&#x27;re interested in this type of thing, I highly recommend &quot;Code Optimization: Effective Memory Usage&quot; by Kris Kaspersky:<p><a href="http://www.amazon.com/Code-Optimization-Effective-Memory-Usage/dp/1931769249/" rel="nofollow">http:&#x2F;&#x2F;www.amazon.com&#x2F;Code-Optimization-Effective-Memory-Usa...</a>

This is a very good article on the topic.<p>I hope universities start to catch up and build this, along with distributed systems computing and networking, into their core curriculum.<p>Mix multi-threaded programming with cache effects and there is a whole new world of side effects and un-expected results. There is a side-note in the article about it, but I think that deserve a whole article on it too!<p>It is interesting that this kind of plays a bit in the favor of functional languages. They are often data centric more than code centric. As in your lay out your data then pass it to your functions as opposed to thinking about the layout of the functionality as different objects that just happen to encapsulate data (so this separates and breaks down the data).

For those on GNU&#x2F;Linux who want to know about the CPU caches on their machine the &quot;lscpu&quot; gives more detailed cache info than &#x2F;proc&#x2F;cpuinfo.<p>I got curious about how lscpu was determining L1 Data and L1 Instruction caches. So I had a look at the source code of lscpu and found that it was looking in &#x2F;sys&#x2F;devices&#x2F;system&#x2F;cpu&#x2F;cpu<i>&#x2F;cache&#x2F; and &#x2F;sys&#x2F;devices&#x2F;system&#x2F;cpu&#x2F;cpu</i>&#x2F;topology&#x2F;<p>This lead me to &quot;Memory part 4: NUMA support&quot; <a href="http://lwn.net/Articles/254445/" rel="nofollow">http:&#x2F;&#x2F;lwn.net&#x2F;Articles&#x2F;254445&#x2F;</a><p>Pretty interesting stuff.

So this is all cool, and it&#x27;s incredibly nifty to have the hardware insight while writing software. But these optimizations (loop tiling, loop fusion, etc) could (and, to my knowledge, ARE) part of basic gcc and java compilers. Why are they not more commonly used? Why do we have to specifically provide a flag to say &quot;Hey btw I almost forgot, make my program 50 times faster.&quot;<p>I&#x27;m slightly in the dark as to why loop optimizations are not part of the default compile process.

Alignment is another key the author forgot to mention. Cache aligning data is seriously important, even if it means padding stuff like crazy. Caches are pretty big, but having to load two different cache lines and do some bit trickery is a real killer.<p>Also, if you really want performance, go parallel. Cilk is amazing and there are forks of both gcc and clang with cilk. Cilk is seriously awesome.

There are some interesting implications on databases in terms of column-stores vs row-stores due to CPU caching. Besides the I&#x2F;O improvements, column-stores benefit greatly from better CPU usage because the data is iterated over by type (column by column), so the same operators stay in the cache. This allows data to be pipelined in to the CPU and processed very quickly relative to traditional row-stores. It can even be efficient to operate on compressed data [1] if the relevant decoding data can be kept in the cache.<p>In case you missed it, there was a relevant article last week about how B-Trees benefit by reducing the number of cache requests.<p>[1]. <a href="http://db.lcs.mit.edu/projects/cstore/abadisigmod06.pdf" rel="nofollow">http:&#x2F;&#x2F;db.lcs.mit.edu&#x2F;projects&#x2F;cstore&#x2F;abadisigmod06.pdf</a><p>[2]. <a href="http://www.me.net.nz/blog/btrees-are-the-new-black/" rel="nofollow">http:&#x2F;&#x2F;www.me.net.nz&#x2F;blog&#x2F;btrees-are-the-new-black&#x2F;</a>

I was curious about this as I have never done any such testing, so I wrote a simple c program.<p>The object was a struct with a size of a typical game object( 100B ), then I trashed the memory by doing a lot of malloc&#x2F;free using the size of the object. The two tests were one with an array of objects( contiguous array ) and the other an array of pointers to objects which were allocated separately. Then I iterated over the object doing some very simple operation( just enough to access it, and identical for each object ) and timed this. And of course I trashed the memory some more for each time.<p>The time taken ratio is:<p>array of objects : array of pointers to objects<p>1 : 1.189<p>The second test is identical except I made some extra effort to make sure that every object in array of pointers was not adjacent to any previous one in memory:<p>array of objects : array of pointers to objects<p>1 : 2.483<p>The difference got much smaller once the operation on each object became more time consuming.

There is also the topic of Cache Oblivious data structures. Sadly, I&#x27;m still trying to figure that one out but it looks like it could help. Both with the memory and cache access time disparities and it is claimed that also with the memory to disk disparities.<p>If someone knows of an easier to digest explanation than the proof-laden academic articles I&#x27;d appreciate a pointer :-)

<a href="http://channel9.msdn.com/Events/Build/2014/2-661" rel="nofollow">http:&#x2F;&#x2F;channel9.msdn.com&#x2F;Events&#x2F;Build&#x2F;2014&#x2F;2-661</a> A talk by Herb Sutter about cache, ram prefetcher, locality&#x2F;contiguous allocation. Very simple and informative.

Author should mention growing cache size.