次のような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もかかってしまうためボトルネックになりやすいです。1
条件付き移動について
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