なぜfloor（）はそんなに遅いのですか？

https://stackoverflow.com/questions/824118

05-07-2019
|

質問

最近いくつかのコード（ISO / ANSI C）を書きましたが、達成したパフォーマンスの低さに驚きました。要するに、原因はfloor()関数であることが判明しました。遅いだけでなく、ベクトル化もしませんでした（Intelコンパイラー、別名ICL）。

2Dマトリックス内のすべてのセルに対してフロアを実行するためのベンチマークは次のとおりです。

VC:  0.10
ICL: 0.20

それを単純なキャストと比較します：

VC:  0.04
ICL: 0.04

どうすれば<=>を単純なキャストよりもずっと遅くすることができますか？！本質的に同じことを行います（負の数を除く）。 2番目の質問：誰かが超高速<=>実装を知っていますか？

PS：ベンチマークを行っていたループは次のとおりです。

void Floor(float *matA, int *intA, const int height, const int width, const int width_aligned)
{
    float *rowA=NULL;
    int   *intRowA=NULL;
    int   row, col;

    for(row=0 ; row<height ; ++row){
        rowA = matA + row*width_aligned;
        intRowA = intA + row*width_aligned;
#pragma ivdep
        for(col=0 ; col<width; ++col){
            /*intRowA[col] = floor(rowA[col]);*/
            intRowA[col] = (int)(rowA[col]);
        }
    }
}

解決

いくつかのことが床をキャストより遅くし、ベクトル化を防ぎます。

最も重要なもの：

floorはグローバル状態を変更できます。浮動小数点形式の整数として表現するには大きすぎる値を渡すと、 errno 変数が EDOM に設定されます。 NaNの特別な処理も行われます。この動作はすべて、オーバーフローのケースを検出し、何らかの形で状況を処理したいアプリケーション向けです（方法は問わないでください）。

これらの問題のある状態の検出は簡単ではなく、フロアの実行時間の90％以上を占めています。実際の丸めは安価で、インライン化/ベクトル化できます。また、大量のコードであるため、フロア関数全体をインライン化すると、プログラムの実行が遅くなります。

一部のコンパイラには、まれにしか使用されないc標準ルールを最適化するための特別なコンパイラフラグがあります。たとえば、 GCC は、errnoにまったく関心がないことを伝えることができます。そのためには、 -fno-math-errno または -ffast-math を渡します。 ICCとVCには、同様のコンパイラフラグがあります。

ところで-単純なキャストを使用して、独自のフロア関数をロールできます。否定的なケースと肯定的なケースを別々に処理する必要があります。オーバーフローとNaNの特別な処理が必要ない場合は、はるかに高速になる可能性があります。

他のヒント

floor()演算の結果をintに変換する場合、およびオーバーフローを心配しない場合、次のコードは(int)floor(x)よりもはるかに高速です。

inline int int_floor(double x)
{
  int i = (int)x; /* truncate */
  return i - ( i > x ); /* convert trunc to floor */
}

分岐のない床と天井（パイプラインをより有効に活用）エラーチェックなし

int f(double x)
{
    return (int) x - (x < (int) x); // as dgobbi above, needs less than for floor
}

int c(double x)
{
    return (int) x + (x > (int) x);
}

またはフロアを使用

int c(double x)
{
    return -(f(-x));
}

実際の最速の実装は、最新のx86 CPU上の大アレイです

MXCSR FPの丸めモードを-Infinity（別名floor）への丸めに変更します。 Cでは、これはfenv stuffまたは_mm_getcsr / _mm_setcsrで可能になります。
SIMDベクトルで_mm_cvtps_epi32を実行して配列をループし、現在の丸めモードを使用して4つのfloat sを32ビット整数に変換します。（そして、結果ベクトルを宛先に保存します。）

cvtps2dq xmm0, [rdi] は、IntelまたはAMD CPU上の単一のマイクロ融合uopです。 K10またはCore 2（ https://agner.org/optimize/ ）256ビットでも同じYMMベクトルを含むAVXバージョン。
MXCSRの元の値を使用して、現在の丸めモードを通常のIEEEデフォルトモードに復元します。（タイブレークとしても、最も近いラウンド）

これにより、切り捨てと同じ速さで、クロックサイクルごとに結果の1 SIMDベクトルをロード+変換+保存できます。（SSE2には、Cコンパイラで非常に一般的に必要とされるため、切り捨てのための特別なFP-<！> gt; int変換命令があります。x87の悪い昔では、(int)xでもx87丸めモードを切り捨てに変更してから cvttps2dqパックされたfloat-<！> gt; intで切り捨てあり（注ニーモニックの余分なt）または、XMMから整数レジスタに移動するスカラーの場合、 cvttss2si またはcvttsd2siはスカラーdoubleからスカラー整数へ。

ループの展開や適切な最適化を行うことで、フロントエンドでボトルネックが発生することなく、キャッシュミスのボトルネックがないことを前提に、1クロックあたり1ストアのスループットで可能になります。（また、Skylakeより前のIntelでは、1クロックあたり1パック変換スループットのボトルネックも発生していました。）すなわち、 SSE2、AVX、またはAVX512を使用して、サイクルごとに16、32、または64バイト。

現在の丸めモードを変更せずに、選択した丸めモードを使用してroundpsを最も近い整数-fno-math-errnoに丸めるには、SSE4.1 -marchが必要です。または、他の回答のトリックショーのいずれかを使用して、符号付き32ビット整数に収まるほど小さい大きさのフロートで動作することができます。それはいずれにしても最終的な宛先形式です）

（-msse4などの正しいコンパイラオプション、および右側のroundsd xmm1, xmm0, 1またはroundsdオプションを使用すると、コンパイラは-march=haswellまたは同等のスカラーおよび/または倍精度を使用して<=>をインライン化できます。 <=>が、これには2 uopがかかり、スカラーまたはベクトルのHaswellで2クロックあたり1スループットがあります。実際、gcc8.2は、高速演算オプション Godboltコンパイラエクスプローラーで確認できます。しかし、それは<=>にあります。残念ながらx86-64のベースラインではないため、マシンがサポートしている場合は有効にする必要があります。

はい、floor()はIEEE fp仕様から多くの動作を実装する必要があるため、すべてのプラットフォームで非常に低速です。内側のループで実際に使用することはできません。

私は時々マクロを使用してfloor（）を概算します：

#define PSEUDO_FLOOR( V ) ((V) >= 0 ? (int)(V) : (int)((V) - 1))

floor(-1) == -1とまったく同じように動作しません。たとえば、PSEUDO_FLOOR(-1) == -2が<=>ですが、ほとんどの用途には十分近いです。

浮動小数点ドメインと整数ドメイン間の単一の変換を必要とする実際のブランチレスバージョンは、値xをすべて正またはすべて負の範囲にシフトしてから、キャスト/トランケートして、シフトします。

long fast_floor(double x)
{
    const unsigned long offset = ~(ULONG_MAX >> 1);
    return (long)((unsigned long)(x + offset) - offset);
}

long fast_ceil(double x) {
    const unsigned long offset = ~(ULONG_MAX >> 1);
    return (long)((unsigned long)(x - offset) + offset );
}

コメントで指摘されているように、この実装はオーバーフローしない一時的な値x +- offsetに依存しています。

64ビットプラットフォームでは、int64_t中間値を使用する元のコードは3つの命令カーネルになります。これはint32_tの範囲の下限/下限に使用でき、|x| < 0x40000000-

inline int floor_x64(double x) {
   return (int)((int64_t)(x + 0x80000000UL) - 0x80000000LL);
}
inline int floor_x86_reduced_range(double x) {
   return (int)(x + 0x40000000) - 0x40000000;
}

彼らは同じことをしません。 floor（）は関数です。したがって、これを使用すると、関数呼び出し、スタックフレームの割り当て、パラメータのコピー、結果の取得が発生します。キャストは関数呼び出しではないため、より高速なメカニズムを使用します（値を処理するためにレジスタを使用する可能性があると思います）。
おそらくfloor（）はすでに最適化されています。
アルゴリズムのパフォーマンスをさらに高めることができますか？行と列の切り替えが役立つかもしれませんか？共通の値をキャッシュできますか？コンパイラのすべての最適化は有効ですか？オペレーティングシステムを切り替えることはできますか？コンパイラ？ Jon BentleyのProgramming Pearls には、可能な最適化の素晴らしいレビューがあります。

高速二重ラウンド

double round(double x)
{
    return double((x>=0.5)?(int(x)+1):int(x));
}

端末ログ

test_1_1 8.3837

native_1 18.4989をテスト

テストcustom_2 8.36333

テストnative_2 18.5001

test custom_3 8.37316

テストnative_3 18.5012

テスト

void test(char* name, double (*f)(double))
{
    int it = std::numeric_limits<int>::max();

    clock_t begin = clock();

    for(int i=0; i<it; i++)
    {
        f(double(i)/1000.0);
    }
    clock_t end = clock();

    cout << "test " << name << " " << double(end - begin) / CLOCKS_PER_SEC << endl;

}

int main(int argc, char **argv)
{

    test("custom_1",round);
    test("native_1",std::round);
    test("custom_2",round);
    test("native_2",std::round);
    test("custom_3",round);
    test("native_3",std::round);
    return 0;
}

結果

型キャストと脳の使用は、ネイティブ関数を使用するよりも最大3倍高速です。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow