c++ - 为什么自制的二进制搜索算法比std::binary_search慢？

一种简单的自制二进制搜索算法被std::binary_search击败(再次):

// 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);
}

编译文件(如果另存为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

去测试

./t2 ; ./t0 ; ./t1

在我的机器上，它输出(时间越短，速度越快):

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

将EXAMPLE_COMPARE_VERSION设置为0时，我们使用自制的二进制搜索算法。

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;
}

将EXAMPLE_COMPARE_VERSION设置为1时，我们使用:

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

将EXAMPLE_COMPARE_VERSION设置为2时，我们使用:

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;
}

这两个std::binary_search函数在gcc头文件目录的bits/stl_algo.h中定义。

问题

为什么使用比较功能(t2)的std::binary_search比没有功能的版本(t1)快得多？

有时甚至t1比自制二进制搜索程序(t0)更快。为什么t0这么慢，如何加快速度？

更新:

将random()替换为rand()，另请参见What difference between rand() and random() functions?

最佳答案

因为基准存在缺陷。

您正在循环(和定时)区域内调用random:它的运行时不仅有问题(并影响基准)，而且还意味着您可能没有在基准

上测量相同的运行

由于花费的时间取决于随机输出，因此您使用了哪种统计方法尽可能公平？平均5次交错运行？ 5个交错运行中最好的？ ...

现在，即使清除了碎石，您也可能最终会遇到标准算法比您自己的自制解决方案更快的情况。此时，请考虑一下C++的理念:您不需要为不需要的东西付钱。结果，如果不对标准实现进行优化，至少可以使其精简到足以与幼稚的方法一样快:如果可以的话，它们早已被修补了!

因此，最后，您需要研究差异。此时，您需要深入研究代码并了解其映射方式。我建议您使用源代码，LLVM IR或程序集进行此探索(如果您不理解某些转换，请随时提问)。

也许正在展开一些事情？也许更好地暗示了测试？谁知道，几十年后，您可能会发现一颗珍珠。

注意:要在http://coliru.stacked-crooked.com上获取LLVM IR，请使用以下命令行clang -O3 -S -emit-llvm -o main.ll main.cpp && cat main.ll