4 ms·
The author took the time to write four long blog posts on the subject but apparently din't bother to look up cache-oblivious algorithms [1], i.e. the field that
by utopcell 3y ago
The author took the time to write four long blog posts on the subject but apparently din't bother to look up cache-oblivious algorithms [1], i.e. the field that deals with designing algorithms that work well in the presence of memory hierarchies.
[1] https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
- anonymoushn 3y agoThese seem minimally useful in the sense that once one needs to whip out the SIMD intrinsics and software prefetches one probably actually cares about the 30% or 100% speedup one can get by writing cache-aware algorithms instead.
- utopcell 3y agoThe 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.
- deleted 3y ago[deleted]
- tsimionescu 3y agoThe so called cache-oblivious algorithms are exactly designed to account for the speed difference between cache levels. The term cache-oblivious refers to the fact that these algorithms don't take into account the exact sizes of the various cache levels.