Why sentinel search slower than linear?

Question

I decided to reduce the number of comparisons required to find an element in an array. Here we replace the last element of the list with the search element itself and run a while loop to see if there exists any copy of the search element in the list and quit the loop as soon as we find the search element. See the code snippet for clarification.

import java.util.Random;

public class Search {

    public static void main(String[] args) {
        int n = 10000000;
        int key = 10000;
        int[] arr = generateRandomSize(n);
        long start = System.nanoTime();
        int find = sentinels(arr, key);
        long end = System.nanoTime();
        System.out.println(find);
        System.out.println(end - start);

        arr = generateRandomSize(n);
        start = System.nanoTime();
        find = linear(arr, key);
        end = System.nanoTime();
        System.out.println(find);
        System.out.println(end - start);
    }

    public static int[] generateRandomSize(int n) {
        int[] arr = new int[n];
        Random rand = new Random();

        for (int i = 0; i < n; ++i) {
            arr[i] = rand.nextInt(5000);
        }

        return arr;
    }

    public static int linear(int[] a, int key) {
        for(int i = 0; i < a.length; ++i) {
            if (a[i] == key) {
                return i;
            }
        }

        return -1;
    }

    public static int sentinels(int[] a, int key) {
        int n = a.length;
        int last = a[n-1];
        a[n-1] = key;

        int i = 0;
        while (a[i] != key) {
            ++i;
        }
        a[n-1] = last;
        if ((i < n - 1) || a[n-1] == key ) {
            return i;
        }

        return -1;
    }

}

So using sentinel search we are not doing 10000000 comparisons like i < arr.length. But why linear search always shows up better performance?

`i < arr.length` is unlikely to take much time. [Potentially related?](https://stackoverflow.com/q/11227809/5475891) — phflack, Apr 27 '19 at 07:40
There are flaws in your benchmark which mean that any results you get must be treated as doubtful. Please read this: ["How to write a correct micro-benchmark in Java"](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Stephen C, Apr 27 '19 at 07:45
this two method also need O(n) to finish work,you example in my computer `sentinels` is more faster — TongChen, Apr 27 '19 at 07:58
@rustyx also, I'm initing array with values between 0, 5000 and trying to find 10000 — indigo153, Apr 27 '19 at 08:12
@StephenC Changed to System.nanoTime() and I run my tests 100 times, the result still the same, linear search always better. — indigo153, Apr 27 '19 at 08:14
@petrush If you read the linked question, it talks about branch prediction. `i < arr.length` will take time to process for the first few iterations of the loop, but for the bulk of it I suspect it's mostly bypassed — phflack, Apr 27 '19 at 08:14

score 3 · Accepted Answer · answered Apr 27 '19 at 08:31

You'd have to look at the byte code, and even deeper to see what hotspot is making from this. But I am quite sure that this statement is not true:

using sentinel search we are not doing 10000000 comparisons like i < arr.length

Why? Because when you access a[i], i has to be bounds checked. In the linear case on the other hand, the optimiser can deduce that it can omit the bounds check since it "knows" that i>=0 (because of the loop structure) and also i<arr.length because it has already been tested in the loop condition.

So the sentinel approach just adds overhead.

This makes me think of a smart C++ optimisation (called "Template Meta Programming" and "Expression Templates") I did about 20 years ago that led to faster execution times (at cost of a much higher compilation time), and after the next compiler version was released, I discovered that the new version was able to optimise the original source to produce the exact same assembly - in short I should have rather used my time differently and stayed with the more readable (=easier to maintain) version of the code.

You would need to look at the native code. The bytecodes are not much help for performance issues. Fortunately, it is easy to get the JVM to dump the native code produced by the JIT compiler — Stephen C, Apr 27 '19 at 09:07
Your last paragraph is very instructive. Too many people waste time optimizing things when the pay-off is too small to be worth it. — Stephen C, Apr 27 '19 at 09:13

Why sentinel search slower than linear?

1 Answers1