why homemade binary search algorithm is slower than std::binary_search?

Question

A simple homemade binary search algorithm is defeated by std::binary_search (once again):

// gcc version 4.8.2 X86_64

#ifndef EXAMPLE_COMPARE_VERSION
# define EXAMPLE_COMPARE_VERSION 0
#endif

static const long long LOOPS = 0x1fffffff;

#include <cassert>
#include <cstdlib>
#include <ctime>
#include <cstdio>

#if EXAMPLE_COMPARE_VERSION
#include <algorithm>

inline bool stl_compare(const int l, const int r) {
  return l < r;
}

#else

inline bool compare(const int *beg, const int *end, int v) {
  for (const int *p; beg <= end;) {
    p = beg + (end - beg) / 2;
    if (*p < v) beg = p + 1;
    else if (*p > v) end = p - 1;
    else return true;
  }
  return false;
}
#endif

int main() {
  const int arr[] = {
    1784, 1785, 1787, 1789, 1794, 1796, 1797, 1801, 
    1802, 1805, 1808, 1809, 1912, 1916, 1918, 1919, 
    1920, 1924, 1925, 1926, 1929, 1930, 2040, 2044, 
    2047, 2055, 2057, 2058, 2060, 2061, 2064, 2168, 
    2172, 2189, 2193, 2300, 2307, 2309, 2310, 2314, 
    2315, 2316, 2424, 2429, 2432, 2433, 2438, 2441, 
    2448, 2552, 2555, 2563, 2565, 2572, 2573, 2680, 
    2684, 2688, 2694, 2697, 2699, 2700, 2704, 2705, 
    2808, 2811, 2813, 2814, 2816, 2818, 2822, 2826, 
    2827, 2828, 2936, 2957, 3064, 3070, 3072, 3073, 
    3074, 3075, 3076, 3077, 3078, 3081, 3082, 3084, 
    3085, 3086, 3088, 3192, 3196, 3198, 3200, 3205, 
    3206, 3211, 3212, 3213, 3326, 3327, 3328, 3330, 
    3331, 3333, 3337, 3338, 3339, 3344, 3448, 3449, 
    3451, 3452, 3454, 3459, 3461, 3462, 3465, 3469, 
    3472, 3578, 3585, 3588, 3593, 3594, 3704, 3712, 
    3715, 3722, 3723, 3852, 3972, 3973, 3974, 3980, 
    3982, 4088, 4090, 4091, 4092, 4094, 4096, 4098, 
    4099, 4100, 4101, 4102, 4103, 4105, 4106, 4107, 
    4108, 4109, 4110, 4216, 4220, 4222, 4223, 4224, 
    4226, 4227, 4229, 4230, 4233, 4234, 4235, 4238, 
    4240, 4350, 4354, 4361, 4369, 4476, 4480, 4486, 
    4600, 4614, 4735, 4864, 4870, 4984, 4991, 5004, 
  };
  clock_t t = clock();
  const size_t len = sizeof(arr) / sizeof(arr[0]);
  for (long long i = 0; i < LOOPS; i++) {
    int v = arr[rand() % len];
#if EXAMPLE_COMPARE_VERSION >= 2
    assert(std::binary_search(arr, arr + len, v, stl_compare));
#elif EXAMPLE_COMPARE_VERSION
    assert(std::binary_search(arr, arr + len, v));
#else 
    assert(compare(arr, arr + len, v));
#endif
  }
  printf("compare version: %d\ttime: %zu\n",
      EXAMPLE_COMPARE_VERSION, (clock() - t) / 10000);
}

To compile the file (if saved as t.cc)

g++ t.cc -O3 -DEXAMPLE_COMPARE_VERSION=0 -o t0
g++ t.cc -O3 -DEXAMPLE_COMPARE_VERSION=1 -o t1
g++ t.cc -O3 -DEXAMPLE_COMPARE_VERSION=2 -o t2

To test

./t2 ; ./t0 ; ./t1

On my machine it outputs (the smaller time the quicker):

compare version: 2      time: 3533
compare version: 0      time: 4074
compare version: 1      time: 3968

when setting EXAMPLE_COMPARE_VERSION to 0 we use the homemade binary search algorithm.

inline bool compare(const int *beg, const int *end, int v) {
  for (const int *p; beg <= end;) {
    p = beg + (end - beg) / 2;
    if (*p < v) beg = p + 1;
    else if (*p > v) end = p - 1;
    else return true;
  }
  return false;
}

when setting EXAMPLE_COMPARE_VERSION to 1 we use:

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);

when setting EXAMPLE_COMPARE_VERSION to 2 we use:

template <class ForwardIterator, class T, class Compare>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

// the Compare function:
inline bool stl_compare(const int l, const int r) {
  return l < r;
}

The two std::binary_search functions are defined in bits/stl_algo.h in gcc header files directory.

The questions

1. Why std::binary_search using a compare function (t2) is much faster than the version without it (t1)?
2. Sometimes even t1 is quicker than homemade binary search program (t0). why t0 is so slow and how to speed it up?

---

Updates:

Replaced random() with rand(), see also What difference between rand() and random() functions?

Answer 1

Because the benchmark is flawed.

1. You are calling random inside the loop (and timed) area: not only is its runtime questionable (and impacting the benchmark), but it also means that you may not be measuring the same run across benchmarks
2. Since the time spent depends on a random output, what statistical method did you use to be as fair as possible ? Average over 5 interleaved runs ? Best of 5 interleaved runs ? ...

Now, even after clearing out the rubble, you may well end up in a situation where the standard algorithm is faster than your own homemade solution. At this point, think over the philosophy of C++: You don't pay for what you don't need. And as a consequence, the Standard implementations are likely to be, if not optimized, at the very least lean enough to be as fast as the naive method: if it ever was otherwise they have been patched a long time ago!

So, finally, you are left with examining the difference. At this point you need to delve into the code and understand how it maps. I advise using the source code, LLVM IR or assembly for this exploration (feel free to ask questions if you don't understand certain transformations).

Maybe there is some unrolling going on ? Maybe the tests are better hinted ? Who knows, after a couple decades of existence you might find a pearl.

Note: to get the LLVM IR on http://coliru.stacked-crooked.com, use the following command-line clang -O3 -S -emit-llvm -o main.ll main.cpp && cat main.ll

Answer 2

The compiler inlines the compare function anyway, and the STL implementations are usually written by gurus.