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

Question

Getting totally unexpected results while comparing binary search vs linear search's real time performance in C++ using the code below -

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

Compiling without optimisation, getting following output -

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

When compiled with -O3 optimisation, getting this output -

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

I understand that for small array size, binary search may be expensive than linear but can't understand reason for difference of this magnitude by adding -O3

Answer 1

I benchmarked your code with https://quick-bench.com and binary search is much faster (for m = 100, it breaks for m = 1000). That's my benchmark code:

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

and the result:

Only the code inside for (auto _ : state) { is benchmarked.