哪个更好？(n - 乘法) vs (n/2 - 乘法 + 2 加法)

Question

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

- Tejas Joshi

---

这在很大程度上取决于你所使用的物理硬件和编译器。如果真的很重要，就在目标环境中对其进行基准测试。 - Eric J.

这也在很大程度上取决于所使用的技术。这个问题太泛泛了，无法给出一个好的答案。 - Jeremy Holovacs

测量它并找出答案（但请记住，任何结果仅适用于您当前的配置）。 - Keith Thompson

谢谢。我尝试了非常大的值。第一个比第二个要慢近1.6倍。 - Tejas Joshi

如果 n=0，则第一个更好。 - Ivan Kuckir

Answer 1

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

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

我猜N个加法+ N/2个乘法比N个乘法慢，如果你正在进行折叠类型操作，我会猜测反之亦然。但这只是一个猜测。

如果想要真相，请进行测试。

然而：大多数如此简单的算法都是内存绑定型的，两者速度将相同。

- Dietrich Epp

Answer 2

首先，按照Dietrich Epp的第一个建议 - 测量（至少对于复杂的优化问题）是确保正确的唯一方法。

现在，如果你想找出一个更快的原因，我们可以试试。有两个不同的重要性能指标：延迟和倒数吞吐量。以下是两者的简要概述：

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

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

对于Sandy Bridge，add r，r/i（r=寄存器，i=立即数，m=内存）的倒数吞吐量为0.33，而延迟为1。 imul r，r的延迟为3，倒数吞吐量为1。

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

此外，请注意，我们忽略了所有额外的复杂性，如内存和缓存行为（这些东西通常对执行时间有更大的影响）或微妙的东西，如µop融合等。总的来说，唯一需要关心这些东西的人是编译器编写者 - 测量他们的努力的结果要简单得多 ;)

无论如何，如果你想获得这些东西的良好清单，请参见这里（上述延迟/倒数吞吐量的描述也来自该特定文档）。

- Voo