C++ 中的线性搜索与二分搜索实时性能

Question

使用以下代码在 C++ 中比较二分搜索与线性搜索的实时性能时得到完全出乎意料的结果 -

typedef std::chrono::microseconds us;

int linear_search(uint64_t* val, int s, int e, uint64_t k) {
    while (s < e) {
      if (!less<uint64_t>()(val[s], k)) {
        break;
      }
      ++s;
    }
    return {s};
}

int binary_search(uint64_t* val, int s, int e, uint64_t k) {
    while (s != e) {
      const int mid = (s + e) >> 1;
      if (less<uint64_t>()(val[mid], k)) {
        s = mid + 1;
      } else {
        e = mid;
      }
    }
    return {s};
}


int main() {

    // Preparing data
    int iter = 1000000;
    int m = 1000;
    uint64_t val[m];
    for(int i = 0; i < m;i++) {
        val[i] = rand();
    }
    sort(val, val + m);
    uint64_t key = rand();

    // Linear search time computation
    auto start = std::chrono::system_clock::now();
    for (int i = 0; i < iter; i++) {
        linear_search(val, 0, m - 1, key);
    }
    auto end = std::chrono::system_clock::now();
    auto elapsed_us = std::chrono::duration_cast<us>(end - start);
    std::cout << "Linear search: " << m << " values "
              << elapsed_us.count() << "us\n";

    // Binary search time computation
    start = std::chrono::system_clock::now();
    for (int i = 0; i < iter; i++) {
        binary_search(val, 0, m - 1, key);
    }
    end = std::chrono::system_clock::now();
    elapsed_us = std::chrono::duration_cast<us>(end - start);
    std::cout << "Binary search: " << m <<" values "
              << elapsed_us.count() << "us\n";
}

未经优化编译，得到如下输出-

Linear search: 1000 values 1848621us
Binary search: 1000 values 24975us

当使用 -O3 优化编译时，得到这个输出 -

Linear search: 1000 values 0us
Binary search: 1000 values 13424us

我知道对于小数组大小，二进制搜索可能比线性搜索昂贵，但无法通过添加 -O3 来理解造成如此巨大差异的原因

Answer 1

编译器设法意识到您的线性搜索是一个 noop（它没有副作用）并将其转换为无所事事。所以它需要零时间。

要解决这个问题，请考虑取 return 值并将其相加，然后在计时块外打印。

Answer 2

我用 https://quick-bench.com 对你的代码进行了基准测试，二进制搜索要快得多（对于 m = 100，它在 m = 1000 时中断）。那是我的基准代码：

int linear_search(uint64_t* val, int s, int e, uint64_t k) {
    while (s < e) {
      if (!std::less<uint64_t>()(val[s], k)) {
        break;
      }
      ++s;
    }
    return s;
}

int binary_search(uint64_t* val, int s, int e, uint64_t k) {
    while (s != e) {
      const int mid = (s + e) >> 1;
      if (std::less<uint64_t>()(val[mid], k)) {
        s = mid + 1;
      } else {
        e = mid;
      }
    }
    return s;
}

constexpr int m = 100;
uint64_t val[m];
uint64_t key = rand();
void init() {
  static bool isInitialized = false;
  if (isInitialized) return;
  for(int i = 0; i < m;i++) {
    val[i] = rand();
  }
  std::sort(val, val + m);
  isInitialized = true;
}

static void Linear(benchmark::State& state) {
  init();
  for (auto _ : state) {
    int result = linear_search(val, 0, m - 1, key);
    benchmark::DoNotOptimize(result);
  }
}
BENCHMARK(Linear);

static void Binary(benchmark::State& state) {
  init();
  for (auto _ : state) {
    int result = binary_search(val, 0, m - 1, key);
    benchmark::DoNotOptimize(result);
  }
}
BENCHMARK(Binary);

结果：

仅对 for (auto _ : state) { 中的代码进行了基准测试。

C++ 中的线性搜索与二分搜索实时性能

Linear search vs binary search real time performance in C++

c++

binary-search

compiler-optimization

linear-search