c++ - 在我看来，我发现了一个比 std :max 运行得更快的函数

Question

有一天，我遇到了一项任务，需要在没有条件运算符和循环(以及位运算)的情况下确定两个数字中的最大值。经过深思熟虑，我做出了这个决定:

long long mmax(long long a, long long b) {
    return (a+b+(a-b)*((2*(a-b)+1)%2))/2;
}

只是为了好玩，我决定检查一下哪个函数更快，因此我在包含 10^7 对从 1 到 10^17 的随机整数的 3 个数据样本上测试了这两个函数大约 100 次。我很惊讶，因为对于从 1 到 10^5 的整数，我的函数的每次调用速度至少加快了 0.092 秒，而对于从 10^5 到 10^17 的整数，每次调用的速度至少加快了 0.044 秒。平均而言，我的函数在处理从 1 到 10^5 的整数时速度快了 0.1 秒，在处理从 10^5 到 10^17 的整数时速度快了 0.06 秒。所以，我不是优化方面的专家，因此我想问这个函数是否真的比 std:max 更快？

这是我的测试代码:

#include <chrono>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

long long mmax(long long a, long long b) {
    return (a+b+(a-b)*((2*(a-b)+1)%2))/2;
}

int main(){
    auto started = std::chrono::high_resolution_clock::now();

    ifstream in("bilt.txt");

    long long a, b;
    while(in >> a >> b) {
        mmax(a,b);
    }

    auto done = std::chrono::high_resolution_clock::now();

    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(done-started).count() << endl;

}

Answer 1

您的基准测试不是对max进行基准测试。它完全受到输入操作所需时间的限制。输入操作花费的时间比 std::max 或您的 mmax 实现长很多倍。

此外，mmax 或 std::max 调用将被任何优化编译器优化掉，因为它们的结果从未被使用，并且它们没有任何其他结果副作用。参见例如here on godbolt 。因此，您可能根本不会对它们进行基准测试。

<小时/>

假设您的说法属实:

您的函数对于某些参数具有未定义的行为，而 std::max 则没有，例如如果a+b导致溢出，则它具有未定义的行为。因此，比较速度确实不公平，因为您的实现并不总是有效。

<小时/>

Here is a quick-bench具有更好的(尽管未经严格验证)基准。

• “std_impl”使用std::max
• “naive_impl”使用简单的分支来获取最大值
• “op_impl”是问题中的实现
• “only_iter”只传递第一个值，不进行任何计算

正如您在图中所看到的，您的实现比简单的实现或 std::max 更差，两者在性能上是相同的。

然而，与您的相反，天真的和标准库实现实际上适用于所有可能的输入值(我将 vector 中的测试用例值限制在适合您的实现的范围内。)

<小时/>

在此基准测试的先前版本中，我犯了一个错误(正确执行基准测试很困难!)，这使得幼稚的实现看起来比 std::max 和 OP 的实现要糟糕得多，事实证明，这是谷歌基准测试的 DoNotOptimize 工作原理的产物(至少在 Clang 上，也许这是谷歌基准测试中的一个错误，或者可能是我使用错误)。如果有人发现其他缺陷，请告诉我!

<小时/>

基准代码:

#include<random>
#include<cmath>
#include<utility>
#include<algorithm>

const auto N = 10'000;

auto values = []{
  std::vector<std::pair<long long, long long>> v;
  std::default_random_engine rng{std::random_device{}()};
  std::uniform_int_distribution<long long> dist{-100'000'000, 100'000'000};
  for(int i = 0; i<N; i++)
    v.emplace_back(dist(rng), dist(rng));
  return v;
}();


void std_impl(benchmark::State& state) {
  for (auto _ : state) {
      for(auto& x : values) {
        auto result = std::max(x.first, x.second);
        benchmark::DoNotOptimize(result);
      }
  }
}

void naive_impl(benchmark::State& state) {
  for (auto _ : state) {
      for(auto& x : values) {
        auto result = x.first > x.second ? x.first : x.second;
        benchmark::DoNotOptimize(result);
      }
  }
}

long long mmax(long long a, long long b) {
    return (a+b+(a-b)*((2*(a-b)+1)%2))/2;
}

void op_impl(benchmark::State& state) {
  for (auto _ : state) {
      for(auto& x : values) {
        auto result = mmax(x.first, x.second);
        benchmark::DoNotOptimize(result);
      }
  }
}

void only_iter(benchmark::State& state) {
  for (auto _ : state) {
      for(auto& x : values) {
        auto result = x.first;
        benchmark::DoNotOptimize(result);
      }
  }
}

BENCHMARK(std_impl);
BENCHMARK(naive_impl);
BENCHMARK(op_impl);
BENCHMARK(only_iter);