9

大規模なシミュレーションの一部である小さなコードのプロファイリングを行っていましたが、驚いたことに、2 つの配列を要素ごとに比較すると、STL 関数 equal (std::equal) は単純な for ループよりもはるかに遅くなります。私は小さなテスト ケースを作成しました。これは、2 つの間の公正な比較であると信じています。違いは、Debian アーカイブの g++ 6.1.1 を使用することは重要ではありません。符号付き整数の 2 つの 4 要素配列を比較しています。std::equal、operator==、および小さな for ループをテストしました。正確なタイミングには std::chrono を使用しませんでしたが、time ./a.out で違いを明示的に確認できます。

私の質問は、以下のサンプル コードを考えると、なぜ operator== とオーバーロードされた関数 std::equal (これは operator== を呼び出すと思います) が完了するのに約 40 秒かかり、手書きのループは 8 秒しかかからないのですか? ごく最近の Intel ベースのラップトップを使用しています。for ループは、-O1、-O2、-O3、および -Ofast のすべての最適化レベルで高速です。でコードをコンパイルしました g++ -std=c++14 -Ofast -march=native -mtune=native

コードを実行する

肉眼で違いを明確にするためだけに、ループは膨大な回数実行されます。モジュロ演算子は、配列要素の 1 つで安価な操作を表し、コンパイラがループ外で最適化するのを防ぐのに役立ちます。

#include<iostream>
#include<algorithm>
#include<array>

using namespace std;
using T = array<int32_t, 4>;

bool 
are_equal_manual(const T& L, const T& R)
noexcept {
    bool test{ true };
    for(uint32_t i{0}; i < 4; ++i) { test = test && (L[i] == R[i]); }
    return test;
}

bool
are_equal_alg(const T& L, const T& R)
noexcept {
    bool test{ equal(cbegin(L),cend(L),cbegin(R)) };
    return test;
}

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

    T left{ {0,1,2,3} };
    T right{ {0,1,2,3} };

    cout << boolalpha << are_equal_manual(left,right) << endl;
    cout << boolalpha << are_equal_alg(left,right) << endl;
    cout << boolalpha << (left == right) << endl;

    bool t{};
    const size_t N{ 5000000000 };
    for(size_t i{}; i < N; ++i) {
      //t = left == right; // SLOW
      //t = are_equal_manual(left,right); // FAST
        t = are_equal_alg(left,right);  // SLOW
      left[0] = i % 10;
      right[2] = i % 8;
    }

    cout<< boolalpha << t << endl;

    return(EXIT_SUCCESS);
}
4

1 に答える 1

1

関数が使用されたときに生成されるforループのアセンブリを次に示します。main()are_equal_manual(left,right)

.L21:
        xor     esi, esi
        test    eax, eax
        jne     .L20
        cmp     edx, 2
        sete    sil
.L20:
        mov     rax, rcx
        movzx   esi, sil
        mul     r8
        shr     rdx, 3
        lea     rax, [rdx+rdx*4]
        mov     edx, ecx
        add     rax, rax
        sub     edx, eax
        mov     eax, edx
        mov     edx, ecx
        add     rcx, 1
        and     edx, 7
        cmp     rcx, rdi

そして、are_equal_alg(left,right)関数が使用されたときに生成されるものは次のとおりです。

.L20:
        lea     rsi, [rsp+16]
        mov     edx, 16
        mov     rdi, rsp
        call    memcmp
        mov     ecx, eax
        mov     rax, rbx
        mov     rdi, rbx
        mul     r12
        shr     rdx, 3
        lea     rax, [rdx+rdx*4]
        add     rax, rax
        sub     rdi, rax
        mov     eax, ebx
        add     rbx, 1
        and     eax, 7
        cmp     rbx, rbp
        mov     DWORD PTR [rsp], edi
        mov     DWORD PTR [rsp+24], eax
        jne     .L20

最初のケースで生成されたコードで何が起こっているのか正確にはわかりませんが、明らかに呼び出していませんmemcmp()。配列の内容をまったく比較していないようです。ループはまだ 5000000000 回繰り返されていますが、何もしないように最適化されています。ただし、使用するループare_equal_alg(left,right)はまだ比較を実行しています。std::equal基本的に、コンパイラはテンプレートよりもはるかに優れた手動比較を最適化できます。

于 2016-09-01T04:42:43.917 に答える