3

我正在阅读其他网站上的一篇文章（计算机科学 - 可以证明最小可能效率吗？）关于假设最坏情况下的最小 Big-O 时间。

答案之一是解释比较二进制值（或类似值）所需的时间。

我对自己说：为什么不按位运算呢？

我用 Javascript 制作了这个模型代码：

console.time('^');
for(var i=0;i<1e5;i++)13^15;
console.timeEnd('^');

console.time('!=');
for(var i=0;i<1e5;i++)13!=15;
console.timeEnd('!=');

我真的很惊讶！

使用^(bitwise-xor) 的循环可以快 3毫秒！

这怎么可能？

为什么按位异或 ( ^) 比不等 ( !=) 比较快？

其他可能相关的信息：

我已经在 Windows 7 Home Premium x64 上运行的 Firefox 34.0.5 上进行了测试。

我还在 Opera 12.17(x64) 和 Chrome 39.0.2171.95 上尝试过这段代码，行为几乎相似，代码使用了^更快的 80% 的测试。

另一个惊喜：

在 php 中，运行这个：

$now=microtime(true);
for($i=0,$x=0;$i<1e6;$i++)$x+=13^15;
echo microtime(true)-$now,PHP_EOL;

$now=microtime(true);
for($i=0,$x=0;$i<1e6;$i++)$x+=13!=15;
echo microtime(true)-$now,PHP_EOL;

显示完全相同的效果：^比!=.
使用$x+=!13^15;而不是在$x+=13^15;70% 的时间内更快。

我已经在http://writecodeonline.com/php/上进行了测试，它在 linux x64 上运行 PHP 5.3。

此代码有来自用户 @AlexK. 的建议，在以下评论中：

13^15 是一个恒定的 noop，也许它只是被优化掉了（尝试一些有效的 x+=13^15;）

4

1 回答 1

1

你在叫错树。

例如，在 2GHz CPU 上，^ 或 != 可以在一纳秒左右执行。执行其中的 1e6 需要 1 毫秒，而不是 460 毫秒。这告诉我两件事：

  1. 这for需要大量时间，并且
  2. JavaScript 被解释为未编译。

请注意，口译员不一定要花时间进行优化。一个非常好的优化器会for($i=0,$x=0;$i<1e6;$i++)$x+=13^15;变成$x = 2000000. 它显然没有这样做。好吧，很难说它是否变成$x+=13^15了$x+=2.

让我们看另一件事。在机器级别，甚至在interperter级别$x+=13!=15比$x+=13^15. 两者都涉及$x+=，但是13^15是一个操作，而13!=15（在这种情况下！）是两个操作——首先比较 13 和 15!=以获得真，然后将真转换为 1。在硬件级别有很多方法可以做到这一点——大多数涉及跳跃，这是昂贵的。还有其他技术涉及多个布尔/移位/等指令，只是为了避免跳转。

或许13!=15比较慢。但是您不知道多少，因为 for 循环的开销很大。

无论如何，有关系吗？在某些情况下这两个操作可以互换吗？你没有比较(13^15)!=0哪个可能是等价的。

于 2015-04-07T05:52:03.043 回答