Xrhrft

I'm putting together an example for students where I would like to show how we can optimize even such basic algorithm like a binary search with respect to hardware. I do not consider threads. I wrote it in C++ and the whole example can be found here. I'm trying to show some examples of the prefetching.

Test data If we would like to see the effects of the optimizations proposed in the following examples, then it is necessary to use data that are not in the CPU cache.

We are going to test it using some code like this

// arr - array with at least 100MB of values

// test_arr - array with values that we are going to search in arr

// test_count - size of the test_arr

for (auto i = 0u; i < test_count; ++i) {

   auto position = binarySearch(item_count, arr, test_arr[i]);

}

Size - If the arr array is significantly larger then largest CPU cache then most of the array won't be stored there and we will inevitably experience the L2 cache misses during the run. L2 cache misses are slow and it will become the major bottleneck of our binary search algorithm.

Randomness - It is better to have data in the test_arr that accesses the arr randomly, otherwise, the basic binary search algorithm will benefit from data access locality.

Please note that the L2 cache misses can be experienced even on a small array in some complex algorithm which works with a lot of data. In other words, we need a large array only for the purpose of testing, but the optimization can be useful everywhere where expect the binary search to happen on a data outside of CPU cache.

The basic algorithm It is something along these lines:

using Type = int64_t;

int binarySearch_basic(size_t item_count, const Type arr, int search)

{

    int l = 0;

    int r = item_count - 1;

    while (l <= r) {

        int m = l + ((r - l) >> 1);

        if (arr[m] == search) return m;

        if (arr[m] < search) l = m + 1;

        else r = m - 1;

    }

    return -1;

}

Prefetch The first optimization simply try to prefetch possible memory in advance

int binarySearch_basic(size_t item_count, const Type arr, int search)

{

    int l = 0;

    int r = item_count - 1;

    while (l <= r) {            

        int m1 = arr[l + ((r - l) >> 2)]; // new code 

        int m2 = arr[r - ((r - l) >> 2)]; // new code 



        int m = l + ((r - l) >> 1);

        if (arr[m] == search) return m;

        if (arr[m] < search) l = m + 1;

        else r = m - 1;

    }

    return -1;

}

More items per iteration The second optimization is a little bit more sophisticated. It accesses more than one item per iteration which allows read more relevant data per CPU L2 cache miss wait.

int binarySearch_duo(size_t item_count, const Type arr, int search)

{

    int l = 0;

    int r = item_count - 1;

    while (r - l > 3) {



        int delta = (r - l) / 3;

        int m1 = l + delta;

        int m2 = r - delta;



        if (arr[m1] == search) return m1;

        if (arr[m2] == search) return m2;



        if (arr[m1] < search) {

            if (arr[m2] < search) {

                l = m2 + 1;

            }

            else {

                r = m2 - 1;

                l = m1 + 1;

            }

        }

        else {

            r = m1 - 1;

        }

    }



    for (int i = l; i <= r; i++)

    {

        if (arr[i] == search) return i;

    }



    return -1;

}

Of course, this approach can be done with more accesses per iteration (I'm testing three as well in my demo). There are some infinite loop issues if the (l,r) interval is very small (less then three), therefore, I finish the remaining items by a simple sequential search to keep the main iteration clean and simple.

I was doing my tests with Visual Studio 2017 C++ compiler.

I have several questions:

• Are there any other possible significant optimizations that could help the algorithm?


• Is my explanation of the improvement of the last algorithm correct? (is it really due to the fact that the CPU read in parallel two data items; therefore, he waits for it just once not twice like in the first algorithm).


• Are there any other comments about my code?

How did you measure the performance of your code (test code, hardware, compiler, etc.)? Without that it is impossible to get into optimization. Depending on chosen compiler I was sort of able to reproduce your results, see this quick bench- for clang 7.0.0 the fancy algorithm is indeed faster. That being said with gcc the basic one is a lot faster (outperforming fancy algorithm in both clang and gcc).

With that in mind, you can optimize your algorithm for different array sizes quite easily (benchmarking on your specific setup), by choosing fastest of the 3 for specific sizes.

As far as the code is concerned, there are a couple of things you can improve.

You could rewrite your algorithms so that they accept iterators, just like all the algorithms from standard library, that will drastically improve their flexibility without added effort (and most probably without degrading performance, but you should measure it anyway).
Apart from that, you should avoid implicit casts, e.g. here:

int r = item_count - 1;

You should also prefer to keep the bodies of your functions short, it's hard to understand what binarySearch_duo actually does (you could easily extract body of the loop etc). Also, avoid magic constants, where does the seven in: while (r - l > 7) { come from?

Edit: I've creted one more benchmark for this, this time as proposed by OP, that is with huge array size (actually a vector) and made the access to the elements of the array random, see here- this time with gcc fancy version is as good as basic. The lesson should probably be: compiler is usually at least as smart as you are :).