divergent performance between alternating conditional and random conditional

alternating vs random iteration.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * sort_strat<ul>
 *     <li>0 random numbers - slowest by a factor of 5 than strat 2 or 3</li>
 *     <li>1 random numbers sort time included - by far the slowest, even NOT counting the sort time. This one is puzzling.</li>
 *     <li>2 incrementing numbers - same as 2</li>
 *     <li>3 first even, then odd numbers - same as 1</li>
 * </ul>
 *
 * @author Jason Dunkelberger (dirkraft)
 */
public class ReallyDumbTest {
    public static void main(String[] args) throws InterruptedException {
        final int trials = 16;
        final int size = 1024 * 1024 * 4;
        final int sort_strat = 1;

        List<Integer> things = new ArrayList<Integer>(size);
        long total = 0;

        Random random = new Random(1L);
        if (sort_strat == 0) {
            for (int i = 0; i < size; i++) {
                things.add(random.nextInt());
            }
        } else if (sort_strat == 1) {
            for (int i = 0; i < size; i++) {
                things.add(random.nextInt());
            }
            long sortStart = System.currentTimeMillis();
            Collections.sort(things);
            total =+ System.currentTimeMillis() - sortStart;
            System.out.println("sort time: " + total);
        } else if (sort_strat == 2) {
            for (int i = 0; i < size; i++) {
                things.add(i);
            }
        } else {
            int boundary = size / 2;
            for (int i = 0; i < size; i++) {
                if (i < boundary) {
                    things.add(2 * i); // always even
                } else {
                    things.add(2 * i + 1); // always odd
                }
            }
        }

        trial(things); // throw away round 1

        for (int i = 0; i < trials; i++) {
            total += trial(things);
        }

        System.out.println("avg: " + total / trials);
    }

    static long trial(List<Integer> things) throws InterruptedException {
        System.out.println("Blasting off");
        Thread.sleep(250L);
        long time = System.currentTimeMillis();
        int even = 0;
        int odd = 0;
        for (Integer thing : things) {
            if (thing % 2 == 0) {
                ++even;
            } else {
                ++ odd;
            }
        }
        long finished = System.currentTimeMillis();

        long elapsed = finished - time;
        System.out.println(elapsed);
        return elapsed;
    }
}