CODEWITHSUNDEEP
javasortingoptimization
ithenoob
ithenoob

Reputation: 326

Why sorting a randomly populated array gets progressively faster

For a programming exercise, we were told to implement insertion, selection, and bubble sorts (in java). I wanted to test how fast the sorts executed, so I wrote a loop to randomly populate and sort an array 10 times. The first two sorts take about twice as long as the last 8 iterations.. why?

Here I have put relevant portions of code

// class fields
public static final int POPULATE_MAX = 1000000000;
public static final int POPULATE_MIN = -1000000000;

public static void populateRandom(int[] toPopulate)
{
    // populate array with random integers within bounds set by class fields
    for (int i = 0; i < toPopulate.length; i++)
    {
        toPopulate[i] = (int)(Math.random() * (POPULATE_MAX - POPULATE_MIN))
            + POPULATE_MIN;
    }
} // end of method populateRandom(int[] toPopulate)

public static void insertionSort(int[] toSort) throws IllegalArgumentException
{
    if (toSort == null)
    {
        throw new IllegalArgumentException();
    }
    if (toSort.length <= 1) return;

    int temp;

    // Index i points to the next unsorted element; assigned to temp
    for (int i = 1; i < toSort.length; i++)
    {
        temp = toSort[i];

        // This loop searches through the sorted portion of the array and
        // determines where to put the aforementioned unsorted element
        for (int j = i - 1; j >= 0; j--)
        {
            if (temp < toSort[j])
            {
                toSort[j + 1] = toSort[j];
                if(j == 0)
                    toSort[j] = temp;
            }
            else
            {
                toSort[j + 1] = temp;
                break;
            } // end of if (temp < toSort[j])
        } // end of for (int j = i - 1; j >= 0; j--)
    } // end of for (int i = 1; i < toSort.length; i++)
} // end of method insertionSort(int[] toSort) throws IllegalArgumentException

public static void main(String[] args)
{
    long time;
    for (int testRun = 0; testRun < 10; testRun++)
    {
        int[] array = new int[100000];
        System.out.print(testRun + "...");
        populateRandom(array);
        time = System.currentTimeMillis();
        insertionSort(array);
        time = System.currentTimeMillis() - time;
        for (int i = 0; i < array.length - 1; i++)
        {
            if (array[i] > array[i+1]) System.out.println(i + ". Bad");
        }
        System.out.println(time + " Done");
    }
    System.out.println("ABS Done");
}

I am guessing that it has to do with branch prediction, but I am not sure as to why subsequent sorts are very noticeably faster.

Upvotes: 2

Views: 112

Answers (1)

Alex D
Alex D

Reputation: 30455

Likely your JVM is running in interpreted mode for the first couple iterations, then it notices that you are running the same method repeatedly and compiles it to native code. If you call the same method an even greater number of times, it may even cause further optimizations to "kick in".

Because the JVM works this way, you should always warm your JVM up before taking performance measurements. Basically, run the code you want to benchmark in a loop a bunch of times, then do the measurements. (Note: this should happen within the space of a single JVM process run -- if the JVM exits and starts up again, you're back to square one.)

Upvotes: 4

Related Questions