我想知道模数(%
)运算符的运行速度。我已经建立了一个简单的程序来对将%
应用于随机生成的值进行基准测试。使用高分辨率时钟以毫秒为单位测量时间。通常,它报告0ns已经过去。显然没有瞬间发生什么,那为什么会这样呢?如果将轮数增加到约50,000,通常需要约1,000,000ns。但是即使5000轮也总是0ns。我测量错了吗?正在为此进行哪些优化?
#include <iostream>
#include <chrono>
#include <random>
void runTest(const int rounds, const int min, const int max);
int main()
{
std::cout << "started" << std::endl;
runTest(5000, 1000000, 2000000);
return 0;
}
/*IN: number of rounds to run on the test, the min and max value to choose between for operands to mod
OUT: time taken (in nanoseconds) to complete each operation on the same randomly generated numbers*/
void runTest(const int rounds, const int min, const int max)
{
std::random_device rd; // only used once to initialise (seed) engine
std::mt19937 rng(rd()); // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased
std::chrono::nanoseconds durationNormalMod = std::chrono::nanoseconds::zero();
std::chrono::nanoseconds durationFastMod = std::chrono::nanoseconds::zero();
long long result = 0;
for(auto i = 0; i < rounds; i++)
{
const int leftOperand = uni(rng);
const int rightOperand = uni(rng);
auto t1 = std::chrono::high_resolution_clock::now();
long long x = (leftOperand % rightOperand);
auto t2 = std::chrono::high_resolution_clock::now();
//std::cout << "x: " << x << std::endl;
result += x;
durationNormalMod += std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1);
}
std::cout << "duration of %: " << durationNormalMod.count() << std::endl;
std::cout << "result: " << result << std::endl;//preventing optimization by using result
}
我用g++ prog.cpp -o prog.exe -O3
进行编译。
我很感兴趣,因为我有一个特殊的情况,我可以使用其他算法来实现模数,我很好奇它是否更快。
基准测试时,重要的是:
Use以某种方式计算的结果。任何从未使用过的结果及其导致的计算都可以并且将被优化的编译器删除。
时间不是单个计算,而是许多计算,以使时钟访问之间的经过时间约为毫秒。这是因为时钟访问是一项相对昂贵的操作,并且会大大延迟非常快速的计算的时间。
禁用CPU时钟频率缩放或至少在测量时间之前预热CPU。
关于所谓的“假设规则”进行了优化。只要可观察的行为相同,就允许编译器对您的代码执行任何转换。由于您不使用计算结果,因此完全不执行计算时就不会有可观察到的变化。测量的时间不算作可观察到的行为(请参见here)。
[时钟,即使是high_resolution_clock,在大多数实现中,其粒度也不足以测量纳秒。
您必须连续执行多项操作,并将总时间除以重复次数。您已经有了一个循环:将时间测量移到循环外部。并增加重复次数。
但是,这有点棘手,因为循环有时会导致编译器执行某些矢量运算,而不是预期的琐碎重复。
您还必须使用计算结果,否则优化器将根本不执行计算结果。