单乘法使代码在fastmod实现中慢10倍

Question

这里是一个fastmod包装器，我已经实现了两个使用它的运算符：

class fastmod
{
public:
  [[using gnu: cold]] fastmod(uint64_t denominator) : denominator_(denominator) 
  { 
    M_ = static_cast<__uint128_t>(-1) / denominator + 1; 
  }

private:
  friend uint64_t operator/(uint64_t, fastmod const&);
  friend uint64_t operator%(uint64_t, fastmod const&);

private:
  uint64_t denominator_;
  __uint128_t M_;
};

[[using gnu: hot, always_inline]] inline uint64_t operator/(uint64_t numerator, fastmod const&     divisor)
{
  return ((divisor.M_ & 0xFFFFFFFFFFFFFFFFULL) * numerator >> 64ULL) + ((divisor.M_ >> 64ULL) * numerator >> 64ULL);
}

[[using gnu: hot, always_inline]] inline uint64_t operator%(uint64_t numerator, fastmod const& divisor)
{
  __uint128_t magic = divisor.M_ * numerator;
  return ((magic & 0xFFFFFFFFFFFFFFFFULL) * divisor.denominator_ >> 64ULL) + ((magic >> 64ULL) * divisor.denominator_ >> 64ULL);
}

以正常整数除法为基准，我看到以下结果（与gcc9.1 -O3 -std=c++17 -c编译：]

-----------------------------------------------------------------
Benchmark              Time             CPU   Iterations
-----------------------------------------------------------------
div_bench           6.19 ns         6.17 ns    113415439
mod_bench           6.18 ns         6.17 ns    113532739
fastdiv_bench       2.06 ns         2.06 ns    340581374
fastmod_bench       25.8 ns         25.7 ns     27230411

使用基准测试代码

std::mt19937_64 mt;
fastdiv denominator = mt() % (1ULL << 27);

for(auto _ : state)
{
  auto numerator = mt();
  benchmark::DoNotOptimize(numerator % denominator);
}

对于fastmod_bench和

std::mt19937_64 mt;
fastmod denominator = mt() % (1ULL << 27);

for(auto _ : state)
{
  auto numerator = mt();
  benchmark::DoNotOptimize(numerator / denominator);
}

对于fastdiv_bench。

fastmod_bench结果不是我期望的。我强烈怀疑这是由于行

__uint128_t magic = divisor.M_ * numerator;

因为如果我删除了这个并仅用magic替换了numerator，则新结果将变为

fastmod_bench       1.70 ns         1.70 ns    412247047

比乘法快十倍以上。

我想知道为什么引入这种乘法后，此代码的运行速度甚至比常规整数除法慢4倍。我希望我的基准以及除法基准在2ns范围内。

我在这里将其加载到[godbolt：https://godbolt.org/z/4fcAQA中，但是我看不到任何东西可以迅速解释为什么由于乘法而导致性能下降的原因。

---

[不幸的是，这似乎是我的基准测试的问题；数字生成必须以某种方式与模数相互作用。这是一个新的基准，相同的编译器/选项：

std::mt19937_64 mt;
fastmod denominator = mt() % (1ULL << 27);
uint64_t numerator{10001107};
constexpr uint64_t transform{10005731};

for(auto _ : state)
{
  numerator *= transform;
  benchmark::DoNotOptimize(numerator % denominator);
}

（类似地划分。）

我现在得到以下结果：

-----------------------------------------------------------------
Benchmark              Time             CPU   Iterations
-----------------------------------------------------------------
div_bench           5.22 ns         5.20 ns    134608758
mod_bench           5.22 ns         5.20 ns    134627064
fastmod_bench       1.30 ns         1.30 ns    540373271
fastdiv_bench       1.30 ns         1.30 ns    540333224

Answer 1

[谢谢@Mark Ransom，他提出了改善我的基准测试的建议。尽管这确实使我获得了更多合理的数字，但是我对当前的方法可能会对性能产生如此巨大的影响并不满意。