比较算法的执行时间：为什么执行顺序很重要？

Question

比较算法的执行时间：为什么执行顺序很重要？

c++algorithmprofilingperformance-testing

5

每当我尝试比较两个竞争算法（使用C++）的执行时间时，我使用std::chrono，就像在此问题中以前建议的一样：Measuring execution time of a function in C++ 然而，我总是注意到所比较的算法执行顺序显著影响了执行时间。这甚至经常改变了哪个竞争算法被认为是最快的。例如，假设我有两个算法algo1和algo2。

我的意思是下面的代码：

std::chrono::high_resolution_clock::time_point start0, start1;
std::chrono::high_resolution_clock::time_point end0, end1;

start1 = std::chrono::high_resolution_clock::now();
algo1();
end1 = std::chrono::high_resolution_clock::now();

start2 = std::chrono::high_resolution_clock::now();
algo2();
end2 = std::chrono::high_resolution_clock::now();

auto time_elapsed1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end1 - start1).count();
auto time_elapsed2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2).count();

与以下代码产生不同的结果：

std::chrono::high_resolution_clock::time_point start0, start1;
std::chrono::high_resolution_clock::time_point end0, end1;

start2 = std::chrono::high_resolution_clock::now();
algo2();
end2 = std::chrono::high_resolution_clock::now();

start1 = std::chrono::high_resolution_clock::now();
algo1();
end1 = std::chrono::high_resolution_clock::now();

auto time_elapsed1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end1 - start1).count();
auto time_elapsed2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2).count();

对于我想要比较的几乎任何算法1和算法2来说，这种情况都是如此。

因此，我的问题有两个方面：1）为什么会出现这种情况，即为什么顺序很重要？2）有没有更好的比较两个算法在执行时间方面的方法，即应该如何进行更好和更准确的比较？

附注：当然，我总是测试所有编译器的优化。

- Kim Shutter

4

需要多次运行算法并获得平均值。有些内容可以加载到缓存中，这会影响后续的运行结果。 - NathanOliver

你必须确保算法运行足够长的时间才能获得有意义的时间间隔。鉴于此，需要注意数据缓存的问题。尝试连续两次运行每个 algo() 并计时第二次运行。 - doug

2

我假设你的函数具有可观察的副作用，否则它们可能会被完全优化掉。另外，像 @NathanOliver 说的那样，每个算法运行几千/几百万次并获得平均值。基准测试非常困难 ;) - Jesper Juhl

@JesperJuhl 可能是为什么一个好的基准测试会产生硬性数字的原因。 - user4581301

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wookie919 · Accepted Answer

这很可能是由于缓存引起的。您可以通过多次运行相同的算法来轻松验证缓存的效果。您可能会注意到，第一次执行所花费的时间比后续执行要长得多。当我不得不为我的博士论文比较两个算法时，我最终连续执行了每个算法10次，丢弃了第一个结果，然后平均了剩余的9个结果，这9个结果非常一致。是否重要丢弃第一个结果有争议，但对我来说并不重要，因为我更感兴趣的是比较两个算法的相对性能（因此正在寻找每个算法的一致运行时间），而不是测量缓存的影响或在不同情况下每个算法的绝对性能。