5

所以，只是为了好玩，出于好奇，我想看看在进行奇偶校验、模数或按位比较时执行得更快。

所以，我整理了以下内容，但我不确定它的行为是否正确，因为差异是如此之小。我在网上某处读到按位应该比模数检查快一个数量级。

它有可能被优化掉吗？我刚刚开始修补程序集，否则我会尝试对可执行文件进行一些剖析。

编辑3：这是一个工作测试，在很大程度上感谢@phonetagger：

#include <stdio.h>
#include <time.h>
#include <stdint.h>

// to reset the global
static const int SEED = 0x2A;

// 5B iterations, each
static const int64_t LOOPS = 5000000000;

int64_t globalVar;

// gotta call something
int64_t doSomething( int64_t input )
{
  return 1 + input;
}

int main(int argc, char *argv[]) 
{
  globalVar = SEED;

  // mod  
  clock_t startMod = clock();

  for( int64_t i=0; i<LOOPS; ++i )
  {    
    if( ( i % globalVar ) == 0 )
    {
      globalVar = doSomething(globalVar);      
    }    
  }

  clock_t endMod = clock();

  double modTime = (double)(endMod - startMod) / CLOCKS_PER_SEC;

  globalVar = SEED;

  // bit
  clock_t startBit = clock();

  for( int64_t j=0; j<LOOPS; ++j )
  {
    if( ( j & globalVar ) == 0 )
    {
      globalVar = doSomething(globalVar);
    }       
  }

  clock_t endBit = clock();

  double bitTime = (double)(endBit - startBit) / CLOCKS_PER_SEC;

  printf("Mod: %lf\n", modTime);
  printf("Bit: %lf\n", bitTime);  
  printf("Dif: %lf\n", ( modTime > bitTime ? modTime-bitTime : bitTime-modTime ));
}

每个循环进行 50 亿次迭代，全局删除编译器优化产生以下结果：

Mod: 93.099101
Bit: 16.701401
Dif: 76.397700
4

3 回答 3

3

gcc foo.c -std=c99 -S -O0 （注意，我特意这样做了-O0） x86为两个循环提供了相同的程序集。运算符强度降低意味着两个ifs 都使用 anandl来完成工作（这比 Intel 机器上的模快）：

第一个循环：

.L6:
        movl    72(%esp), %eax
        andl    $1, %eax
        testl   %eax, %eax
        jne     .L5
        call    doNothing
.L5:
        addl    $1, 72(%esp)
.L4:
        movl    LOOPS, %eax
        cmpl    %eax, 72(%esp)
        jl      .L6

第二循环：

.L9:
        movl    76(%esp), %eax
        andl    $1, %eax
        testl   %eax, %eax
        jne     .L8
        call    doNothing
.L8:
        addl    $1, 76(%esp)
.L7:
        movl    LOOPS, %eax
        cmpl    %eax, 76(%esp)
        jl      .L9

您看到的微小差异可能是由于clock.

于 2012-07-19T17:22:53.470 回答
2

按位检查只需要一条机器指令（“and ...,0x01”）；这很难被击败。

如果您有一个愚蠢的编译器，它实际上通过取余数来计算模数（有时包括对模数例程的子例程调用！），模数检查绝对会更慢。智能编译器知道模函数并直接为它生成代码；如果他们有任何不错的优化，他们就会知道“模（x，2）”可以用上面相同的 AND 技巧来实现。

我们的PARLANSE编译器理所当然地做到了这一点。如果广泛使用的 C 和 C++ 编译器也不这样做，我会感到惊讶。

使用这样的“好”编译器，您编写奇数/偶数（或什至“是二的幂”）检查的方式并不重要；它会非常快。

于 2012-07-19T17:12:18.670 回答
2

大多数编译器会将以下两者编译为完全相同的机器指令：

if( ( i % 2 ) == 0 )

if( ( i & 1 ) == 0 )

...即使没有打开任何“优化”。原因是您正在对常量值进行 MOD-ing 和 AND-ing，并且 %2 操作，正如任何编译器编写者都应该知道的那样，在功能上等同于 &1 操作。事实上，任何 2 的幂的 MOD 都有一个等效的 AND 操作。如果你真的想测试差异，你需要让两个操作的右边都是可变的，并且为了绝对确保编译器的聪明不会阻碍你的努力，你需要隐藏变量' 在某个地方进行初始化，此时编译器无法判断它的运行时值是多少；即您需要将值作为参数传递给全局声明（即不是“静态”）测试函数，在这种情况下编译器无法追溯到它们的定义& 用常量替换变量，因为理论上任何外部调用者都可以为这些参数传递任何值。或者，您可以将代码留在 main() 中并全局定义变量，在这种情况下，编译器不能用常量替换它们，因为它不能确定另一个函数可能已经改变了全局变量的值。

Incidentally, this same issue exists for divide operations.... Divisions by constant powers-of-two can be substituted with an equivalent right-shift (>>) operation. The same trick works for multiplication (<<), but the benefits are less (or nonexistant) for multiplications. True division operations just take a long time in hardware, though significant improvements have been made in most modern processors vs. even 15 years ago, division operations still take maybe 80 clock cycles, while a >> operation takes only a single cycle. You're not going to see an "order of magnitude" improvement using bitwise tricks on modern processors, but most compilers will still use those tricks because there is still some noticeable improvement.

编辑：在一些嵌入式处理器上（尽管它是令人难以置信的，v8 之前的原始 Sparc 桌面/工作站处理器版本），甚至根本没有除法指令。此类处理器上的所有真正除法运算必须完全在软件中执行，这可能是一项极其昂贵的操作。在那种环境下，你肯定会看到一个数量级的差异。

于 2012-07-19T17:26:02.203 回答