☰

最新の x86-64 clang でソートされていない配列を処理する速度が、ソートされた配列を処理する速度と同じなのはなぜですか? 質問する

tag-icon • tag-icon c++ performance clang cpu-architecture branch-prediction
最新の x86-64 clang でソートされていない配列を処理する速度が、ソートされた配列を処理する速度と同じなのはなぜですか? 質問する

私はこの人気の9歳児を発見しました質問ですそしてその結果を再確認することにしました。

そこで、私は AMD Ryzen 9 5950X、clang++ 10、Linux を使用して、質問からコードをコピーして貼り付け、次のような結果を得ました。

ソート済み - 0.549702秒:

~/d/so_sorting_faster$ cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    std::sort(data, data + arraySize);
0.549702
sum = 314931600000

未分類 - 0.546554秒:

~/d/so_sorting_faster $ cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    // std::sort(data, data + arraySize);
0.546554
sum = 314931600000

ソートされていないバージョンが 3 ミリ秒速くなったという事実は単なるノイズであると確信していますが、もはや遅くはないようです。

それで、CPUのアーキテクチャで何が変わったか(もう桁違いに遅くならないように)?

複数回実行した結果は次のとおりです。

Unsorted: 0.543557 0.551147 0.541722 0.555599
Sorted:   0.542587 0.559719 0.53938  0.557909

念のため、main.cpp をここに示します。

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    // std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
    return 0;
}

アップデート

要素数が多い場合（627680）：

Unsorted
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    // std::sort(data, data + arraySize);
10.3814

Sorted:
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    std::sort(data, data + arraySize);
10.6885

この質問は今でも関連性があると思います。ほとんど違いはありません。

ベストアンサー1

リンク先の質問の回答のいくつかでは、コードを分岐なしに書き直して分岐予測の問題を回避することについて触れています。更新されたコンパイラはまさにそれを行っています。

具体的には、clang++ 10と-O3 ベクトル化する内側のループ。godboltのコードを見る、アセンブリの 36 行目から 67 行目です。コードは少し複雑ですが、テストで条件分岐がまったく見られないのは確かです。代わりに、一致する要素には 1、一致しない要素には 0 が出力されるマスクであるdata[c] >= 128ベクトル比較命令 ( ) を使用します。このマスクを使用した後続の命令は、一致しない要素を 0 に置き換えます。そのため、無条件に合計に追加されても、一致しない要素は何も寄与しません。pcmpgtdpand

大まかにC++で言えば

sum += data[c] & -(data[c] >= 128);

コードは実際には、配列の偶数要素と奇数要素に対して 2 つの 64 ビットの実行状態を保持しsum、それらを並列に累積してループの最後に合計できるようにします。

追加の複雑さの一部は、32 ビットdata要素を 64 ビットに符号拡張することです。これは、次のようなシーケンスによってpxor xmm5, xmm5 ; pcmpgtd xmm5, xmm4 ; punpckldq xmm4, xmm5実現されます。オンにすると、代わりにより-mavx2単純なものが表示されます。vpmovsxdq ymm5, xmm5

ループが展開され、data反復ごとに 8 つの要素が処理されるため、コードも長く見えます。

おすすめ記事