17

コードのホット パスでいくつかの整数除算を実行する必要があります。プロファイリングとサイクル カウントによって、整数除算のコストがかかっていることを既に確認しています。部門をより安価なものに減らすためにできることがあるといいのですが。

このパスでは、2^n+1 (n は変数) で割ります。基本的に、この関数を最適化して除算演算子を削除したいと考えています。

unsigned long compute(unsigned long a, unsigned int n)
{
    return a / ((1 << n) + 1);
}

2^n で除算する場合は、div を右シフト n に置き換えるだけです。定数で除算する場合、コンパイラの強度によってその特定の除算が削減され、おそらく乗算とシフトになります。

2^n+1 に適用される同様の最適化はありますか?

編集: a here は、任意の 64 ビット整数にすることができます。n は 10 から 25 までの数個の値しか取りません。確かに、各 n についていくつかの値を事前計算できますが、a についてはできません。

4

2 に答える 2

13

非常に多くの場所しかシフトできないintため、これらすべてのケースを、定数によるいくつかの分割のいずれかの選択に入れることができます。

unsigned long compute(unsigned long a, unsigned int n)
{
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader):
    switch (n) {
        case  0: return a / ((1 << 0) + 1);
        case  1: return a / ((1 << 1) + 1);
        case  2: return a / ((1 << 2) + 1);

            // cases 3 through 30...

        case 31: return a / ((1 << 31) + 1);
    }
}

したがって、各除算は定数によるものであり、コンパイラは通常、一連の乗算/シフト/加算命令に縮小します(質問が言及したように)。ac/c++ コンパイラは定数除算を 2 の累乗値でシフトに最適化しますか?を参照してください。詳細については。

于 2010-10-25T17:39:10.783 に答える
9

整数除算を定数で、乗算 (モジュロ ワードサイズ) でマジック ナンバーとシフトで置き換えることができます。

マジック ナンバーは、既知の定数に対して事前に計算できます。

n は 0..31 などの多くの値を取ることができないため、すべての n に対してこれらのマジック ナンバーを事前に計算し、32 要素のテーブルに格納するのは「簡単」です。

マジックナンバーを計算するJavascriptページ

優れたコンパイラは、マジック ナンバーを計算し、除数がコンパイル時に定数である場合、整数除算を乗算とシフトに置き換えることができます。残りのコードがパフォーマンス クリティカルなコードを中心にどのように構成されているかに応じて、マクロまたはインライン トリックを使用して n のすべての可能な値を展開し、コンパイラにマジック ナンバーを見つける作業を行わせることができます (スイッチの答えと同様)。 、しかし、定数領域により多くのコードを配置します。そうしないと、価値のないトレードオフになる可能性があります-分岐によりパフォーマンスが低下する可能性もあります)

詳細な説明とマジック ナンバーを計算するためのコードは、Henry S. Warren, Jr. 著の「Hackers Delight」という本 (本を持っておくことを強くお勧めします! ) pp. 180ff に記載されています。

関連する章の Google ブックスへのリンク:

第 10-9 章 除数 >= 1 による符号なし除算

于 2010-10-25T18:16:31.787 に答える