Developing for Developers : Cache-oblivious data structures
Nowadays, typical desktop CPUs possess deep cache hierarchies – at least a sizable L1 and L2 cache – to prevent runtime from being dominated by RAM accesses. Data structures and algorithms that efficiently exploit the cache can perform dramatically more quickly than those that don\’t, and our analysis needs to take this into account.