Binary search slow on smaller arrays

Question

I wrote a program that tests speeds of linear and binary search and have found that at the beginning when the sorted array is the size of 1000 binary search uses a lot more time than later on when array size increases. Is there an explanation of why that is the case.

The program checks the algorithm 1000 times and calculates the average time it took to find the desired item for each array the size of n that contains elements from 1 to n.

import java.util.*;

public class Test {
public static void main(String[] args) {
    System.out.println("   n     |    linear    |   binary    |\n---------+--------------+---------------");

    for (int i = 1000; i <= 100000; i += 1000) {
        System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
    }
}

static int[] generateTable(int n) {
    int[] a = new int[n];
    int ind = 0;

    for (int i = 1; i <= n; i++) {
        a[ind++] = i;
    }

    return a;
}

static int findLinear(int[] a, int n) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == n) return i;
    }
    return -1;
}

static int findBinary(int[] a, int l, int r, int n) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (n < a[mid]) {
        findBinary(a, l, mid - 1, n);
    }
    else if (n > a[mid]) {
        findBinary(a, mid + 1, r, n);
    }
    return mid;
}

static long timeLinear(int n) {
    Random rn = new Random();
    int[] arr = generateTable(n);

    long start = System.nanoTime();

    for (int i = 0; i < 1000; i++) {
        findLinear(arr, rn.nextInt(n) + 1);
    }

    long stop = System.nanoTime() - start;
    return stop / 1000;
}

static long timeBinary(int n) {
    Random rn = new Random();
    int[] arr = generateTable(n);

    long start = System.nanoTime();

    for (int i = 0; i < 1000; i++) {
        findBinary(arr, 0, arr.length - 1, rn.nextInt(n) + 1);
    }

    long stop = System.nanoTime() - start;
    return stop / 1000;
}

}

Output:

   n     |    linear    |   binary     |
---------+--------------+---------------
     1000|          5736|          1518|
     2000|           787|          2012|
     3000|          1313|           626|
     4000|          1230|           711|
     5000|          1281|           723|
     6000|          1888|           463|
     7000|          1846|           213|
     8000|          1089|           187|
     9000|          1213|           188|
    10000|          1583|           216|
    11000|          1607|           302|
    12000|          3294|           311|
    13000|          3656|           274|
    14000|          3497|           274|
    15000|          2315|           141|
    16000|          1945|           135|
    17000|          2223|           154|
    18000|          2964|           136|
    19000|          2464|           138|
    20000|          2472|           138|
    21000|          2829|           140|
    22000|          3209|           157|
    23000|          2901|           141|
    24000|          3095|           140|
    25000|          3157|           142|
    26000|          3235|           162|
    27000|          4118|           143|
    28000|          3483|           145|
    29000|          3906|           144|
    30000|          3801|           145|
    31000|          4322|           166|
    32000|          4057|           146|
    33000|          4516|           167|
    34000|          4566|           147|
    35000|          4453|           148|
    36000|          4708|           148|
    37000|          4772|           149|
    38000|          5391|           168|
    39000|          5500|           150|
    40000|          5048|           150|
    41000|          4979|           150|
    42000|          5402|           151|
    43000|          6160|           171|
    44000|          6402|           153|
    45000|          5855|           152|
    46000|          5702|           152|
    47000|          6184|           153|
    48000|          5963|           154|
    49000|          6927|           155|
    50000|          6611|           154|
    51000|          6326|           155|
    52000|          6488|           155|
    53000|          7690|           156|
    54000|          7245|           156|
    55000|          7074|           156|
    56000|          6998|           154|
    57000|          8299|           157|
    58000|          7456|           156|
    59000|          7776|           156|
    60000|          8015|           189|
    61000|          7762|           160|
    62000|          8145|           158|
    63000|          7946|           158|
    64000|          9157|           156|
    65000|          8299|           157|
    66000|          8399|           159|
    67000|          9119|           159|
    68000|          8758|           159|
    69000|          8921|           161|
    70000|          9366|           162|
    71000|          9326|           170|
    72000|          9035|           161|
    73000|          9873|           189|
    74000|          9642|           189|
    75000|         10272|           185|
    76000|         10299|           163|
    77000|         10602|           162|
    78000|          9878|           165|
    79000|         10790|           168|
    80000|         10535|           165|
    81000|         10627|           164|
    82000|         11579|           166|
    83000|         11003|           167|
    84000|         11778|           164|
    85000|         10686|           167|
    86000|         11280|           168|
    87000|         12562|           171|
    88000|         11190|           197|
    89000|         12949|           167|
    90000|         11954|           169|
    91000|         13170|           168|
    92000|         12013|           169|
    93000|         12245|           170|
    94000|         12949|           194|
    95000|         12264|           172|
    96000|         13754|           170|
    97000|         12919|           171|
    98000|         14172|           170|
    99000|         13436|           172|
   100000|         14466|           171|

I'd guess this is to do with JIT warming up - after all, the linear search for `1000` is very slow too. What happens if you reverse the order of the for loop over `n`? — Andy Turner, Oct 13 '15 at 21:00
Possible duplicate of [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — resueman, Oct 13 '15 at 21:01
Thanks @AndyTurner haven't even thought of that, I understand why that is now :) — Clutchy, Oct 13 '15 at 21:08
Clutchy, I strongly urge you to look at the link posted by @resueman. Good benchmarks are really important, but they're really hard to get right without some information. I suspect if you run your searches a bunch of times first to get things warmed up (without saving results) and then interleave your calls to the linear and binary (search with linear, search with binary, save the results, repeat), you'll see a much smoother curve. You also might want to look at the selection of your target number, and hold it to be the same (generate your random outside of the find methods). — CPerkins, Oct 13 '15 at 21:22
Oh, and you should also definitely be generating your array to be searched outside of the find methods and pass it in along with the target. That way the find methods don't pay the cost of the array creation. — CPerkins, Oct 13 '15 at 21:24
@CPerkins I am reading it as we speak, as for results they are consistent enough for my liking I just didn't understand why is the time difference 5 times lower on an array 10 times the size. — Clutchy, Oct 13 '15 at 21:32
@CPerkins they don't pay the cost of array creation because the timer starts after the array is already generated. — Clutchy, Oct 13 '15 at 21:34
You may also find http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array useful in your investigations. It is not about Java, but some of the same principles apply. — Jonah Graham, Oct 13 '15 at 21:48

score 1 · Accepted Answer · answered Oct 13 '15 at 22:30

1

You should give a chance to JIT compiler for heating. Try this one instead:

for (int j = 0; j < 20; j++) {
    System.out.printf("%n%nCycle # %d%n%n%n%n", j);
    for (int i = 1000; i <= 100000; i += 1000) {
        System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
    }
}

answered Oct 13 '15 at 22:30

ursa

4,404
1
24
38

This warms it up nicely and you can see the change. Thanks. – Clutchy Oct 13 '15 at 23:12

score -1 · Answer 2 · answered Nov 18 '20 at 11:43

-1

the smaler lists are only perfomed by 1 or 2 cpu cores but with the biger lits all of your cores are bing used and so it is faser.

answered Nov 18 '20 at 11:43

Gordon Prime

11
1
3

The code of the OP is singlethreaded, so it will not use more than one core. – Mark Rotteveel Nov 18 '20 at 13:30
Please add some explanation to your answer such that others can learn from it – Nico Haase Nov 18 '20 at 14:33

Binary search slow on smaller arrays

2 Answers2