ムーアの法則の終わり、そして最近の分岐予測について
序
僕らx86の大地の上に生きるものは、この10年Intelが告げるTick-Tockの鐘の音にあわせてムーアの法則の恩恵を享受してきた。*1
*2
しかし、Kaby Lakeの14nmプロセス採用つまり、2年おきのプロセスルール刷新を諦めたことを持って、ムーアの法則は終焉を迎えたとされる。が、この認識は本当に正しいのだろうか。
ムーアの1965年の論文では、後のムーアの法則を”The complexity for minimum component costs has increased at a rate of roughly a factor of two per year"と表現している。人々はこの”complexity"は単位面積あたりのトランジスタ数のことだとこの50年間理解してきた。もっと言えばこの10年はプロセス・ルールのことだったかもしれない。だが、CPUがその内に集積してきたものはトランジスタだけだったのだろうか。
前述の論文のタイトルは"Cramming more components onto integrated circuits”という。Intelは様々なものをCPUという集積回路に詰め込んできた。しかし、このタイトルとムーアの法則の記述をあわせれば、真にCPUが集積したものが何かは明らかだろう。それは「複雑さ」だ。多数のSIMD命令も、AVXの奇怪なVEXエンコーディングも、すべてこの世界の複雑さを小さな魔法の石に封じ込めた結果なのだ。
分岐予測の進化
さて、高度なCPUにはブラックボックスが多数含まれますが、分岐予測はその中の最たるものの一つでしょう。CPUの最適化情報豊富なIntel® 64 and IA-32 Architectures Optimization Reference Manualを見ても毎度"Improved branch predictor."としか書かれていません。
とはいえ、手元にCPUはあるわけで、実際に動かしてその実力を測ることは出来るので測ってみましょう。
計測に使ったのはSpeed of various interpreter dispatch techniques V2のthreading.tar.gzの./directです。現代においてこれが適切なベンチマークだとは思わないのですが、間接分岐については多少参考にはなるんじゃないかな……。
SandyBridge
naruse@chkbuild008:~/threading$ grep -m1 'model name' /proc/cpuinfo
model name : Intel(R) Xeon(R) CPU E5-2630L 0 @ 2.00GHz
naruse@chkbuild008:~/threading$ perf stat ./direct-gcc48
Performance counter stats for './direct':
277.440861 task-clock (msec)
5 context-switches
0 cpu-migrations
112 page-faults
650,780,115 cycles
365,836,274 stalled-cycles-frontend
377,885,001 stalled-cycles-backend
423,892,636 instructions
208,884,768 branches
12,251,769 branch-misses
0.278114864 seconds time elapsed
naruse@chkbuild008:~/threading$ perf stat ../direct-gcc54
Performance counter stats for '../direct-gcc54':
155.542201 task-clock (msec)
3 context-switches
0 cpu-migrations
113 page-faults
352,393,558 cycles
141,991,479 stalled-cycles-frontend
160,691,365 stalled-cycles-backend
379,813,966 instructions
160,216,299 branches
3,933 branch-misses
0.156168350 seconds time elapsed
% grep -m1 'model name' /proc/cpuinfo
model name : Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz
% perf stat ../direct-gcc48
Performance counter stats for '../direct-gcc48':
238.146900 task-clock (msec)
37 context-switches
0 cpu-migrations
42 page-faults
689162737 cycles
403352479 stalled-cycles-frontend
<not supported> stalled-cycles-backend
430913321 instructions
210172241 branches
14205738 branch-misses
0.242429416 seconds time elapsed
% perf stat ./direct-gcc54
Performance counter stats for './direct-gcc54':
120.812507 task-clock (msec)
0 context-switches
0 cpu-migrations
41 page-faults
355605784 cycles
170213145 stalled-cycles-frontend
<not supported> stalled-cycles-backend
380562594 instructions
160106383 branches
9808 branch-misses
0.121333298 seconds time elapsed
Haswell
% grep -m1 'model name' /proc/cpuinfo
model name : Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz
% perf stat ./direct
Performance counter stats for './direct':
159.226456 task-clock:u (msec)
0 context-switches:u
0 cpu-migrations:u
35 page-faults:u
321780650 cycles:u
380085245 instructions:u
160015808 branches:u
5206 branch-misses:u
0.159844405 seconds time elapsed
% perf stat ../direct-gcc48
Performance counter stats for '../direct-gcc48':
205.179841 task-clock:u (msec)
0 context-switches:u
0 cpu-migrations:u
36 page-faults:u
448041978 cycles:u
430085324 instructions:u
210015836 branches:u
4887 branch-misses:u
0.206141759 seconds time elapsed
% perf stat ../direct-gcc54
Performance counter stats for '../direct':
158.532437 task-clock:u (msec)
0 context-switches:u
0 cpu-migrations:u
35 page-faults:u
315471369 cycles:u
380085288 instructions:u
160015810 branches:u
6829 branch-misses:u
0.159275797 seconds time elapsed
Skylake
% grep -m1 'model name' /proc/cpuinfo
model name : Intel(R) Xeon(R) CPU E3-1245 v5 @ 3.50GHz
% perf stat ./direct
Performance counter stats for './direct':
84.458565 task-clock (msec)
0 context-switches
0 cpu-migrations
38 page-faults
300759565 cycles
380503237 instructions
160093203 branches
9349 branch-misses
0.084794713 seconds time elapsed
% perf stat ../direct-gcc54
Performance counter stats for '../direct':
101.940704 task-clock (msec)
0 context-switches
0 cpu-migrations
37 page-faults
361064330 cycles
380540900 instructions
160100883 branches
18006 branch-misses
0.102305561 seconds time elapsed
訂正: 初出の記事ではSkylakeの値が-O3にしたものになっていました。-Oだと以上の通りです。
考察
所要時間はCPUの周波数も影響するのでその分は差し引いてみてくださいね。（本当はTurbo Boostオフにするべきなんだけど、手元のマシンじゃないんだゴメンな……）
考察と言ってもそこまで詳しいわけではないので実のあることは言えないのですが、今でもその進化が続いていることは見ればわかるでしょう。また、分岐予測に詳しい人ほど最近のIntel CPUの分岐予測的中率には驚かれるのではないかと思いました。
まとめ
あんまり賢い解説もないまま締めに入りますが、あんまり最近のIntel CPUの分岐予測について言及した記事って英語含めてもないと思うので、これで盛り上がって誰か解説してくれるといいなと思います！
追記
Sandy Bridgeが著しく悪かったのはgcc5.4以降が賢いからっぽい。
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
000000000040052d <main>:
40052d: 48 8b 35 2c 0b 20 00 mov 0x200b2c(%rip),%rsi # 601060 <prog.1723>
400534: 48 89 f2 mov %rsi,%rdx
400537: b9 80 96 98 00 mov $0x989680,%ecx
40053c: b8 68 10 60 00 mov $0x601068,%eax
400541: ff e2 jmpq *%rdx
400543: 48 8b 10 mov (%rax),%rdx
400546: 48 8d 40 08 lea 0x8(%rax),%rax
40054a: eb f5 jmp 400541 <main+0x14>
40054c: 48 8b 10 mov (%rax),%rdx
40054f: 48 8d 40 08 lea 0x8(%rax),%rax
400553: eb ec jmp 400541 <main+0x14>
400555: 48 8b 10 mov (%rax),%rdx
400558: 48 8d 40 08 lea 0x8(%rax),%rax
40055c: eb e3 jmp 400541 <main+0x14>
40055e: 48 8b 10 mov (%rax),%rdx
400561: 48 8d 40 08 lea 0x8(%rax),%rax
400565: eb da jmp 400541 <main+0x14>
400567: 48 8b 10 mov (%rax),%rdx
40056a: 48 8d 40 08 lea 0x8(%rax),%rax
40056e: eb d1 jmp 400541 <main+0x14>
400570: 85 c9 test %ecx,%ecx
400572: 7e 0d jle 400581 <main+0x54>
400574: 83 e9 01 sub $0x1,%ecx
400577: 48 89 f2 mov %rsi,%rdx
40057a: b8 68 10 60 00 mov $0x601068,%eax
40057f: eb c0 jmp 400541 <main+0x14>
400581: 48 83 ec 08 sub $0x8,%rsp
400585: bf 00 00 00 00 mov $0x0,%edi
40058a: e8 a1 fe ff ff callq 400430 <exit@plt>
40058f: 90 nop
% gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.2) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
0000000000400526 <main>: [37/1887]
400526: 48 8b 35 33 0b 20 00 mov 0x200b33(%rip),%rsi # 601060 <prog.1832>
40052d: 48 89 f2 mov %rsi,%rdx
400530: b9 80 96 98 00 mov $0x989680,%ecx
400535: b8 68 10 60 00 mov $0x601068,%eax
40053a: eb 07 jmp 400543 <main+0x1d>
40053c: 48 8b 10 mov (%rax),%rdx
40053f: 48 8d 40 08 lea 0x8(%rax),%rax
400543: ff e2 jmpq *%rdx
400545: 48 8b 10 mov (%rax),%rdx
400548: 48 8d 40 08 lea 0x8(%rax),%rax
40054c: eb f5 jmp 400543 <main+0x1d>
40054e: 48 8b 10 mov (%rax),%rdx
400551: 48 8d 40 08 lea 0x8(%rax),%rax
400555: eb ec jmp 400543 <main+0x1d>
400557: 48 8b 10 mov (%rax),%rdx
40055a: 48 8d 40 08 lea 0x8(%rax),%rax
40055e: eb e3 jmp 400543 <main+0x1d>
400560: 48 8b 10 mov (%rax),%rdx
400563: 48 8d 40 08 lea 0x8(%rax),%rax
400567: eb da jmp 400543 <main+0x1d>
400569: 85 c9 test %ecx,%ecx
40056b: 7e 0d jle 40057a <main+0x54>
40056d: 83 e9 01 sub $0x1,%ecx
400570: 48 89 f2 mov %rsi,%rdx
400573: b8 68 10 60 00 mov $0x601068,%eax
400578: eb c9 jmp 400543 <main+0x1d>
40057a: 48 83 ec 08 sub $0x8,%rsp
40057e: bf 00 00 00 00 mov $0x0,%edi
400583: e8 88 fe ff ff callq 400410 <exit@plt>
400588: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
40058f: 00
追記2
かと思われたが、HaswellだとGCC4.8で作ったバイナリでも分岐予測ミスは0.00%だった。なお、GCC4.8バイナリをIvy Bridgeマシンで実行するとSandyと大差ない結果なので、分岐予測能力はSandyでもそれなりにすごくて、Haswellはもっとすごいってことかな。
追記3
なんか前にやろうとしてできなかった気がしたんだけど、今改めてGCCのマニュアル見たら-fprofile-generateつけて-fprofile-useつけるだけだった。
% perf stat ./direct
Performance counter stats for './direct':
121.760309 task-clock (msec) # 0.993 CPUs utilized
2 context-switches # 0.016 K/sec
0 cpu-migrations # 0.000 K/sec
42 page-faults # 0.345 K/sec
353933863 cycles # 2.907 GHz
167429077 stalled-cycles-frontend # 47.31% frontend cycles idle
<not supported> stalled-cycles-backend
380553084 instructions # 1.08 insns per cycle
# 0.44 stalled cycles per insn
160104472 branches # 1314.915 M/sec
7542 branch-misses # 0.00% of all branches
0.122630111 seconds time elapsed
0000000000400526 <main>:
400526: 48 8b 0d 33 0b 20 00 mov 0x200b33(%rip),%rcx # 601060 <prog.1832>
40052d: 48 89 ca mov %rcx,%rdx
400530: be 80 96 98 00 mov $0x989680,%esi
400535: b8 68 10 60 00 mov $0x601068,%eax
40053a: eb 07 jmp 400543 <main+0x1d>
40053c: 48 8b 10 mov (%rax),%rdx
40053f: 48 8d 40 08 lea 0x8(%rax),%rax
400543: ff e2 jmpq *%rdx
400545: 48 8b 10 mov (%rax),%rdx
400548: 48 8d 40 08 lea 0x8(%rax),%rax
40054c: eb f5 jmp 400543 <main+0x1d>
40054e: 48 8b 10 mov (%rax),%rdx
400551: 48 8d 40 08 lea 0x8(%rax),%rax
400555: eb ec jmp 400543 <main+0x1d>
400557: 48 8b 10 mov (%rax),%rdx
40055a: 48 8d 40 08 lea 0x8(%rax),%rax
40055e: eb e3 jmp 400543 <main+0x1d>
400560: 48 8b 10 mov (%rax),%rdx
400563: 48 8d 40 08 lea 0x8(%rax),%rax
400567: eb da jmp 400543 <main+0x1d>
400569: 85 f6 test %esi,%esi
40056b: 7e 0d jle 40057a <main+0x54>
40056d: 83 ee 01 sub $0x1,%esi
400570: 48 89 ca mov %rcx,%rdx
400573: b8 68 10 60 00 mov $0x601068,%eax
400578: eb c9 jmp 400543 <main+0x1d>
40057a: 48 83 ec 08 sub $0x8,%rsp
40057e: bf 00 00 00 00 mov $0x0,%edi
400583: e8 88 fe ff ff callq 400410 <exit@plt>
400588: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
40058f: 00
あんまかわりませんね。
ちなみに-O3だと以下のような調子なので、最適化レベルを上げると意味がある模様。
% gcc -O3 -fomit-frame-pointer direct.c -o direct
direct.c:4:1: warning: return type defaults to 'int' [-Wimplicit-int]
main()
^
direct.c: In function 'main':
direct.c:32:3: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
exit(0);
^
direct.c:32:3: warning: incompatible implicit declaration of built-in function 'exit'
direct.c:32:3: note: include '<stdlib.h>' or provide a declaration of 'exit'
# 1471360659 0:17:39 naruse@tk2-243-31075:~/threading
% perf stat ./direct
Performance counter stats for './direct':
46.157782 task-clock (msec) # 0.980 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
41 page-faults # 0.888 K/sec
135493298 cycles # 2.935 GHz
49319786 stalled-cycles-frontend # 36.40% frontend cycles idle
<not supported> stalled-cycles-backend
320446132 instructions # 2.37 insns per cycle
# 0.15 stalled cycles per insn
110085385 branches # 2384.980 M/sec
6551 branch-misses # 0.01% of all branches
0.047097047 seconds time elapsed
0000000000400430 <main>:
400430: 48 8b 35 29 0c 20 00 mov 0x200c29(%rip),%rsi # 601060 <prog.1832>
400437: b9 80 96 98 00 mov $0x989680,%ecx
40043c: b8 68 10 60 00 mov $0x601068,%eax
400441: ff e6 jmpq *%rsi
400443: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
400448: 85 c9 test %ecx,%ecx
40044a: 7e 64 jle 4004b0 <main+0x80>
40044c: 83 e9 01 sub $0x1,%ecx
40044f: b8 68 10 60 00 mov $0x601068,%eax
400454: ff e6 jmpq *%rsi
400456: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40045d: 00 00 00
400460: 48 8b 10 mov (%rax),%rdx
400463: 48 83 c0 08 add $0x8,%rax
400467: ff e2 jmpq *%rdx
400469: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400470: 48 8b 10 mov (%rax),%rdx
400473: 48 83 c0 08 add $0x8,%rax
400477: ff e2 jmpq *%rdx
400479: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400480: 48 8b 10 mov (%rax),%rdx
400483: 48 83 c0 08 add $0x8,%rax
400487: ff e2 jmpq *%rdx
400489: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400490: 48 8b 10 mov (%rax),%rdx
400493: 48 83 c0 08 add $0x8,%rax
400497: ff e2 jmpq *%rdx
400499: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
4004a0: 48 8b 10 mov (%rax),%rdx
4004a3: 48 83 c0 08 add $0x8,%rax
4004a7: ff e2 jmpq *%rdx
4004a9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
4004b0: 48 83 ec 08 sub $0x8,%rsp
4004b4: 31 ff xor %edi,%edi
4004b6: e8 55 ff ff ff callq 400410 <exit@plt>
4004bb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
% gcc -O3 -fprofile-use -fomit-frame-pointer direct.c -o direct
direct.c:4:1: warning: return type defaults to 'int' [-Wimplicit-int]
main()
^
direct.c: In function 'main':
direct.c:32:3: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
exit(0);
^
direct.c:32:3: warning: incompatible implicit declaration of built-in function 'exit'
direct.c:32:3: note: include '<stdlib.h>' or provide a declaration of 'exit'
# 1471360636 0:17:16 naruse@tk2-243-31075:~/threading
% perf stat ./direct
Performance counter stats for './direct':
46.108716 task-clock (msec) # 0.981 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
41 page-faults # 0.889 K/sec
123812228 cycles # 2.685 GHz
39859092 stalled-cycles-frontend # 32.19% frontend cycles idle
<not supported> stalled-cycles-backend
320466395 instructions # 2.59 insns per cycle
# 0.12 stalled cycles per insn
110090077 branches # 2387.620 M/sec
6079 branch-misses # 0.01% of all branches
0.046992565 seconds time elapsed
0000000000400430 <main>:
400430: 48 8b 0d 29 0c 20 00 mov 0x200c29(%rip),%rcx # 601060 <prog.1832>
400437: be 80 96 98 00 mov $0x989680,%esi
40043c: b8 68 10 60 00 mov $0x601068,%eax
400441: ff e1 jmpq *%rcx
400443: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
400448: 48 8b 10 mov (%rax),%rdx
40044b: 48 83 c0 08 add $0x8,%rax
40044f: ff e2 jmpq *%rdx
400451: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
400458: 4c 8b 18 mov (%rax),%r11
40045b: 48 83 c0 08 add $0x8,%rax
40045f: 41 ff e3 jmpq *%r11
400462: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
400468: 85 f6 test %esi,%esi
40046a: 7e 3e jle 4004aa <main+0x7a>
40046c: 83 ee 01 sub $0x1,%esi
40046f: b8 68 10 60 00 mov $0x601068,%eax
400474: ff e1 jmpq *%rcx
400476: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40047d: 00 00 00
400480: 4c 8b 00 mov (%rax),%r8
400483: 48 83 c0 08 add $0x8,%rax
400487: 41 ff e0 jmpq *%r8
40048a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
400490: 4c 8b 08 mov (%rax),%r9
400493: 48 83 c0 08 add $0x8,%rax
400497: 41 ff e1 jmpq *%r9
40049a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
4004a0: 4c 8b 10 mov (%rax),%r10
4004a3: 48 83 c0 08 add $0x8,%rax
4004a7: 41 ff e2 jmpq *%r10
4004aa: 50 push %rax
4004ab: 31 ff xor %edi,%edi
4004ad: e8 5e ff ff ff callq 400410 <exit@plt>
4004b2: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
4004b9: 00 00 00
4004bc: 0f 1f 40 00 nopl 0x0(%rax)
