在我看来，我发现了一个比 std:max 运行速度更快的函数

Question

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

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实现长很多倍。

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

假设您的主张是正确的：

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

这是一个带有更好（虽然没有经过严格验证）的基准的快速测试。

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

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

然而，与您的情况相反，天真和标准库实现实际上可以处理所有可能的输入值（我将向量中的测试用例值限制为适用于您的实现的范围。）

在这个基准测试的前一个版本中，我犯了一个错误（做正确的基准测试很困难！）这使得看起来好像幼稚的实现比std::maxOP 的实现更糟糕，结果证明这是谷歌基准测试DoNotOptimize工作的产物（在至少在 Clang 上，也许这是 google 基准测试中的一个错误，或者我可能使用错误）。如果有人发现另一个缺陷，请告诉我！

基准代码：

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