Wednesday, August 31, 2016

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).

1 Comment RSS · Twitter

"What every programmer should know about memory, Part 1"

Parts 1, 2, and 3 go in most exhaustive detail about memory, caching, and how to program to take advantage of it.

Leave a Comment