C#/XNA - 乘法比除法更快吗？

Question

最近我看到一条推文让我感到困惑（这是由一个XNA编码者发布的，在编写XNA游戏的上下文中）:

微优化提示：在高频区域尽可能使用乘法而不是除法。它会快几个周期。

我非常惊讶，因为我一直认为编译器很聪明（例如，使用位移），最近读了Shawn Hargreaves的一篇文章也说了同样的事情。我想知道其中有多少真相，因为我的游戏中有很多计算。

我询问了一下，希望能得到一个示例，但原始作者无法提供。然而，他确实说了这个：

当它是"center = width / 2"之类的东西时并不总是如此。而且我已经确定"是值得的"。 :)

所以，我很好奇...

有人能给出一个代码示例吗？在这个示例中，您可以将除法更改为乘法，并获得性能增益，而C#编译器无法自行完成相同的操作。

- Danny Tuppeny

---

相关：在C#中使用乘法移位优化整数除法，发现于相关问题如何最快地将整数除以3？) -- 展示了如何减少除法，例如作为编译器优化。利用了常量的事实，这是编译器可以确保程序员语义的最佳方式。一旦除法不是一个常量，编译器能做到的最好就是“按原样执行”。 - user166390

@pst 有趣的东西 - 谢谢！ - Danny Tuppeny

肖恩·哈格里夫斯的博客文章现在在这里发布：https://shawnhargreaves.com/blog/a-story-about-premature-optimization.html - Jonathan Johansen

Answer 1

大多数编译器在给它们机会的情况下都能做出合理的优化。例如，如果你正在除以一个常量，那么编译器很有可能会优化，使其执行速度与任何你可以合理替换的内容一样快。

然而，当你有两个不事先知道的值，并且你需要将一个除以另一个得到答案时，如果编译器能够做很多事情，它就会这样做。而且，如果编译器有足够的空间来进行优化，CPU 也会这样做，这样编译器就没必要再去优化了。

编辑：对于像这样（相对真实）的东西，你最好的选择可能是类似于：

double scale_factor = get_input();

for (i=0; i<values.size(); i++)
    values[i] /= scale_factor;

这相对容易转换成类似以下的内容：

scale_factor = 1.0 / scale_factor;

for (i=0; i<values.size(); i++)
    values[i] *= scale_factor;

我无法确保某个编译器会这样做，也无法否定。这基本上是强度降低和循环提升的组合。肯定有一些优化器知道如何同时进行两者，但我所见过的C#编译器似乎可能不会（但我从未测试过完全相同的内容，而且我测试的版本已经过时…）

- Jerry Coffin

---

@DanTup - Danny Tuppeny: 将整个算法重新排列以适应倒置是超出最复杂编译器能力之外的。 - Jerry Coffin

@Jerry，你说得有道理，但我认为推文的意图并不是这样做（我会称之为优化算法而不是“将除法改为乘法”）。我更新了我的问题，让它更明确一些：有人能举一个例子吗？在这个例子中，你可以将除法改为乘法并获得性能提升，而C#编译器无法自行完成相同的操作。 - Danny Tuppeny

@Jerry：这种转换会产生相同的结果吗？我有一种感觉，浮点运算会在某个地方出错...当然，小差异可能大多数时候并不重要，但我认为编译器这样做是不好的。 - R. Martinho Fernandes

@Martinho Fernandes：我最近没有阅读过C#规范的那部分，无法确定。我之所以建议这样做，是因为我并不真正期望大多数编译器会这样做，但在许多情况下（例如图形），结果将是很好的，而且转换也很容易。 - Jerry Coffin

@Jerry 这个示例看起来相当简单，但我可以看出几个编译器不能改变它的原因。我还没有测试过它（还没想出如何在我的iPad上运行cs...），但我猜它和原始推特者的思路差不多 :-) - Danny Tuppeny

Answer 2

尽管编译器可以优化2的幂次方的除法和乘法，但其他数字可能很难或不可能进行优化。尝试优化一个除以17的操作，你会发现为什么了。当然，这是假设编译器不知道你事先在运行时使用的除数是17（它是一个运行时变量，而不是常量）。

- Darkhydro

---

对于简单的“难以优化或不可能优化到恒定”的解决方案点赞。它实际上可以优化掉一个较大但更多（整数）除法。参见https://dev59.com/JXVC5IYBdhLWcg3w1E1q --虽然不一定如此。 - user166390

Answer 3

略晚了一些，但没关系。

你问题的答案是肯定的。

请看这里我写的文章：http://www.codeproject.com/KB/cs/UniqueStringList2.aspx。文章中的信息基于第一个评论中提到的文章。

我有一个QuickDivideInfo结构体，它存储了给定除数的魔数和位移，从而允许使用更快速的乘法进行除法和取模计算。我预先计算（并测试过！）了一组Golden Prime Numbers的QuickDivideInfos。至少在x64上，QuickDivideInfo上的.Divide方法被内联，并且比使用除法运算符（在i5上）快3倍；它适用于所有分子，除了int.MinValue，因为乘法在移位之前存储在64位中，所以不会溢出。（我没有在x86上尝试过，但如果由于某些原因它无法内联，则Divide方法的简洁性将会丢失，您将不得不手动内联它）。

因此，在所有场景下（除了int.MinValue），以上将起作用，如果您可以预计算的话。如果您信任生成魔数/位移的代码，那么您可以在运行时处理任何除数。

对于其他已知范围很小的小除数，可以将它们写成内联的形式，如果它们不需要一个中间long，可能会更快。

除以二的多个倍数：我希望编译器能处理这个问题（例如你的width / 2），因为它是常量。如果它无法处理，则将其更改为width >> 1 应该没有问题。

- Simon Hewitt

Answer 4

给一些数字，在这个pdf上

http://cs.smith.edu/dftwiki/index.php/CSC231_Pentium_Instructions_and_Flags

关于奔腾处理器，我们得到了一些数字，而它们并不好：

• IMUL 10或11
• FMUL 3+1
• IDIV 46（32位操作数）
• FDIV 39

我们谈论的是巨大的差异。

- xanatos

---

@DanTup 您的意思是它应该将 x 乘以 0.5 而不是除以 2 吗？或者（更好的是）如果 x 是整数，则应将其向左移动 1？ - xanatos

@xanatos 我想问的是，在什么情况下编译器无法优化我可以轻松优化的内容。我应该将所有的“/ 2”更改为“* 0.5”吗？如果我有varA * varB，我应该将其更改为除法吗？等等。 - Danny Tuppeny

如果考虑副作用，那么可能不行。例如，在浮点数中，我不确定 / 5 和 * 0.2 是否相同。0.2 无法由浮点数表示（在基数2中是周期性的），因此您已将错误从“操作后”移动到“操作前”。10000000000 / 5 是否与 10000000000 * 0.2 相同（其中 0.2 实际上是 1.99999999999999999...）？ - xanatos

值得指出的是，你提供的资源链接来自于1993年。如今，与你的回答所暗示的那样，“巨大”的差异已经远远不是这样了。 - Andrew Russell

在现代处理器（如SandyBridge、IvyBridge等）上，乘法仍然比除法少很多时钟周期（速度更快）。参见：https://dev59.com/JW855IYBdhLWcg3w0H93和https://dev59.com/a2jWa4cB1Zd3GeqPojkY以及其他更多相关链接。 - deegee

Answer 5

 while(start<=end)
    {
    int mid=(start+end)/2;
    if(mid*mid==A)
    return mid;
    if(mid*mid<A)
    {
    start=mid+1;
    ans=mid;
    }

如果我这样做，结果是求2147483647的平方根超时

但如果我按照以下方式操作，则很明显除法比乘法更快。

while(start<=end)
    {
    int mid=(start+end)/2;
    if(mid==A/mid)
    return mid;
    if(mid<A/mid)
    {
    start=mid+1;
    ans=mid;
    }
    else
    end=mid-1;
    }

- Parveen Kumar

---

“the outcome is the TIME LIMIT EXCEEDED” 是什么意思？你是指无限循环，还是指运行速度比预期慢了？ - Ignatius

计算所需的时间比使用除法描述的情况要长。@Taegyung - Parveen Kumar