c++ - 计算算法的绝对处理时间

Question

出于这个问题的目的，我对大 O 计算不感兴趣；据我了解，它用于比较算法之间的相对比较，而我想估计运行算法所花费的绝对时间。

例如，我使用的视觉算法每帧执行大约 200 万次计算。该程序在 core-i7 桌面上运行。那么，需要多长时间？

要计算此持续时间，我应该将哪个 cpu 操作作为最坏情况计算（*、/、+、.. 浮点数或其他）？

Answer 1

您可以每秒使用浮点运算并计算算法所需的最坏情况。您还可以使用特定（且足够大）的输入大小为您的算法计时，并使用时间复杂度分析来估计最坏情况下的执行时间。

Answer 2

您必须以某种方式获得执行时间的基线，因为执行时间可能会因架构而异。

例如，缓存未命中可能会占用 300 个 CPU 周期，而如果您有缓存命中，相同的数据访问可能仅占用 5 个周期。如果将所有变量访问加起来，从长远来看，它可以改变很多运行时间。

因此，您必须了解算法在特定输入大小上的执行时间。然后将其与预期的复杂性（Big-O 复杂性）相匹配。然后，您推导出前导常数的近似值，您现在可以在合理的输入上获得算法执行时间的近似值。

合理的，我的意思是你不会遇到完全不同的行为的输入，比如交换/分页（你基本上对运行时间不太了解）。

Answer 3

如果没有更多信息，可能无法给出有意义的答案。

首先，很大程度上取决于这些操作中有多少可以并行执行。首先让我们考虑一下理想情况：您已经优化了代码以完美地并行执行。每个内核每个时钟周期执行 4 条指令。

在这种情况下，您将在每个时钟周期停用 16 条指令，因此您有 200 万/16 = 125000 个时钟周期。在 4 GHz 时，计算结果为 31.25 微秒。

在相反的极端，让我们假设代码是完全串行的——每个时钟周期最多有一条指令退出。对于更糟糕的情况，它可能不仅是串行的，而且还受到严重的内存限制，因此每（例如）一百个时钟周期（平均）只有一条指令退休。在这种情况下，执行相同数量的指令需要 50 毫秒——慢了 1000 倍以上。

当然，这些都是非常极端的例子——更典型的情况可能是几十条指令的高速缓存未命中，平均每个时钟周期有 1.8 条指令。如果平均使用 2.5 个内核，则每个时钟周期平均可以获得 4.5 条指令。这将提供 444444 个时钟周期，计算结果为 111 微秒（再次假设 4 GHz）。