Empirical analysis for binary search not matching Theoretical Analysis

Question

I'm currently doing a test for the Binary searches average case. Simply all I do is I generate a random variable and then search for this random variable in different sized arrays using the binary search. Below is my code used:

   public static void main(String[] args) 
    {
        //This array keeps track of the times of the linear search
        long[] ArrayTimeTaken = new long[18];

        //Values of the array lengths that we test for
        int[] ArrayAssignValues = new int[18];
        ArrayAssignValues[0] = 1000000;
        ArrayAssignValues[1] = 10000000;
        ArrayAssignValues[2] = 20000000;
        ArrayAssignValues[3] = 30000000;
        ArrayAssignValues[4] = 40000000;
        ArrayAssignValues[5] = 50000000;
        ArrayAssignValues[6] = 60000000;
        ArrayAssignValues[7] = 70000000;
        ArrayAssignValues[8] = 80000000;
        ArrayAssignValues[9] = 90000000;
        ArrayAssignValues[10] = 100000000;
        ArrayAssignValues[11] = 110000000;
        ArrayAssignValues[12] = 120000000;
        ArrayAssignValues[13] = 130000000;
        ArrayAssignValues[14] = 140000000;
        ArrayAssignValues[15] = 150000000;
        ArrayAssignValues[16] = 160000000;
        ArrayAssignValues[17] = 170000000;

        //Code that runs the linear search
        for (int i = 0; i < ArrayAssignValues.length; i++) 
        {
            float[] arrayExperimentTest = new float[ ArrayAssignValues[i]];

            //We fill the array with ascending numbers 
            for (int j = 0; j < arrayExperimentTest.length; j++) 
            {
                arrayExperimentTest[j] = j;
            }

            Random Generator = new Random();
            int ValuetoSearchfor = (int) Generator.nextInt(ArrayAssignValues[i]);
            System.out.println(ValuetoSearchfor);
            ValuetoSearchfor = (int) arrayExperimentTest[ValuetoSearchfor];

            //Here we perform a the Linear Search
            ArrayTimeTaken[i] = BinarySearch(arrayExperimentTest,ValuetoSearchfor);
        }
        ChartCreate(ArrayTimeTaken);  
        System.out.println("Done");
    }

Here is my code for the binary search:

 static long BinarySearch(float[] ArraySearch,int ValueFind)
    {
        System.gc();
        long startTime = System.nanoTime();

        int low = 0;
        int high = ArraySearch.length-1;
        int mid = Math.round((low+high)/2);

        while (ArraySearch[mid] != ValueFind ) 
        {            
            if (ValueFind <ArraySearch[mid]) 
            {
                high = mid-1;
            }
            else
            {
                low = mid+1;
            }
            mid = (low+high)/2;
        }
        long TimeTaken = System.nanoTime() - startTime;
        return TimeTaken;
    }

Now the problem is that the results aren't making sense. Below is a graph:

Can some explain how the 1st array takes so much time? I've run the code a good few times and its basically the same graph created every time. Does Java some how cache results? Can anyone explain the result why the 1st binary search takes so long relativve to the others even though the array size is tiny compared to the rest?

Answer 1

It looks like you're doing these searches one after another, starting with the lowest values. If that's true, then the code will be running much slower, because the JIT compiler won't have had a chance to warm up yet. Generally, for benchmarking like this, you want to run through all relevant code to give the JIT compiler time to compile it and optimize before you do the real testing.

For more information on the JIT compiler, read this

You should also see this question to learn more about benchmarking.

Another possible cause of the slowness is that the JVM could still be in the process of starting up, and running it' own background code while you're timing it, causing slowdown.

Answer 2

Benchmarking is not done this way, you should run at least 1000 cycles as a "warmup" and only then start measuring. Benchmarking could be more complicated than it seems, it should be carefully constructed to not be affected by other programs that run in the memory at the same time etc. Here and here you can find some good tips.