[解決済み] 最新のx86-64 clangでソートされていない配列の処理とソートされた配列の処理が同じ速度になるのはなぜですか？

質問

9歳児に大人気の SO質問 その結果を再確認することにしました。

で、AMD Ryzen 9 5950Xとclang++ 10とLinuxを持っているので、質問からコードをコピーペーストしてみたら、こんな感じになりました。

ソート済み - 0.549702s :

~/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.546554s :

~/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

ソートされていないバージョンの方が3ms速くなったというのは単なるノイズであることは間違いないのですが、もう遅くはなっていないようです。

では。 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

ほとんど差がないというのは、やはり疑問だと思います。

どのように解決するのですか？

リンク先の質問にあるいくつかの回答は、分岐のないコードに書き換えて、分岐予測の問題を回避することについて述べています。 これは、あなたがアップデートしたコンパイラが行っていることです。

具体的には、clang++ 10で -O3 ベクトル化 は、内側のループを godboltのコードを見る , アセンブリの36-67行目。 少し複雑なコードですが、ひとつだけ絶対に見えないのが data[c] >= 128 をテストします。 その代わり、ベクター比較命令( pcmpgtd その出力は，一致する要素を1，一致しない要素を0とするマスクである。 その後に続く pand は、このマスクによって、マッチしない要素が0に置き換えられ、無条件に和に追加されても何も貢献しないようになる。

大まかな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 を追加しました。

の8つの要素を処理し、ループを展開しているため、コードも長く見えます。 data を繰り返し実行します。