How much slower is random access, really?

Summary

You may know that, because your computer has different caches (L1, L2, L3...), and memory operations operate on cache lines of about 64 bytes each, you should write programs that exhibit locality to get maximum performance. L1 L1 L1 L1 L1 L1 L2 L2 L2 L2 L2 L2 L3 RAM (Disk not shown, of course.) But how well do you understand this idea? For instance, let's say you have an array of floating-point numbers, and an array of all the indices of the first array. You have a program that adds up the numbers from the first array in the order given by the second array. So, for this example, we'd add ε + α + δ + ζ + β + γ in that order: Let's just consider the two cases where the indices are in first-to-last order or in random order. Before I wrote this post, I couldn't answer any of the following questions: How big of an array do you need before you see a difference in performance between the two orderings? How much time does the first-to-last ordering take per element, on average? How much slower is random order than first-to-last order for arrays that fit in RAM? How much slower is random order than first-to-last order for arrays that don't fit in RAM? To construct these shuffled index arrays for the random ordering, is standard Fisher-Yates sufficient? How much slower is first-to-last order for arrays that don't fit in RAM, when using memory-mapped files? Are memory-mapped files as fast as you can get? If you already know the answers to all these questions, sweet! Otherwise, make your guesses and check them when you reach the bottom of this post :) Setup All the code to reproduce the measurements in this blog post can be found in a supplementary GitHub repository. Because the indices are just stored in an array, they should use the exact same machine code for both first-to-last order and random order, we've chosen the precisions for our floating-point and integer data types. That means the performance should be entirely determined by dynamic behavior in the CPU based on the ...