4

我有一个 C 程序，它有 n 次乘法（单次乘法和 n 次迭代），我发现另一个逻辑有 n/2 次迭代（1 次乘法 + 2 次加法）。我知道两者都是 O(n) 的复杂性。但就 CPU 周期而言。哪个更快？

4

2 回答 2

3

在你的电脑上测试。或者，查看您的处理器的规格并猜测。

旧的逻辑不再适用：在现代处理器上，整数乘法可能非常便宜，在一些新的英特尔处理器上，它是 3 个时钟周期。在这些相同的处理器上，加法是 1 个周期。然而，在现代流水线处理器中，由数据依赖造成的停顿可能会导致添加时间更长。

我的猜测是，如果您进行折叠类型的操作，N 次加法 + N/2 次乘法比 N 次乘法要慢，而对于映射类型的操作，我猜相反。但这只是一个猜测。

测试你是否想要真相。

但是：大多数这么简单的算法都是受内存限制的，并且两者的速度相同。

于 2011-08-16T00:25:44.820 回答
2

首先遵循 Dietrich Epp 的第一个建议 - 测量（至少对于复杂的优化问题）是唯一确定的方法。

现在，如果您想弄清楚为什么一个比另一个快，我们可以尝试。有两种不同的重要性能指标：延迟和互惠吞吐量。两者的简短总结：

延迟：这是指令在依赖链中生成的延迟。数字是最小值。高速缓存未命中、未对齐和异常可能会显着增加时钟计数。在启用超线程的情况下，在另一个线程中使用相同的执行单元会导致性能下降。非正规数、NAN 和无穷大不会增加延迟。使用的时间单位是核心时钟周期，而不是时间戳计数器给出的参考时钟周期。

倒数吞吐量：同一线程中一系列同类独立指令的每条指令的平均核心时钟周期数。

对于桑迪桥的记录。add r, r/ian （进一步注意 r=register，i=immediate，m=memory）的吞吐量为0.33，而延迟为 1。

Animul r, r的延迟为 3，rec。吞吐量为 1。

因此，正如您所看到的，它完全取决于您的特定算法 - 如果您可以将一个 imul 替换为两个独立的添加，那么您算法的这个特定部分可以获得 50% 的理论加速（在最好的情况下显然加速约 350% ）。但另一方面，如果您的添加添加了一个有问题的依赖项，那么一个 imul 可能与一个添加一样快。

另请注意，我们忽略了所有额外的复杂性，例如内存和缓存行为（通常会对执行时间产生非常大的影响）或诸如 µop 融合之类的复杂事物。一般来说，唯一应该关心这些东西的人是编译器编写者——仅仅衡量他们努力的结果要简单得多；）

Anyways if you want a good listing of this stuff see this here (the above description of latency/rec. throughput is also from that particular document).

于 2011-08-16T00:51:11.873 回答