30

私がプロファイリングしているアプリでは、一部のシナリオでは、この関数が合計実行時間の10％以上を占める可能性があることがわかりました。

卑劣な浮動小数点トリックを使用したより高速なsqrt実装の長年にわたる議論を見てきましたが、そのようなものが最新のCPUで時代遅れであるかどうかはわかりません。

参考までに、MSVC ++ 2008コンパイラが使用されています...ただし、sqrtはそれほどオーバーヘッドを追加しないと思います。

modf関数に関する同様の説明については、こちらも参照してください。

編集：参考までに、これは広く使用されている方法の1つですが、実際にははるかに高速ですか？とにかく最近SQRTは何サイクルですか？

4

6 に答える 6

34

はい、トリックがなくても可能です。

  1. 速度のために精度を犠牲にします。sqrt アルゴリズムは反復的であり、反復回数を減らして再実装します。

  2. ルックアップ テーブル: 反復の開始点のためだけに、または補間と組み合わせてそこにたどり着きます。

  3. キャッシング: 常に同じ限られた値のセットを計算していますか? その場合、キャッシングはうまく機能します。これは、同じサイズの多数の図形に対して同じことが計算されるグラフィックス アプリケーションで役立つことがわかったので、結果を便利にキャッシュできます。

11年後からこんにちは。

これがまだときどき投票されることを考慮して、パフォーマンスについてのメモを追加すると思いました。パフォーマンスは、メモリ アクセスによってさらに劇的に制限されています。このようなものを最適化するときは、現実的なベンチマーク (理想的にはアプリケーション全体) を絶対に使用する必要があります。アプリケーションのメモリ アクセス パターンは、ルックアップ テーブルやキャッシュなどのソリューションに劇的な影響を与え、最適化されたバージョンの「サイクル」を比較するだけです。プログラム時間を個々の命令に割り当てることも非常に難しく、プロファイリング ツールがここで誤解を招く可能性があります。

  1. 関連する注意事項として、ユースケースに適している場合は、_mm512_sqrt_psなどの平方根を計算するための simd/ベクトル化された命令の使用を検討してください。

  2. インテルの最適化リファレンス マニュアルのセクション 15.12.3 を参照してください。これには、ベクトル化された命令を使用した近似方法が記載されています。これは、おそらく他のアーキテクチャにもうまく変換されるでしょう。

于 2010-04-14T13:42:49.957 に答える
15

ここに優れた比較表があります: http://assemblyrequired.crashworks.org/timing-square-root/

簡単に言うと、SSE2 の ssqrts は FPU の fsqrt よりも約 2 倍高速であり、近似と反復はそれよりも約 4 倍高速です (全体で 8 倍)。

また、単精度の sqrt を取得しようとしている場合は、それが実際に得られるものであることを確認してください。float 引数を double に変換し、倍精度 sqrt を呼び出してから float に戻すコンパイラが少なくとも 1 つあると聞いたことがあります。

于 2010-04-14T15:29:09.040 に答える
8

実装を変更するよりも、アルゴリズムを変更することで、より多くの速度を改善できる可能性が非常に高くなります。呼び出しを高速化する代わりに、呼び出し回数を減らすようにしてください。(そして、これが不可能だと思われる場合 -あなたが言及する改善点は、平方根の計算に使用されるアルゴリズムの改善だけです。)sqrt()sqrt()

これは非常に頻繁に使用されるため、標準ライブラリの の実装はsqrt()、一般的な場合にほぼ最適である可能性があります。アルゴリズムがいくつかのショートカットを取ることができる制限されたドメイン (たとえば、精度を下げる必要がある場合) を持っていない限り、誰かがより高速な実装を考え出す可能性はほとんどありません。

その関数は実行時間の 10% を使用するため、 の時間の 75% しかかからない実装を思いついたとしても、実行時間は2.5%std::sqrt()しか短縮されないことに注意してください。ほとんどのアプリケーションでは、時計を使用して測定する場合を除いて、ユーザーはこれに気付くことさえありません。

于 2010-04-14T13:32:16.757 に答える
3

どのくらい正確である必要がありますsqrtか? 妥当な概算を非常に迅速に得ることができます。インスピレーションについては、Quake3 の優れた逆平方根関数を参照してください (コードは GPL に準拠しているため、直接統合したくない場合があることに注意してください)。

于 2010-04-14T13:44:00.050 に答える
2

これを修正したかどうかはわかりませんが、以前に読んだことがありますsqrt。関数をインライン アセンブリ バージョンに置き換えるのが最も速いようです。

ここで多くの選択肢の説明を見ることができます。

最高の魔法のスニペットです：

double inline __declspec (naked) __fastcall sqrt(double n)
{
    _asm fld qword ptr [esp+4]
    _asm fsqrt
    _asm ret 8
}

sqrt同じ精度の標準呼び出しよりも約 4.7 倍高速です。

于 2013-11-23T16:37:20.873 に答える
1

これは、わずか 8KB のルックアップ テーブルを使用した高速な方法です。間違いは結果の ~0.5% です。表は簡単に拡大できるので、間違いを減らすことができます。通常の sqrt() よりも約 5 倍高速に実行されます

// LUT for fast sqrt of floats. Table will be consist of 2 parts, half for sqrt(X) and half for sqrt(2X).
const int nBitsForSQRTprecision = 11;                       // Use only 11 most sagnificant bits from the 23 of float. We can use 15 bits instead. It will produce less error but take more place in a memory. 
const int nUnusedBits   = 23 - nBitsForSQRTprecision;       // Amount of bits we will disregard
const int tableSize     = (1 << (nBitsForSQRTprecision+1)); // 2^nBits*2 because we have 2 halves of the table.
static short sqrtTab[tableSize]; 
static unsigned char is_sqrttab_initialized = FALSE;        // Once initialized will be true

// Table of precalculated sqrt() for future fast calculation. Approximates the exact with an error of about 0.5%
// Note: To access the bits of a float in C quickly we must misuse pointers.
// More info in: http://en.wikipedia.org/wiki/Single_precision
void build_fsqrt_table(void){
    unsigned short i;
    float f;
    UINT32 *fi = (UINT32*)&f;

    if (is_sqrttab_initialized)
        return;

    const int halfTableSize = (tableSize>>1);
    for (i=0; i < halfTableSize; i++){
         *fi = 0;
         *fi = (i << nUnusedBits) | (127 << 23); // Build a float with the bit pattern i as mantissa, and an exponent of 0, stored as 127

         // Take the square root then strip the first 'nBitsForSQRTprecision' bits of the mantissa into the table
         f = sqrtf(f);
         sqrtTab[i] = (short)((*fi & 0x7fffff) >> nUnusedBits);

         // Repeat the process, this time with an exponent of 1, stored as 128
         *fi = 0;
         *fi = (i << nUnusedBits) | (128 << 23);
         f = sqrtf(f);
         sqrtTab[i+halfTableSize] = (short)((*fi & 0x7fffff) >> nUnusedBits);
    }
    is_sqrttab_initialized = TRUE;
}

// Calculation of a square root. Divide the exponent of float by 2 and sqrt() its mantissa using the precalculated table.
float fast_float_sqrt(float n){
    if (n <= 0.f) 
        return 0.f;                           // On 0 or negative return 0.
    UINT32 *num = (UINT32*)&n;
    short e;                                  // Exponent
    e = (*num >> 23) - 127;                   // In 'float' the exponent is stored with 127 added.
    *num &= 0x7fffff;                         // leave only the mantissa 

    // If the exponent is odd so we have to look it up in the second half of the lookup table, so we set the high bit.
    const int halfTableSize = (tableSize>>1);
    const int secondHalphTableIdBit = halfTableSize << nUnusedBits;
    if (e & 0x01) 
        *num |= secondHalphTableIdBit;  
    e >>= 1;                                  // Divide the exponent by two (note that in C the shift operators are sign preserving for signed operands

    // Do the table lookup, based on the quaternary mantissa, then reconstruct the result back into a float
    *num = ((sqrtTab[*num >> nUnusedBits]) << nUnusedBits) | ((e + 127) << 23);
    return n;
}
于 2015-11-11T18:12:21.727 に答える