The Myth of RAM
Emil Ernerfeldt (via Russ Bishop, Hacker News, Reddit):
This article is the first of four in a series, in which I argue that thinking of a memory access as O(1) is generally a bad idea, and we should instead think of them as taking O(√N) time. In part one I lay out a hand-wavy argument based on a benchmark. In part II I build up a mathematical argument based in theoretical physics, and in part III I investigate some implications. Part IV is a FAQ in which I answers some common questions and misunderstandings.
I think he’s misusing O-notation by not focusing on the asymptotic behavior. However, the general point that memory access times are nonuniform and layers of cache matter is sound.
See also: Erik Demaine’s Memory Hierarchy lectures.
Update (2016-08-31): See also: CacheFun (via McCloud).
Related:
"What every programmer should know about memory, Part 1"
https://lwn.net/Articles/250967/
Parts 1, 2, and 3 go in most exhaustive detail about memory, caching, and how to program to take advantage of it.