Is array access always constant-time / O(1)?

Question

From Richard Bird, Pearls of Functional Algorithm Design (2010), page 6:

For a pure functional programmer, an update operation takes logarithmic time in the size of the array. To be fair, procedural programmers also appreciate that constant-time indexing and updating are only possible when the arrays are small.

Under what conditions do arrays have non-constant-time access? Is this related to CPU cache?

Answer 1

Most modern machine architectures try to offer small unit time access to memory.

They fail. Instead we see layers of caches with differing speeds.

The problem is simple: the speed of light. If you need an enormous memory [array] (in the extreme, imagine a memory the size of the Andromeda galaxy), it will take enormous space, and light cannot cross enormous space in short periods of time. Information cannot travel faster than the speed of light. You are screwed by physics from the start.

So the best you can do is build part of memory "nearby" where light takes only fractions of nanosecond to traverse (thus registers and L1 cache), and part of the memory far away (the disk drive). Other practical complications ensue, such as capacitance (think inertia) to slow down access to things further away.

Now, if you are willing to take the access time of your farthest memory element as "unit" time, yes, access to everything takes the same amount of time, e.g., O(1). In practical computing, we treat RAM memory this way most of the time, and we leave out other, slower devices to avoid screwing up our simple model.

Then you discover people that aren't satisfied with that, and voila, you have people optimizing for cache line access. So it may be O(1) in theory, and acts like O(1) for small arrays (that fit in the first level of cache), but it often is not in practice.

An extreme practical case is an array that doesn't fit in main memory; now an array access may cause paging from the disk.

Sometimes we don't care even in that case. Google is essentially a giant cache. We tend to think of Google searches as O(1).