2

数値の乗算または除算を行うときに、何が最速かを把握するためにいくつかの速度テストを行いました。オプティマイザーを倒すには、本当に一生懸命働かなければなりませんでした。大規模なループが 2 マイクロ秒で動作する、または乗算が除算と同じ速度であるなどの無意味な結果が得られました (それが本当なら)。

最終的にコンパイラの最適化を十分に無効にするのに十分な努力をした後、速度を最適化しながら、これらの速度の結果が得られました。彼らはおそらく他の誰かに興味がありますか？

私のテストにまだ欠陥がある場合は、お知らせください。ただし、このがらくたを書くのに2時間かかるだけなので、親切に見てください:P

64 time: 3826718 us
32 time: 2476484 us
D(mul) time: 936524 us
D(div) time: 3614857 us
S time: 1506020 us

double を使用した「乗算による除算」は、除算を行う最速の方法のようであり、次に整数除算が続きます。除算の精度はテストしていません。「適切な分割」の方が正確でしょうか？基数 10 の定数で整数除算を使用し、コンパイラにそれを最適化させるだけなので、これらの速度テストの結果を知りたいとは思いません;) (また、最適化を無効にすることもありません)。

結果を取得するために使用したコードは次のとおりです。

#include <iostream>

int Run(int bla, int div, int add, int minus) {
    // these parameters are to force the compiler to not be able to optimise away the
    // multiplications and divides :)
    long LoopMax = 100000000;

    uint32_t Origbla32 = 1000000000;
    long i = 0;

    uint32_t bla32 = Origbla32;
    uint32_t div32 = div;
    clock_t Time32 = clock();
    for (i = 0; i < LoopMax; i++) {
        div32 += add;
        div32 -= minus;
        bla32 = bla32 / div32;
        bla32 += bla;
        bla32 = bla32 * div32;
    }
    Time32 = clock() - Time32;

    uint64_t bla64 = bla32;
    clock_t Time64 = clock();
    uint64_t div64 = div;
    for (long i = 0; i < LoopMax; i++) {
        div64 += add;
        div64 -= minus;
        bla64 = bla64 / div64;
        bla64 += bla;
        bla64 = bla64 * div64;
    }
    Time64 = clock() - Time64;

    double blaDMul = Origbla32;
    double multodiv = 1.0 / (double)div;
    double multomul = div;
    clock_t TimeDMul = clock();
    for (i = 0; i < LoopMax; i++) {
        multodiv += add;
        multomul -= minus;
        blaDMul = blaDMul * multodiv;
        blaDMul += bla;
        blaDMul = blaDMul * multomul;
    }
    TimeDMul = clock() - TimeDMul;

    double blaDDiv = Origbla32;
    clock_t TimeDDiv = clock();
    for (i = 0; i < LoopMax; i++) {
        multodiv += add;
        multomul -= minus;
        blaDDiv = blaDDiv / multomul;
        blaDDiv += bla;
        blaDDiv = blaDDiv / multodiv;
    }
    TimeDDiv = clock() - TimeDDiv;

    float blaS = Origbla32;
    float divS = div;
    clock_t TimeS = clock();
    for (i = 0; i < LoopMax; i++) {
        divS += add;
        divS -= minus;
        blaS = blaS / divS;
        blaS += bla;
        blaS = blaS * divS;
    }
    TimeS = clock() - TimeS;

    printf("64 time: %i us  (%i)\n", (int)Time64, (int)bla64);
    printf("32 time: %i us  (%i)\n", (int)Time32, bla32);

    printf("D(mul) time: %i us  (%f)\n", (int)TimeDMul, blaDMul);
    printf("D(div) time: %i us  (%f)\n", (int)TimeDDiv, blaDDiv);
    printf("S time: %i us  (%f)\n", (int)TimeS, blaS);

    return 0;
}

int main(int argc, char* const argv[]) {
    Run(0, 10, 0, 0); // adds and minuses 0 so it doesn't affect the math, only kills the opts
    return 0;
}
4

5 に答える 5

11

特定の算術演算を実行する方法は多数あるため、答えが 1 つにならない場合があります (シフト、分数乗算、実際の除算、対数単位のラウンドトリップなど)。これらはすべて、オペランドと資源配分）。

コンパイラは、プログラムとデータ フロー情報を使用して処理を実行します。

x86 でのアセンブリに適用可能なデータについては、「AMD および Intel x86 プロセッサの命令レイテンシとスループット」を参照してください。

于 2009-11-17T22:02:10.243 に答える
4

何が最速かは、ターゲットアーキテクチャに完全に依存します。ここでは、たまたま使用しているプラ​​ットフォームにのみ関心があるようです。実行時間から推測すると、Intel（Core2？）またはAMDのいずれかの64ビットx86のようです。

とはいえ、逆数による浮動小数点の乗算は多くのプラットフォームで最速ですが、推測すると、通常は浮動小数点の除算よりも精度が低くなります（1つではなく2つの丸め-使用法に関係なく）別の質問です）。一般に、分割を可能な限り効率的にするために、フープをジャンプするよりも少ない分割を使用するようにアルゴリズムを再配置することをお勧めします（最速の分割は実行しない分割です）。除算のボトルネックとなるアルゴリズムはほとんどなく、その間にあるため、最適化に時間を費やします。

また、整数のソースがあり、整数の結果が必要な場合は、ベンチマークに整数と浮動小数点の間の変換のコストを含めるようにしてください。

特定のマシンでのタイミングに関心があるため、Intelがこの情報を最適化リファレンスマニュアル（pdf）で公開していることに注意してください。具体的には、付録Cのセクション3.1「レジスタオペランドのレイテンシとスループット」の表に関心があります。

整数除算のタイミングは、関係する実際の値に大きく依存することに注意してください。そのガイドの情報に基づくと、測定するパフォーマンス比がIntelの公開情報と一致しないため、タイミングルーチンにはまだかなりのオーバーヘッドがあるようです。

于 2009-11-17T22:09:55.793 に答える
2

Stephenが述べたように、最適化マニュアルを使用しますが、SSE命令の使用も検討する必要があります。これらは、1つの命令で4または8の除算/乗算を実行できます。

また、除算が処理するのに1クロックサイクルかかることはかなり一般的です。結果は数クロックサイクル（レイテンシーと呼ばれる）では利用できない場合がありますが、最初の結果を必要としない限り、次の分割はこの時間（最初の分割と重複）中に開始できます。これは、前の荷物がまだ乾燥している間にさらに衣類を洗うことができるのと同じように、CPUのパイプライニングによるものです。

乗算して除算するのは一般的なトリックであり、除数が頻繁に変更されない場合は常に使用する必要があります。

最終的な含意を制限するのは（入力をナビゲートして出力を書き込むときの）メモリアクセスの速度であることを発見するためだけに、計算を高速化するために時間と労力を費やす可能性が非常に高いです。

于 2009-11-17T22:41:50.780 に答える
0

私はMSVC2008でこれを行うための欠陥のあるテストを書きました

double i32Time  = GetTime();
{
    volatile __int32 i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 61;
        count++;
    }
}
i32Time = GetTime() - i32Time;

double i64Time  = GetTime();
{
    volatile __int64 i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 61;
        count++;
    }
}
i64Time = GetTime() - i64Time;


double fTime    = GetTime();
{
    volatile float i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 4.0f;
        count++;
    }
}
fTime   = GetTime() - fTime;

double fmTime   = GetTime();
{
    volatile float i = 4;
    const float div = 1.0f / 4.0f;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i *= div;
        count++;
    }
}
fmTime  = GetTime() - fmTime;

double dTime    = GetTime();
{
    volatile double i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 4.0f;
        count++;
    }
}
dTime   = GetTime() - dTime;

double dmTime   = GetTime();
{
    volatile double i = 4;
    const double div = 1.0f / 4.0f;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i *= div;
        count++;
    }
}
dmTime  = GetTime() - dmTime;


DebugOutput( _T( "%f\n" ), i32Time );
DebugOutput( _T( "%f\n" ), i64Time );
DebugOutput( _T( "%f\n" ), fTime );
DebugOutput( _T( "%f\n" ), fmTime );
DebugOutput( _T( "%f\n" ), dTime );
DebugOutput( _T( "%f\n" ), dmTime );

DebugBreak();

次に、32ビットモードのAMD64Turion64で実行しました。私が得た結果は次のとおりです。

0.006622
0.054654
0.006283
0.006353
0.006203
0.006161

テストに欠陥がある理由は、変数が変更された場合に備えて、コンパイラにメモリから変数を再ロードさせるvolatileの使用です。そのすべては、このマシンの実装の間に貴重な小さな違いがあることを示しています（__int64は明らかに遅いです）。

また、MSVCコンパイラが逆数最適化による乗算を実行することも明確に示しています。GCCは、良くはないにしても同じことをすると思います。フロートと二重除算のチェックを「i」で除算するように変更すると、時間が大幅に増加します。その多くはディスクからの再ロードである可能性がありますが、コンパイラがそれをそれほど簡単に最適化できないことは明らかです。

このようなマイクロ最適化を理解するには、このpdfを読んでみてください。

全体として、そのようなことを心配しているのであれば、明らかにコードのプロファイルを作成していないと思います。問題が実際に問題である場合は、問題のプロファイルを作成して修正します。

于 2009-11-17T23:02:17.473 に答える
0

Agner Fog は、かなり詳細な測定を自分で行っています。本当に何かを最適化しようとしているなら、彼のソフトウェア最適化リソースから残りのドキュメントも読むべきです。

ベクトル化されていない浮動小数点演算を測定している場合でも、コンパイラには、生成されたアセンブリに対して 2 つのオプションがあります。FPU 命令 ( fadd、fmul) を使用するか、1 つの浮動小数点値を操作しながら SSE 命令を使用できます。命令ごと ( addss、mulss)。私の経験では、SSE 命令の方が高速で不正確さが少ないですが、古い動作に依存するコードとの互換性を損なう可能性があるため、コンパイラはそれをデフォルトにしません。-mfpmath=sseフラグを使用して gcc で有効にすることができます。

于 2009-11-18T04:43:08.610 に答える