2

以下の関数は、テスト後foo2までよりも高速であると常に信じていました。foo3

以下のすべてのコード:

#include <iostream>
#include <boost/timer.hpp>
#include <boost/lexical_cast.hpp>
#include <stdint.h>

struct session {
    bool operator==(const session& r) const;

    uint8_t proto;
    uint16_t sport;
    uint16_t dport;
    uint32_t sip;
    uint32_t dip;
};

bool session::operator==(const session& r) const {
    return proto == r.proto && sport == r.sport && dport == r.dport 
        && sip == r.sip && dip == r.dip;
}

// my L1,L2,L3 total cache size is 16MB, so set it 32MB to overflow all 16MB caches.
static const int SIZE = 32 * 1024 * 1024 / sizeof(session);
int sum;

void foo1(session* p) {
    session s = {1, 2, 3, 4, 5};
    for (int i = 0; i < SIZE; i++)
        if (p[i] == s)
            sum++;
}

void foo2(session* p) {
    session s = {1, 2, 3, 4, 5};
    int n = SIZE - SIZE % 4;
    int i;

    for (i = 0; i < n; i += 4) {
        if (p[i + 0] == s)
            sum++;
        if (p[i + 1] == s)
            sum++;
        if (p[i + 2] == s)
            sum++;
        if (p[i + 3] == s)
            sum++;
    }
    /*
    for (; i < SIZE; i++)
            if (p[i] == s)
               sum++;
    */
}

void foo3(session* p) {
    session s = {1, 2, 3, 4, 5};
    int n = SIZE - SIZE % 4;
    int i;

    for (i = 0; i < n; i += 4) {
        if (p[i + 0] == s)
            sum++;
        else if (p[i + 1] == s)
            sum++;
        else if (p[i + 2] == s)
            sum++;
        else if (p[i + 3] == s)
            sum++;
    }
    /*
    for (; i < SIZE; i++)
            if (p[i] == s)
               sum++;
    */
}

int main(int argc, char* argv[]) {
    if (argc < 2)
        return -1;

    int n = boost::lexical_cast<int>(argv[1]);
    session* p = new session[SIZE];

    boost::timer t;
    for (int i = 0; i < n; i++)
        foo1(p);
    std::cout << t.elapsed() << std::endl;

    t.restart();
    for (int i = 0; i < n; i++)
        foo2(p);
    std::cout << t.elapsed() << std::endl;

    t.restart();
    for (int i = 0; i < n; i++)
        foo3(p);
    std::cout << t.elapsed() << std::endl;

    delete [] p;
    return 0;
}

1000回テストし、./a.out 1000

出力：

4.36
3.98
3.96

私のマシン：

CPU: Intel(R) Xeon(R) CPU E5-2420 0 @ 1.90GHz

キャッシュ:

L1d キャッシュ: 32K

L1i キャッシュ: 32K

L2 キャッシュ: 256K

L3 キャッシュ: 15360K

テストでは、同等の性能foo2を持っています。CPU が展開されたすべての式を並列に実行foo3する可能性があるため、同じです。そうですよね？その場合、構文は C/C++ の基本的なセマンティクスに違反しています。foo2foo3else ifelse if

誰かがそれを説明していますか？どうもありがとう。

アップデート

私のコンパイラはgcc 4.4.6 ins RedHatです

g++ -Wall -O2 a.cpp

4

3 に答える 3

3

特定の状況では、短絡する可能性があるため、foo3 の方が高速であることが期待されます (4 以下の分岐が発生しますが、foo2 では常に 4 つの分岐が発生します)。sが 4 つの配列要素のいずれとも等しくない場合 (この場合は非常に可能性が高い)、foo2 と foo3 は基本的に同じコードです。その場合、両方の関数で 4 つの分岐が発生します。

(ブランチに関して) foo3 が実際にどのように見えるかを考えてみましょう:

if (p[i + 0] == s)
    sum++;
else
    if (p[i + 1] == s)
        sum++;
    else 
        if (p[i + 2] == s)
            sum++;
        else 
            if (p[i + 3] == s)
                sum++;

ifこれにより、偽が発生し続ける限り、サブブランチが発生することが明らかになるはずです。これは、どの if も真でない状況では、foo2 と同じ数の操作を実行することを意味します (ただし、機能は同じではありません)。

それについて大まかに考えると、それぞれifにコストがあるかのようになります (if の本体ではなく、実際の if)。つまり、実行フローが an に到達するたびifに、一定のコストが必要になります。これは、分岐を行う必要があるためです。このように考えると、foo3 のフローが短絡していない場合 (4 つのすべてのfoo3sifに遭遇した場合)、各関数のコストが同じであることは明らかです。(KillianDS が指摘したように、分岐予測が間違っている場合、実際には foo3 の方が時間がかかります。これは、間違った分岐を巻き戻し、代わりに正しい分岐を実行する必要があるためです。ただし、正しい分岐が常に選択されているように見えます。)

これは、次のコード スニペットが同じパフォーマンスを持つ方法に似ています。

if (short_runtime()) {}

と：

if (short_runtime() && long_runtime()) {}

true を返す場合short_runtime、2 番目の関数呼び出しを伴うものは明らかに時間がかかります。short_runtime()ただし、戻り値が falseの場合、long_runtime()呼び出しは発生しないため、実行時間は同じになります (または少なくとも非常に似ています)。

この理論をテストするために、それp[i + 0] == sが真実になるように作ることができます。配列の値を初期化し（session* p = new session[SIZE]();）、session s = {1, 2, 3, 4, 5};ローカルで使用するだけです。

ループ展開の目的/結果については、少し混乱しているようです。ジャンプが少なくて済むようにするためです。処理が必要な場合nは、n反復ごとに 1 つのアクションでn/k反復 (ジャンプ) が発生する代わりに、代わりに反復 (ジャンプ) を発生させることができます。すべてがキャッシュに収まる場合、これにより速度が向上します (キャッシュに収まらない場合は、実際にパフォーマンスが低下する可能性があります!)。

命令は同時に発生していません (同時に発生した場合、sum非常に高価なミューテックスが必要になります)。1セットではなく、4セットで発生しているだけです。

于 2013-08-15T09:43:55.200 に答える
2

これは分岐予測です:

あなたのプログラムでは、これらの速度が得られます（ここではfoo3は少し遅く、g ++ 4.8です）：

7.57
0.63
0.99

さてどうなる？セッションの初期配列を初期化しないでください。すべての変数sessionが POD であるため、デフォルトで初期化されず、本質的にゴミが含まれます。したがって、ifコード内の 's' は非常に迅速に収束し、常に実行されない分岐を予測します。この場合foo3、 とfoo2は非常に似ておりfoo2、無条件にすべての if を実行し、foo3予測されているため実行します。foo3なぜまだ少し遅いのかはよくわかりません。そのための逆アセンブリコードを調べる必要があります。

次のデフォルト コンストラクターを追加するとどうなるか見てみましょう。

session() : proto(1), sport(2), dport(3), sip(4), dip(5) {}

もちろん、のセッション変数も変更する必要がありましたfoo。session s;これで、タイミングは次のようになります。

9.7
1.5
0.75

突然foo3、ずっと速くなります。単純に、ブランチがほとんど (正しく) 'taken' と予測されるからです。この場合foo3、最初の条件のみが実行され、関数がすぐに終了することを意味します。foo2予測が良好であっても、すべてのブランチを評価する必要があるため、明らかに遅くなります。

于 2013-08-15T10:08:53.070 に答える
0
  • foo2 と foo3 は、出力に 0.02 ms または s の差しかないため、同等のパフォーマンスを示します。異なるセッション サイズを使用して、foo2 と foo3 の複数のテストを実行できます。サイズは 10、19、20、21、50、80、99 などです。これにより、パフォーマンスが同等かどうかを判断するための出力がさらに得られます。
  • この問題では、ループ展開を実行してコンパイラを悪用しようとしています。if ステートメントと else if ステートメントは、並列処理と最適化の一部ではないため、コンパイラにとってあまり意味がないかもしれませんが、それでも役立つ場合があります。
于 2013-09-01T05:10:20.760 に答える