random access just means that each access has the same amount of latency. It turns out that 100 nano seconds is quite a lot of time for a CPU. The CPU has to wait roughly 60-100 cycles doing nothing on a cache miss when it has to load stuff from RAM. If you have a predictable loading pattern like array[0], array[1] then the CPU can try to prefetch array[2] and array[3] since latency is the problem not bandwidth (unless you go multicore).