Eric Dramstad and I have been working on a new canvas-based tool. This time, it’s a cache visualizer.
On the left is the sequence of memory touches; black pixels are touched first, and white pixels are touched last. The left side shows that each row of the upper triangle is accessed in tandem with the corresponding column of the lower triangle. On the right are the cache hits and misses. The upper triangle has a cache-friendly sequential access pattern, while the lower triangle has a cache-unfriendly strided access pattern. 56% of the memory accesses result in a cache miss.
The left side shows the divide-and-conquer approach. Small blocks are transposed rather than whole rows and columns, which helps with cache locality, as reflected on the right. In this instance, only 28% of the memory touches were cache misses, a significant improvement over the naive algorithm.
There are several improvements I’d eventually like to make. One major shortcoming is that the cache model is only approximately like the cache system found in your average x86 chip. We currently only model a single-level fully-associative cache. We should eventually refine that model to a two-level set-associative cache, of configurable level sizes. I’d also like to show the cache effects of various sorting algorithms, like one-pivot quicksort versus insertion sort versus two-pivot quicksort.
The source code for canvas-cacheviz is hosted on GitHub. So far my experience with git has been negative in comparison to Mercurial. Git may be more powerful, but it has been all too easy to do strange and unwanted things with the repository DAG. And even simple questions like “what’s the equivalent of svn revert?” were difficult to answer using the tool’s help listing.