6

我正在编写一个 2D 曲线算法，并且有一些代码可以有效地进行求和：

for (i=0, end=...; i<end; i++) {
  value += coefficients[i] * expensiveToCalculateValue(i);
}

其中coefficients[i]某些迭代步骤的值为零。由于零倍的东西仍然是零（至少在简单的算术规则下），我想我可以通过首先检查是否coefficients[i]为零来显着优化这段代码，如果是，就continue到下一次迭代。添加，排序，工作出色。

但这留下了一个问题：为什么不为我这样做？这不是乘法的一些创造性的利基版本，它是简单的算术。几乎所有语言都会短路二进制 OR 和 AND 运算，如果找到一个操作数会使结果从那时起保持不变，那么为什么算术乘以零不会同样短路呢？

我尝试在 Java、PHP、JavaScript、Perl、Python、C++ 中运行这段代码（修改为 synax），甚至看看 Prolog 做了什么，但他们都没有意识到，一旦他们看到“零次......”他们不必评估可能昂贵的第二（或第三、第四等）术语：

printed = 0;
function veryExpensive() {
  print "oh god this costs so much, x" + (printed++);
  return 0;
}
value = 0 * veryExpensive() * veryExpensive() * veryExpensive()

所有这些最终都运行veryExpensive()了三遍。

现在，我知道你可以- 如果你是那种人 - 编写你的veryExpensive函数来执行管理开销工作，基于这样一个事实，你可以依赖它被执行，尽管它的结果对算术表达式没有贡献（如果你这样做那，你可能在滥用一种语言，但每个人在他们的编程生涯中的某个时候都喜欢偷偷摸摸的忍者代码），但你这样做只是因为你知道这种语言碰巧碰巧没有针对这种情况进行优化。如果该语言为您优化了算术评估，那么您的代码表达能力就不会完全受到阻碍。

那么：是否有一些历史先例导致大量当前使用的语言针对“true OR ...”和“false AND ...”而不是“zero TIMES ...”进行优化？为什么我们要优化二元运算，而不是 MUL 0？（如果我们幸运的话，有人有一个迷人的故事来讲述为什么我们现在不短路）

更新

John Skeet 和 Nik Bougalis 都给出了很好的论据，说明为什么用现存的语言优化它会导致问题，但 Nik 的答案与问题更吻合，所以我将他的答案标记为“正确”的答案。也就是说，它们涵盖了同一问题的不同方面，因此真正的答案是两者的结合。

4

2 回答 2

9

所有这些最终都运行了 veryExpensive() 三次。

他们应该这样做。

但是您这样做只是因为您知道该语言恰好没有针对这种情况进行优化。

不，这不是“有趣”不优化的问题。这是一个不违反语言规范的优化问题。

如果语言指定操作X * Y首先评估X然后评估，然后将两个值相乘，那么如果 的值恰好为 0 ，则Y删除评估只是一个不正确的优化。YX

当然，经常有这样的操作符——尤其是（在类 C 语言中）：

  • 条件运算符，a ? b : c仅计算或 b c
  • x || y仅评估y是否x为假
  • x && y仅评估y是否x为真

并且 C# 具有 null-coalescing 运算符x ?? y，它仅评估y是否x为 null。

乘法可以这样定义，但我怀疑：

  • 在大多数乘法运算中，条件执行的分支命中是不值得的。但是你会希望行为是明确定义的：要么是短路，要么不是；它不应该（IMO）未定义。
  • 它使语言的指定和使用都更加复杂。您可能想要一个“无条件乘法”操作，它总是评估两个操作数（就像x | y并且x & y是非短路的）。

基本上，我认为对于所有相关人员来说，增加额外的复杂性是不值得的。

于 2013-03-07T17:51:20.317 回答
2

让编译器自动添加运行时检查可能有意义，也可能没有意义。在您的特定情况下，检查可能确实提高了性能，但您的特定情况并不是判断优化的最终情况。

如果乘法非常昂贵并且微处理器没有对乘以零的内部优化，并且零乘法的结果被保证（例如0 * NaN != 0）为零，那么检查可能是有意义的。但这有很多and操作数，如您所知，您可以将and短路。

假设您有一个准随机分布的数字，以及零与非零数字的未知比率。根据比率、零和非零序列的运行长度以及处理器的分支预测算法，检查实际上可能会导致问题（即流水线停顿）。

您仍然认为编译器应该代表您插入这样的检查吗？

于 2013-03-07T17:57:22.180 回答