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） for x86は、両方のループに対して同じアセンブリを提供しました。オペレーターの強度低下ifは、両方が仕事を成し遂げるためにを使用したことを意味しandlました（これは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

2番目のループ：

.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

ビット単位のチェックは、単一のマシン命令（ "および...、0x01"）のみを取ります。それを打ち負かすのはかなり難しいです。

剰余を取ることによって実際にモジュロを計算するダムコンパイラがある場合、モジュロチェックは絶対に遅くなります（モジュロルーチンへのサブルーチン呼び出しを含む場合もあります！）。スマートコンパイラはモジュロ関数を認識しており、そのコードを直接生成します。適切な最適化があれば、「modulo（x、2）」は上記と同じANDトリックで実装できることがわかります。

私たちのPARLANSEコンパイラは当然のことながらこれを行います。広く利用可能なCおよびC++コンパイラもこれを行わないのであれば、私は驚きます。

このような「優れた」コンパイラでは、奇数/偶数（または「2の累乗」）のチェックをどちらの方法で記述してもかまいません。それはかなり速いでしょう。

于 2012-07-19T17:12:18.670 に答える
2

ほとんどのコンパイラは、次の両方をコンパイルして、まったく同じマシン命令にします。

if( ( i % 2 ) == 0 )

if( ( i & 1 ) == 0 )

...「最適化」がオンになっていない場合でも。その理由は、定数値を使用してMODとANDを実行しているためです。また、％2操作は、プログラマーの作成者なら誰でも知っているはずですが、機能的には＆1操作と同等です。実際、2の累乗によるMODには、同等のAND演算があります。本当に違いをテストしたい場合は、両方の操作の右側を可変にする必要があります。コンパイラの巧妙さが作業を妨げないようにするには、変数を埋める必要があります。 'コンパイラがその時点で実行時の値が何であるかを判断できない場所での初期化。つまり、値をパラメーターとしてGLOBALLY-DECLARED（つまり、「静的」ではない）テスト関数に渡す必要があります。この場合、コンパイラーはそれらの定義にさかのぼることができません。理論的には、外部の呼び出し元がこれらのパラメーターに任意の値を渡すことができるため、変数を定数に置き換えます。または、コードをmain（）に残して変数をグローバルに定義することもできます。その場合、別の関数がグローバル変数の値を変更した可能性があることを確実に知ることができないため、コンパイラはそれらを定数に置き換えることができません。

ちなみに、これと同じ問題が除算演算にも存在します。一定の2乗による除算は、同等の右シフト（>>）演算に置き換えることができます。同じトリックが乗算（<<）でも機能しますが、乗算の利点は少なくなります（または存在しません）。真の除算演算はハードウェアで長い時間がかかりますが、ほとんどの最新のプロセッサでは15年前と比べて大幅な改善が行われていますが、除算演算には80クロックサイクルかかりますが、>>演算には1サイクルしかかかりません。最新のプロセッサでビット単位のトリックを使用しても「桁違い」の改善は見られませんが、顕著な改善がまだあるため、ほとんどのコンパイラは引き続きこれらのトリックを使用します。

編集：一部の組み込みプロセッサ（および、v8より前の元のSparcデスクトップ/ワークステーションプロセッサバージョンでは信じられないほど）では、除算命令すらありません。このようなプロセッサでのすべての真の除算およびmod演算は、完全にソフトウェアで実行する必要があり、これは非常にコストのかかる演算になる可能性があります。そのような環境では、確かに桁違いの違いが見られます。

于 2012-07-19T17:26:02.203 に答える