In this paper presented at the annual Usenix Meeting in 2006, Stephen C Johnson questions the traditional algorithms and data structures taught to computer science students, emphasizing the changing nature of machines on which these algorithms run. Using cycle counters on desktop machines, the author examines the impact of memory access patterns on performance. Surprisingly, the paper reveals that modern computer cache/memory systems reward sequential memory access, penalizing patterns with high locality of reference, particularly for large problems on 64-bit architectures. The data presented showcases the significant impact of cache design on algorithm efficiency, challenging traditional assumptions in computer science education.
http://yaccman.com/papers/a21/Alg21.html