次のようなC++のコードがあります。

#include <chrono>
#include <iostream>
int main() {
    unsigned rnd = 1;
    unsigned a = 2, b = 3, c = 4;

    auto st = std::chrono::system_clock::now();
    for (int i = 0; i != 100000000; ++i) {
        rnd = 1103515245 * rnd + 12345;
        a = (rnd >> 31 & 1) ? 13 * a + 17 : a;
        b = (rnd >> 30 & 1) ? 31 * b + 29 : b;
        c = (rnd >> 29 & 1) ? 15 * c + 11 : c;
    }
    std::cout << std::chrono::system_clock::now() - st << std::endl;

    std::cout << a << ' ' << b << ' ' << c << '\n';
}

これを実行すると以下のような出力が得られました。

762967000ns
2531276912 1104338938 1163044519

ループ内の計算に762msかかっているようです。

次に、ループの中身をこのような等価なものに書き換えます。

rnd = 1103515245 * rnd + 12345;
volatile unsigned tmp1 = 13 * a + 17;
volatile unsigned tmp2 = 31 * b + 29;
volatile unsigned tmp3 = 15 * c + 11;
unsigned tmp4 = tmp1, tmp5 = tmp2, tmp6 = tmp3;
a = (rnd >> 31 & 1) ? tmp4 : a;
b = (rnd >> 30 & 1) ? tmp5 : b;
c = (rnd >> 29 & 1) ? tmp6 : c;

この書き換えたバージョンを実行すると

139995000ns
2531276912 1104338938 1163044519

このような出力を得られました。
ループ内の計算に139msかかっています。元のコードだと762msですから、762÷139=5.48倍の高速化に成功しました！

なんで?

元のコードのループ内のアセンブリを見てみます。

.L62:
        imul    edx, edx, 1103515245
        add     edx, 12345
        jns     .L59
        lea     esi, [rbx+rbx*2]
        lea     ebx, [rbx+17+rsi*4]
.L59:
        test    edx, 1073741824
        je      .L60
        mov     esi, r12d
        sal     esi, 5
        sub     esi, r12d
        lea     r12d, [rsi+29]
.L60:
        test    edx, 536870912
        je      .L61
        mov     esi, ebp
        sal     esi, 4
        sub     esi, ebp
        lea     ebp, [rsi+11]
.L61:
        sub     ecx, 1
        jne     .L62

jeが2回、jns、jneが1回ずつの計4回の条件分岐が行われています。最後のjne .L62はループの終了判定で、残りの3回はループ内の三項演算子に対応しています。

書き換えた後のアセンブリも見てみましょう。

.L62:
        imul    eax, eax, 1103515245
        lea     edx, [rbx+rbx*2]
        lea     edx, [rbx+17+rdx*4]
        mov     DWORD PTR [rsp+12], edx
        mov     edx, r12d
        sal     edx, 5
        sub     edx, r12d
        add     edx, 29
        mov     DWORD PTR [rsp+16], edx
        mov     edx, ebp
        sal     edx, 4
        sub     edx, ebp
        add     edx, 11
        add     eax, 12345
        mov     DWORD PTR [rsp+20], edx
        mov     edi, DWORD PTR [rsp+12]
        mov     esi, DWORD PTR [rsp+16]
        mov     edx, DWORD PTR [rsp+20]
        cmovs   ebx, edi
        test    eax, 1073741824
        cmovne  r12d, esi
        test    eax, 536870912
        cmovne  ebp, edx
        sub     ecx, 1
        jne     .L62

ループの終了判定以外の条件分岐が消え去り、条件付き移動命令(cmovsとcmovne)に置きかわっています。

※追記
@fujitanozomuさんがコメントで指摘してくださったのですが、volatileを使うと最適化が抑止されるため、スタックフレームへの余計な読み書きが生じて(mov DWORD PTR [rsp+12], edxなど)速度に影響があるようです。提案されているインラインアセンブリを使用した方法を計測したところ132msであり、volatileを使うバージョンより少し高速でした。

実行したコード

#include <chrono>
#include <iostream>
#include <type_traits>
int main() {
    unsigned rnd = 1;
    unsigned a = 2, b = 3, c = 4;

    auto st = std::chrono::system_clock::now();
    for (int i = 0; i != 100000000; ++i) {
        rnd = 1103515245 * rnd + 12345;
        if (!std::is_constant_evaluated()) { // コンパイル時計算をする場合には必要
            __asm__ volatile("" ::"r"(13 * a + 17), "r"(31 * b + 29), "r"(15 * c + 11));
        }
        a = (rnd >> 31 & 1) ? 13 * a + 17 : a;
        b = (rnd >> 30 & 1) ? 31 * b + 29 : b;
        c = (rnd >> 29 & 1) ? 15 * c + 11 : c;
    }
    std::cout << std::chrono::system_clock::now() - st << std::endl;

    std::cout << a << ' ' << b << ' ' << c << '\n';
}

条件分岐について

通常、プロセッサはいくつかの命令を並列に実行し、効率を高めています。しかし、条件分岐があるとどちらの分岐を実行していいのかがわからないため、分岐予測が行われるまでCPU内の多くの部分が待つことになります。CPUには分岐予測の機能がありますが、今回の場合trueになる確率とfalseになる確率が半々かつランダムなため予測は困難です。予測が当たった場合は1 cycle程度で実行できますが、外れた場合は約18 cycleもかかってしまうためボトルネックになりやすいです。¹

条件付き移動について

cmov系の命令を使うと条件分岐を削除できる場合があります。具体的にはa = b ? c : aのようなプログラムを3 cycleで実行できます。しかし、条件分岐の方がいいときもあります。なぜならa = b ? 13 * a + 17 : aのようなプログラムの場合、bがtrueかfalseかにかかわらず13 * a + 17の値を求めなければならないからです。今回のケースではGCCは分岐予測失敗のコストよりも13 * a + 17の値を毎回求めるコストのほうが高いと判断しています。(実際には間違いですが...)

なぜvolatileで条件分岐を回避できる?

volatileを使うと、変数への読み書きを最適化することを禁止します。

volatile unsigned tmp1 = 13 * a + 17;
unsigned tmp4 = tmp1
a = (rnd >> 31 & 1) ? tmp4 : a;

tmp1がvolatileなので、(rnd >> 31 & 1)がfalseでも13 * a + 17を強制的に計算しなければいけなくなります。GCCは13 * a + 17を毎回計算するのを避けるため条件分岐にコンパイルしていましたが、これにより条件分岐を使用するメリットがなくなって条件付き移動が使用されるようになります。

おまけ

clangは賢いので、最初の書き方でも条件分岐を使わないコードにコンパイルしてくれます。

127011000ns
2531276912 1104338938 1163044519

GCCより速いです。アセンブリを見たらループアンローリングをしていたので、そのためだと思います。

追記：Visual C++だと、次のようにしても分岐は除去できるようです。

rnd = 1103515245 * rnd + 12345;
unsigned tmp1 = 13 * a + 17;
unsigned tmp2 = 31 * b + 29;
unsigned tmp3 = 15 * c + 11;
a = (rnd >> 31 & 1) ? tmp1 : a;
b = (rnd >> 30 & 1) ? tmp2 : b;
c = (rnd >> 29 & 1) ? tmp3 : c;

2045522[1/10000000]s
2531276912 1104338938 1163044519

環境

実行環境

gcc.exe (x86_64-win32-seh-rev0, Built by MinGW-Builds project) 13.2.0
g++ -g -std=gnu++20 -O2 -mtune=native -march=native -o a.exe Tmp.cpp

clang version 18.1.6 (https://github.com/llvm/llvm-project.git 1118c2e05e67a36ed8ca250524525cdb66a55256)
clang++ -g -std=c++20 -O2 -mtune=native -march=native -fuse-ld=lld -o a.exe Tmp.cpp

Microsoft Visual Studio Community 2022 (64 ビット) - Current
Version 17.9.5
Releaseモードで実行

アセンブリ

Compiler Explorer (https://godbolt.org/)
x86-64 gcc 13.2
-O2 -mavx512vl -std=c++20

参考：https://lpha-z.hatenablog.com/entry/2020/11/15/231500 ↩