8

我最近一直在为我正在从事的研究项目编写一些代码，其中效率非常重要。我一直在考虑删除一些我做事的常规方法，并改用按位异或。我想知道的是，这是否会有所不同（如果我正在执行此操作说几百万次），或者在我在 g++ 中使用 03 之后是否相同。

想到的两个例子：

我有一个实例（我正在使用纯正整数）如果 n 是奇数，我需要将 n 更改为 n-1 ，如果 n 是偶数，我需要将 n 更改为 (n+1) 。我想我有几个选择：

if(n%2) // or (n%2==0) and flip the order
    n=n-1
else
    n=n+1

或者

n=n+2*n%2-1; //This of course was silly, but was the only non-bitwise 1 line I could come up with

最后：

n=n^1;

所有方法显然都做同样的事情，但我的感觉是第三种方法是最有效的。

下一个例子是一个更一般的注释。假设我正在比较两个正整数，其中一个会比其他的表现更好。或者即使我执行此操作数百万次，差异是否真的不明显：

if(n_1==n_2)
if(! (n_1 ^ n_2) )
if( n_1 ^ n_2) else \do work here

编译器会在所有这些实例中执行相同的操作吗？我只是好奇是否存在我应该使用按位运算而不相信编译器为我完成工作的实例。

修正：在正确的问题陈述中。

4

8 回答 8

9

检查很容易，只需启动反汇编程序即可。看一看：

fc：

unsigned int f1(unsigned int n)
{
  n ^= 1;  
  return n;
}

unsigned int f2(unsigned int n)
{
  if (n % 2)
    n=n-1;
  else
    n=n+1;

  return n;
}

构建和拆卸：

$ cc -O3 -c f.c 
$ otool -tV f.o 
f.o:
(__TEXT,__text) section
_f1:
00  pushq   %rbp
01  movq    %rsp,%rbp
04  xorl    $0x01,%edi
07  movl    %edi,%eax
09  leave
0a  ret
0b  nopl    _f1(%rax,%rax)
_f2:
10  pushq   %rbp
11  movq    %rsp,%rbp
14  leal    0xff(%rdi),%eax
17  leal    0x01(%rdi),%edx
1a  andl    $0x01,%edi
1d  cmovel  %edx,%eax
20  leave
21  ret

它看起来f1()有点短，实际上是否重要取决于一些基准测试。

于 2010-02-22T01:45:46.230 回答
4

如果 n 是偶数，我需要将 n 更改为 n-1，如果 n 是奇数，我需要将 n 更改为 (n+1)。

那样的话，不管效率如何，n = n ^ 1都是错误的。

对于您的第二种情况，==将与其他任何一种情况一样有效（如果不是更高的话）。

一般来说，在优化方面，您应该自己进行基准测试。如果潜在的优化不值得进行基准测试，那么它就不值得进行。

于 2010-02-22T01:34:31.120 回答
4

我有点不同意这里的大多数答案，这就是为什么我仍然看到自己在回答 2010 年的问题 :-)

XOR 实际上是 CPU 可以做的最快的操作，好的部分是所有 CPU 都支持它。这样做的原因很简单：一个 XOR 门可以只用 4 个 NAND 门或 5 个 NOR 门创建——这意味着使用硅结构很容易创建。毫不奇怪，我所知道的所有 CPU 都可以在 1 个时钟周期（甚至更少）内执行您的 XOR 操作。

如果您需要对数组中的多个项目进行 XOR，现代 x64 CPU 还支持一次对多个项目进行 XOR，例如 f.ex。英特尔上的 SIMD 指令。

您选择的替代解决方案使用 if-then-else。诚然，大多数编译器都能够解决这个简单的问题……但是为什么要冒险呢？结果是什么？

编译器没有弄清楚的后果是分支预测错误。单个分支预测失败将很容易花费 17 个时钟节拍。如果您看一看处理器指令的执行速度，您会发现分支对您的性能非常不利，尤其是在处理随机数据时。

请注意，这也意味着如果您不正确地构建测试，数据会弄乱您的性能测量。

所以总结一下：首先思考，然后编程，然后配置文件——而不是相反。并使用异或。

于 2013-12-16T14:19:55.657 回答
2

关于确定的唯一方法是测试。我不得不同意，需要一个相当聪明的编译器才能产生尽可能高效的输出：

if(n%2) // or (n%2==0) and flip the order
    n=n-1
else
    n=n+1

可以n ^= 1;，但我最近没有检查任何类似的东西，可以肯定地说。

至于你的第二个问题，我怀疑它有什么不同——对于这些方法中的任何一种，平等比较都会很快结束。如果你想要速度，主要要做的是避免涉及到一个分支——例如：

if (a == b)
    c += d;

可以写成： c += d * (a==b);. 查看汇编语言，第二个通常看起来有点混乱（很难将比较结果从标志获取到普通寄存器），但通过避免任何分支仍然通常表现更好。

编辑：至少我方便的编译器（gcc & MSVC ）不会cmov为. 我将代码扩展为可测试的东西。ifsete* (a==b)

Edit2：由于 Potatoswatter 提出了另一种使用按位而不是乘法的可能性，因此我决定与其他方法一起进行测试。这是添加的代码：

#include <time.h>
#include <iostream>
#include <stdlib.h>

int addif1(int a, int b, int c, int d) { 
    if (a==b) 
        c+=d;
    return c;
}

int addif2(int a, int b, int c, int d) {
    return c += d * (a == b);
}

int addif3(int a, int b, int c, int d) {
    return c += d & -(a == b);
}

int main() {
    const int iterations = 50000;
    int x = rand();
    unsigned tot1 = 0;
    unsigned tot2 = 0;
    unsigned tot3 = 0;

    clock_t start1 = clock();
    for (int i=0; i<iterations; i++) {
        for (int j=0; j<iterations; j++) 
            tot1 +=addif1(i, j, i, x);
    }
    clock_t stop1 = clock();

    clock_t start2 = clock();
    for (int i=0; i<iterations; i++) {
        for (int j=0; j<iterations; j++) 
            tot2 +=addif2(i, j, i, x);
    }
    clock_t stop2 = clock();

    clock_t start3 = clock();
    for (int i=0; i<iterations; i++) {
        for (int j=0; j<iterations; j++) 
            tot3 +=addif3(i, j, i, x);
    }
    clock_t stop3 = clock();

    std::cout << "Ignore: " << tot1 << "\n";
    std::cout << "Ignore: " << tot2 << "\n";
    std::cout << "Ignore: " << tot3 << "\n";

    std::cout << "addif1: " << stop1-start1 << "\n";
    std::cout << "addif2: " << stop2-start2 << "\n";
    std::cout << "addif3: " << stop3-start3 << "\n";    
    return 0;
}

现在真正有趣的部分是：第三版的结果非常有趣。对于 MS VC++，我们大致得到了我们大多数人可能期望的：

Ignore: 2682925904
Ignore: 2682925904
Ignore: 2682925904
addif1: 4814
addif2: 3504
addif3: 3021

使用 the&代替*, 会带来明显的改进——几乎和*give over一样多if。使用 gcc 的结果却有很大不同：

Ignore: 2680875904
Ignore: 2680875904
Ignore: 2680875904
addif1: 2901
addif2: 2886
addif3: 7675

在这种情况下，代码 usingif的速度更接近于代码 using 的速度*，但代码 using比&任何一个都慢——慢得多！万一有人在乎，我发现这很令人惊讶，以至于我用不同的标志重新编译了几次，每次都重新运行了几次，依此类推，结果完全一致——使用的代码始终慢得多.&

使用 gcc 编译的第三版代码的糟糕结果让我们回到了我所说的开头 [并结束此编辑]：

正如我一开始所说的那样，“确定的唯一方法是测试”——但至少在这个有限的测试中，乘法始终优于if. 可能存在编译器、编译器标志、CPU、数据模式、迭代计数等的某种if组合，这有利于乘法 - 毫无疑问，差异足够小，以至于另一个方向的测试是完全可信的。尽管如此，我相信这是一种值得了解的技术。对于主流编译器和 CPU，它似乎相当有效（尽管它对 MSVC 肯定比对 gcc更有帮助）。

[edit2 的恢复：] 使用 gcc 的结果&展示了 1）微优化可以/是编译器特定的程度，以及 2）现实生活中的结果与预期有多大不同。

于 2010-02-22T01:46:56.677 回答
1

n^=1比 快吗if ( n%2 ) --n; else ++n;？是的。我不希望编译器对此进行优化。由于按位运算要简洁得多，因此熟悉 XOR 并在该行代码上添加注释可能是值得的。

如果它对你的程序的功能真的很重要，那么它也可能被认为是一个可移植性问题：如果你在你的编译器上进行测试并且速度很快，那么在尝试另一个编译器时你可能会感到惊讶。通常这不是代数优化的问题。

x^y比 快吗x==y？不行。迂回做事一般都不好。

于 2010-02-22T01:52:23.610 回答
0

一个好的编译器会优化n%2，但你总是可以检查生成的程序集来查看。如果您看到分水岭，请自己开始优化它，因为分水器的速度几乎一样慢。

于 2010-02-22T01:37:42.587 回答
0

你应该相信你的编译器。gcc/++ 是多年开发的产物，它能够进行您可能正在考虑进行的任何优化。而且，如果您开始玩弄，您很可能会篡改它优化代码的努力。

于 2010-02-22T01:45:06.870 回答
0

n ^= 1并且n1==n2可能是您能做的最好的，但实际上，如果您追求最大效率，请不要盯着代码寻找类似的小东西。

这是一个如何真正调整性能的示例。

在抽样证明它们是您应该关注的地方之前，不要指望低级优化有很大帮助。

于 2010-02-22T16:07:25.927 回答