Why is summing a sorted array faster than an unsorted one?

Question

I have an ArrayList with numbers from 10 MM to 20 MM

 List<Long> l = new ArrayList<>();
        for (long i = 10_000_000; i < 20_000_000; i++) {
            l.add(i);
        }

Why is the sum() function faster on a sorted array than on an unsorted?

public class Main {

    public static void main(String[] args) {
        List<Long> l = new ArrayList<>();
        for (long i = 10_000_000; i < 20_000_000; i++) {
            l.add(i);
        }

        System.out.println(sum(l));

        Collections.shuffle(l);
        System.out.println(sum(l));

        Collections.sort(l);
        System.out.println(sum(l));
    }

    static long sum(List<Long> l) {
        long started = System.nanoTime();
        long result = 0;
        for (long v : l) {
            result += v;
        }
        System.out.println(" duration: " + (System.nanoTime() - started) / 1_000_000 + "ms");
        return result;
    }

}

I execute the sum() function three times

• First time, on a sorted array
• Second time on unsorted
• And the third time again on sorted

On my computer, the execution time was

1. 85ms

2. 250ms

3. 97ms

Why is the sum() function faster on a sorted array than on an unsorted?

Answer 1

It's not about being sorted per-se, it's about the order in which memory is accessed.

I will briefly describe a few experiments to confirm that:

• Try using long[] instead of ArrayList<Long>. Then there are no individually allocated Long objects, just one big array that directly contains the data. That makes the memory access order of sum independent of the contents of the array. I did not perform this experiment since it would take a bit more work to write the code.

• Try initializing the list with randomly-ordered values. I tried that (I also made the list a bit shorter to save time) and got this result:

  duration: 31ms
  -6262510617230624864
  duration: 77ms
  -6262510617230624864
  duration: 160ms
  -6262510617230624864
  

  ie the fastest order is the same as the order in which the Long objects were created, independently of their values.

• Recreate the Long objects in-order after shuffling, for example:

    for (int i = 0; i < l.size(); i++)
        l.set(i, new Long(l.get(i)));
  

  That makes the sum of the shuffled list fast again (subsequently sorting the list un-orders the memory access pattern and makes sum slow again).

There is actually no guarantee that Long objects that are allocated one after the other will be allocated in the same order in memory, but that is a pretty common thing to happen, when a sufficiently large number of them is allocated and not much disturbance happens meanwhile.