The opportunity from designing cache-aware algorithms is much larger than a 2X speedup. As a rule of thumb, main memory : L1 access times are ~ 100 : 1. The ca

The opportunity from designing cache-aware algorithms is much larger than a 2X speedup. As a rule of thumb, main memory : L1 access times are ~ 100 : 1. The canonical example of a cache-aware algorithm is scanning a 2D array as it is laid out on RAM vs in cache-hostile strides. The perf diff varies per architecture, but on my Broadwell server, the former is ~6.7X faster than the latter for a 10000 x 10000 int array. Of course there is a large perf opportunity in vectorizing code, but that was not in scope for this blog post.