0

私はgcc 4.6.3を使用しており、ランダムショートの大きな配列を作成しています。私は次のステートメントでそれらを生成しています:

val = SHRT_MAX; //as defined by limits.h
while(array<end) {
    *array++ = rand() % val;
}

これは非常に高速な操作であり、5,000,000 要素もの大きな配列の場合でも、ほぼ瞬時に完了します。数値の変動が小さい場合のソート効率に興味があり、それを次のように変更しました。

val = 3;

これにより、かなりの速度差が生じ、元のステートメントよりもはるかに遅くなりました。このような大きな速度差を引き起こしているのは何ですか?

4

3 に答える 3

3

SHRT_MAXは より大きいか等しい可能性が高いRAND_MAXです。ステートメント:

*array++ = rand() % val;

次のように最適化できます。

int rand_value= rand();
if (rand_value==RAND_MAX) rand_value= 0;
*array++= rand_value;

モジュラスをブランチに置き換えるため、これは高速です。3である 2 番目のバージョンは、valモジュラスなしで実行される単純なバージョンに最適化することはできません。

% SHRT_MAXビット演算に単純化することはできません。しかし、 がどのように指定されているかという知識と組み合わせることで、コンパイラはと 以上の値rand()を扱うステートメントを確実に最適化できます。rand()RAND_MAX

于 2013-01-24T23:04:05.960 に答える
2

コンパイラは、モジュロ (a%B) の計算を最適化できます。ここで、B は定数です。実際のモジュロをより単純な算術演算に置き換えます。詳細は、 C でモジュラスを計算するための最も最適化された方法などのトピックで説明されています。ただし、このような最適化は、B の値によっては他の値よりも高速です。

CPU除算/モジュロ命令でさえ、異なる数のサイクルを完了することができます（少なくとも一部のCPUでは）。ここで x86 の数値を参照してください: http://gmplib.org/~tege/x86-timing.pdf。

于 2013-01-24T22:52:48.940 に答える
0

SHRT_MAX は2^n-1除算用に最適化できる値です。2^n-13 で割るのはかなり難しいので、コンパイラは 3 で割ることを決定するかもしれません (または、バリアントよりも遅い他の魔法の演算を行うこともできます。

使用できる最速のモジュロは for です2^n。これは、単一の and-instructiton に置き換えることができます。正の値の場合:x % 256は と同じx & 255です。残念ながら、値が負になる可能性がある場合は、それほど簡単ではありません...

于 2013-01-25T00:12:41.597 に答える