9

unsigned short int の上位ビットを使用して、合計する配列の値を示す、小さくて使用頻度の高い関数を最適化しようとしています。最初は、以下に示す明白なアプローチを使用していました。ループのアンローリングは、コンパイラによって実行される必要があるため、明示的に表示されないことに注意してください。

int total = 0;
for(unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++){
    if (i & mask){
        total += value[j];
    }
}

しかし、後になって、CPU のパイプライン処理を支援するために分岐を削除した方がよいのではないかと考え、次のことを思いつきました。

int total = 0;
for(unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++){
    total += ((i & mask) != 0) * value[j];
}

(i & mask) はブール値の答えにはならないので、0 との比較は結果を 1 または 0 にすることに注意してください。方程式の残りの部分に加えて、反復ごとに 0 または 1 の乗算を実行します。

どのコードがより速く実行されますか?

4

12 に答える 12

13

どのコードがより速く実行されますか?

テストして確認してください。

また、コンパイラが発行するコードのアセンブリ言語バージョンを見てください。そこには、驚くべきことや、さらなる最適化を示唆するものが含まれている可能性があるためです (たとえば、使用中の使用には、使用short中の使用よりも多くの命令が必要な場合があります)。マシンの自然な整数サイズ)。

于 2009-02-05T05:10:06.460 に答える
9

どちらかが速くなる可能性があります。一部のプロセッサでは、実際の入力データによって答えが変わる場合があります。実際のデータを使用して両方のアプローチをプロファイリングする必要があります。x86 ハードウェアでの実際のパフォーマンスに影響を与える可能性のあるいくつかの事柄を次に示します。

差し当たり、最新モデルの Pentium 4 を使用していると仮定しましょう。このプロセッサには、2 レベルの分岐予測子が CPU に組み込まれています。分岐予測子が分岐方向を正しく推測できる場合、最初の分岐が最速になると思います。これは、フラグがほぼすべて同じ値であるか、ほとんどの場合非常に単純なパターンで交互に変化する場合に発生する可能性が最も高くなります。フラグが完全にランダムである場合、分岐予測子は半分の確率で間違っています。仮想的な 32 ステージの Pentium 4 では、これによりパフォーマンスが低下します。Pentium 3 チップ、Core 2 チップ、Core i7、およびほとんどの AMD チップでは、パイプラインが短くなるため、不適切な分岐予測のコストははるかに低くなります。

値ベクトルがプロセッサのキャッシュより著しく大きい場合、いずれのアプローチもメモリ帯域幅によって制限されます。どちらも本質的に同じパフォーマンス特性を持っています。値ベクトルがキャッシュに問題なく収まる場合は、プロファイリングの方法に注意して、テスト ループの 1 つがキャッシュをいっぱいにすることでペナルティを受けないようにし、もう 1 つのテスト ループがその恩恵を受けるようにします。

于 2009-02-05T05:15:29.240 に答える
8

乗算なしでブランチレスにすることができます。ビットセットごとに、そのビット位置を配列へのインデックスとして使用しているように見えます。

まず、次のように設定されたビットを簡単に抽出できます。

unsigned short set_mask= i & -i;
i&= i - 1;

次に、 に設定されたビットをカウントすることで、ビット インデックスを取得できます(set_mask - 1)。これには一定時間の公式があります。

一部のプラットフォームには、おそらくより高速なビット セットのビット インデックスを取得するための組み込み関数もあります。x86にはbsr、PPCにはありcntlzます。

したがって、答えは、ブランチレス乗算なしバージョンがおそらく最速です:)

于 2009-02-05T05:19:15.737 に答える
4

このリビジョンはどうですか?

int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++){
    total += (mask & 0x0001) * value[j];
}

16 ビットの符号なし範囲に制限さmaskれたコピーを作成しましたが、コードはマスクの最後のビットが設定されているかどうかをチェックし、配列の値にそのビットを掛けます。i反復ごとの操作が少なく、メイン ループの分岐と条件のみが必要なため、これは単純に高速になるはずです。iまた、最初からが小さい場合、ループは早期に終了する可能性があります。


これは、測定が重要である理由を示しています。古い Sun SPARC を使用しています。質問の 2 つの候補をテスト 0 とテスト 1 として、私自身の回答をテスト 2 として、示されているようにテスト プログラムを作成しました。次に、タイミング テストを実行しました。「合計」はサニティ チェックとして出力されます。これは、アルゴリズムがすべて同じ答えを出すことを保証するためです。

最適化されていない 64 ビット:

gcc -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4

Test 0: (sum = 1744366)  7.973411 us
Test 1: (sum = 1744366) 10.269095 us
Test 2: (sum = 1744366)  7.475852 us

ナイス: 私のは元のバージョンよりもわずかに高速で、強化されたバージョンは低速です。

最適化された 64 ビット:

gcc -O4 -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4

Test 0: (sum = 1744366)  1.101703 us
Test 1: (sum = 1744366)  1.915972 us
Test 2: (sum = 1744366)  2.575318 us

ダーン - 私のバージョンは劇的に遅くなりました。オプティマイザは良いです!

32 ビットに最適化:

gcc -O4 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4

Test 0: (sum = 1744366)  0.839278 us
Test 1: (sum = 1744366)  1.905009 us
Test 2: (sum = 1744366)  2.448998 us

最適化されていない 32 ビット:

gcc -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4

Test 0: (sum = 1744366)  7.493672 us
Test 1: (sum = 1744366)  9.610240 us
Test 2: (sum = 1744366)  6.838929 us

(32ビット)Cygwinとそれほど古くないラップトップ(32ビット、最適化)で同じコード

Test 0: (sum = 1744366)  0.557000 us
Test 1: (sum = 1744366)  0.553000 us
Test 2: (sum = 1744366)  0.403000 us

今、私のコード最速です。だからこそ測る!また、生計を立てるためにベンチマークを実行している人々が取り乱す理由も示しています。

timer.hテスト ハーネス (およびtimer.cコードが必要な場合は叫ぶ):

#include <stdio.h>
#include "timer.h"

static volatile int value[] =
{
    12, 36, 79, 21, 31, 93, 24, 15,
    56, 63, 20, 47, 62, 88,  9, 36,
};

static int test_1(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        if (i & mask)
            total += value[j];
    }
    return(total);
}

static int test_2(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        total += ((i & mask) != 0) * value[j];
    }
    return(total);
}

static int test_3(int i)
{
    int total = 0;
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
    {
        total += (mask & 0x0001) * value[j];
    }
    return(total);
}

typedef int(*func_pointer)(int);

static func_pointer test[] = { test_1, test_2, test_3 };

#define DIM(x)(sizeof(x)/sizeof(*(x)))

int main()
{
    int i, j, k;
    char buffer[32];
    for (i = 0; i < DIM(test); i++)
    {
        Clock t;
        long sum = 0;
        clk_init(&t);
        clk_start(&t);
        for (j = 0; j < 0xFFFF; j += 13)
        {
            int rv;

            for (k = 0; k < 1000; k++)
                rv = (*test[i])(j);
            sum += rv;
        }
        clk_stop(&t);
        printf("Test %d: (sum = %ld) %9s us\n", i, sum,
               clk_elapsed_us(&t, buffer, sizeof(buffer)));
    }
}

最適化するとコードが遅くなる理由を解明するのに時間を費やしていません。

于 2009-02-05T06:15:16.873 に答える
3

これは、コンパイラ、機械命令セット、そしておそらく月の満ち欠けに完全に依存します。

このため、具体的な正解はありません。本当に知りたい場合は、コンパイラからのアセンブリ出力を確認してください。

単純化した観点から言えば、最初のすべての計算に加えて乗算が含まれるため、2 番目の方が遅いと言えます。しかし、コンパイラはそれを最適化するのに十分賢いかもしれません。

したがって、正しい答えは次のとおりです。

于 2009-02-05T05:06:47.400 に答える
1

2 番目の例には明示的な分岐はありませんが、比較の結果を bool に変換するための暗黙的な分岐がある可能性があります。コンパイラのアセンブリ リストの出力をオンにして、それを調べると、少し洞察が得られる場合があります。

もちろん、確実に知る唯一の方法は、両方の方法でいくつかのタイミングを取ることです.

于 2009-02-05T05:07:00.193 に答える
1

答えはきっと次のとおりです。ターゲット ハードウェアで試してみてください。また、ここ数週間にわたって SO に投稿された多数のマイクロ ベンチマーク/ストップウォッチ ベンチマークの質問のアドバイスに従ってください。

ベンチマークに関する 1 つの質問へのリンク:ストップウォッチのベンチマークは許容されますか?

個人的には、「難読化された」代替手段を使用する本当に説得力のある理由がない限り、if を使用します。

于 2009-02-05T05:07:21.767 に答える
1

超高速にするために、ループ、シフト、および乗算を回避できます-スイッチを使用します。

switch (i) {
    case 0: break;
    case 1: total = value[0]; break;
    case 2: total = value[1]; break;
    case 3: total = value[1] + value[0]; break;
    case 4: total = value[2]; break;
    case 5: total = value[2] + value[0]; break;
    ...
}

入力するのはたくさんありますが、実行時ははるかに高速になると思います。ルックアップ テーブルのパフォーマンスに勝るものはありません。

入力エラーを避けるために、このコードを生成する小さな Perl スクリプトを作成したいと思います。

少し極端だと思う場合は、より小さなテーブルを使用できます-4ビットの場合、ルックアップを数回実行し、毎回マスクをシフトします。パフォーマンスは少し低下しますが、コードははるかに小さくなります。

于 2009-02-05T07:41:09.213 に答える
1

ステートメントの真偽を判断する唯一の実際の方法は、テストすることです。それを念頭に置いて、試してみてくださいという以前の投稿に同意します。

最近のほとんどのプロセッサでは、分岐はコストのかかるプロセスであり、特に分岐の頻度が低い場合は特にそうです。これは、パイプラインをフラッシュする必要があり、結果として CPU が 1 つまたは複数の命令を同時に実行できなくなるためです。単純に、次の命令がどこから来るかわからないためです。分岐が少ないと、可能な制御フローが複雑になり、CPU がすべての可能性を同時に試すことができなくなるため、分岐を実行してから、その後一度に多くの命令を実行し始める必要があります。

于 2009-02-05T06:11:53.340 に答える
1

明白な解決策:

int total = 0;
for(unsigned j = 0; j < 16; j++){
    total += -(i>>j & 1) & value[j];
}
于 2011-02-10T11:10:17.433 に答える
1

なぜこれをしないのですか(iが32ビットであると仮定して)

  for (i2 = i; i2; i2 = i3) {
    i3 = i2 & (i2-1);
    last_bit = i2-i3;
    a = last_bit & 0xffff;
    b = (last_bit << 16);
    j = place[a] + big_place[b];
    total += value[j];
  }

place は、place[0] = 0、place[1] = 1、place[2] = 2、place[4] = 3、place[8] = 4 のようなサイズ 2^15+1 のテーブルです。 .place[15] = 16 (残りの値は重要ではありません)。big_place はほぼ同じです: big_place[0] = 0,big_place[1] = 17.... big_place[15] = 32.

于 2009-02-05T06:16:25.437 に答える
1

試す

total += (-((i & mask) != 0)) & value[j];

代わりに

total += ((i & mask) != 0) * value[j];

これにより、乗算が回避されます。分岐があるかどうかは、コンパイラが -(foo != 0) の分岐のないコードを見つけるのに十分賢いかどうかにかかっています。(これは可能ですが、少し驚きます。)

(もちろん、これは 2 の補数表現に依存します。C 標準はそれにとらわれません。)

32 ビットの int とその符号付き >> が符号ビットを伝播すると仮定すると、次のようにコンパイラを支援することができます。

total += (((int)((i & mask) << (31 - j))) >> 31) & value[j];

つまり、設定された可能性のあるビットを左にシフトして最も重要な位置に置き、signed int としてキャストし、次に右に移動して最も重要でない位置に戻し、上記の実装定義の仮定の下で、すべて 0 またはすべて 1 のいずれかを生成します。 . (私はこれをテストしていません。)

別の可能性: 一度に (たとえば) 4 ビットのブロックを検討してください。16 の異なる加算シーケンスがあります。各コードブロック内でテストをまったく行わずに、それぞれの展開されたコードにディスパッチできます。ここでの希望は、1 回の間接ジャンプのコストが 4 回のテストと分岐よりも少なくなることです。

更新: Jonathan Leffler の scaffolding を使用すると、一度に 4 ビットの方法が私の MacBook で大幅に高速になります。Negate-and は、乗算とほぼ同じであることがわかります。プロセッサが 0 と 1 のような特殊なケースをより速く乗算するかどうかは疑問です (または、ほとんどのビットがクリアまたは最もビットが設定された被乗数で一般的に高速である場合、そのような特殊なケースではありません)。

この特定のベンチマークで最速になる可能性は低いため、受け入れられた回答をコーディングしませんでした(設定されたビットのみを列挙し、スパースセットで最善を尽くすことでほとんどの利点が得られるはずですが、ビットの完全な半分がこれに設定されています基準)。他の誰かがこれに時間を費やすことに奇妙な動機を持っている場合に備えて、Leffler のコードに対する私の変更は次のとおりです。

#include <stdio.h>
#include <time.h>

static int value[] =
{
    12, 36, 79, 21, 31, 93, 24, 15,
    56, 63, 20, 47, 62, 88,  9, 36,
};

static int test_1(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        if (i & mask)
            total += value[j];
    }
    return(total);
}

static int test_2(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        total += ((i & mask) != 0) * value[j];
    }
    return(total);
}

static int test_3(int i)
{
    int total = 0;
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
    {
        total += (mask & 0x0001) * value[j];
    }
    return(total);
}

static int test_4(int i)
{
    int total = 0;
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
    {
        total += -(mask & 0x0001) & value[j];
    }
    return(total);
}

static int test_5(int i)
{
    int total = 0;
    const int *p = value;
    for (unsigned mask = i & 0xFFFF; mask != 0; mask >>= 4, p += 4)
    {
        switch (mask & 0xF)
        {
        case 0x0: break;
        case 0x1: total += p[0]; break;
        case 0x2: total += p[1]; break;
        case 0x3: total += p[1] + p[0]; break;
        case 0x4: total += p[2]; break;
        case 0x5: total += p[2] + p[0]; break;
        case 0x6: total += p[2] + p[1]; break;
        case 0x7: total += p[2] + p[1] + p[0]; break;
        case 0x8: total += p[3]; break;
        case 0x9: total += p[3] + p[0]; break;
        case 0xA: total += p[3] + p[1]; break;
        case 0xB: total += p[3] + p[1] + p[0]; break;
        case 0xC: total += p[3] + p[2]; break;
        case 0xD: total += p[3] + p[2] + p[0]; break;
        case 0xE: total += p[3] + p[2] + p[1]; break;
        case 0xF: total += p[3] + p[2] + p[1] + p[0]; break;
        }
    }
    return(total);
}

typedef int(*func_pointer)(int);

static func_pointer test[] = { test_1, test_2, test_3, test_4, test_5 };

#define DIM(x)(sizeof(x)/sizeof(*(x)))

int main()
{
    int i, j, k;
    for (i = 0; i < DIM(test); i++)
    {
        long sum = 0;
        clock_t start = clock();
        for (j = 0; j <= 0xFFFF; j += 13)
        {
            int rv;

            for (k = 0; k < 1000; k++)
                rv = (*test[i])(j);
            sum += rv;
        }
        clock_t stop = clock();
        printf("(sum = %ld) Test %d: %8.6f s\n", sum, i + 1, 
               (stop - start) / (1.0 * CLOCKS_PER_SEC));
    }
}

結果 ( gcc -O4 -std=c99 branchmult2.c):

(sum = 1744366) Test 1: 0.225497 s
(sum = 1744366) Test 2: 0.221127 s
(sum = 1744366) Test 3: 0.126301 s
(sum = 1744366) Test 4: 0.124750 s
(sum = 1744366) Test 5: 0.064877 s

編集 2:volatile修飾子がなければ、テストはより現実的であると判断しました。

于 2009-02-05T06:18:42.530 に答える