[お詫び] 色々比較がガバガバだったので、ある程度条件を揃えて比較し直したものを後半に追記しました。
キャッシュの恩恵を体感したい
発端はこのツイートを見かけたことでした。
メモリアクセスが速く見えるのはキャッシュのおかげ、本当にそう（知識として習ったことがあっても実際にCache Disableにしてアプリケーションを動かしたことがある人は少ないと思う。実際オフにするとめっちゃ遅くてびっくりする。）
— hikalium (@hikalium) 2019年5月19日
実には、頑張ってプロセッサのキャッシュをdisableにしなくても、キャッシュのおかげでプログラムがどのくらい速くなっているかを体感することは可能です。
2次元に配置されたデータへのアクセス
現在の多くの計算機では、プロセッサのキャッシュメモリは「メモリアクセスはシーケンシャルに行われることが多いはず」という前提で作られています。なので、その前提が崩れるとキャッシュの効果がほとんどなくなるどころか、かえってパフォーマンスが低下したりします。
画像などの2次元データに対する処理が典型的ですが、画像を横方向にスキャンしながら処理するのと、縦方向にスキャンしながら処理するのとでは、ときに想像しがたいほどの性能差が生じます。
実際にコードを書いて実験してみました。
https://gist.github.com/naohaq/07582d1eb3dabb93361831e6df4c5cc2
2次元に配置されたuint8_t型のデータを1つずつインクリメントするだけですが、これを2通りのアクセス順で実行しています。
一方は横方向へのアクセスが連続的になるようなアクセス順、
for (int32_t y=0; y<h; y+=1) {
for (int32_t x=0; x<w; x+=1) {
pixbuf[y*w + x] += 1;
}
}
もう一方は縦方向へのアクセスが連続的になるようなアクセス順です。
for (int32_t x=0; x<w; x+=1) {
for (int32_t y=0; y<h; y+=1) {
pixbuf[y*w + x] += 1;
}
}
実験結果
実験した環境は、
- CPU: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
- L1キャッシュ 32KiB/コア, L2キャッシュ 256KiB/コア, L3キャッシュ 1.5MiB/コア
- Memory: 16GB
- OS: Linux 4.19.0-4-amd64 #1 SMP Debian 4.19.28-2 (2019-03-15) x86_64 GNU/Linux
- コンパイラ: gcc 8.3.0
まず横方向へ連続的にアクセスするコードを実行してみます。
$ /usr/bin/time ./horizontal
................................................................................................................................
Elapsed time: 0.337
0.34user 0.00system 0:00.34elapsed 100%CPU (0avgtext+0avgdata 34236maxresident)k
0inputs+0outputs (0major+600minor)pagefaults 0swaps
0.34秒で実行が終了しました。
次は縦方向です。
$ /usr/bin/time ./vertical
...
あれ?(汗)
なんかめちゃくちゃ遅いです。とりあえず終わるまで待ちましょう。
$ /usr/bin/time ./vertical
................................................................................................................................
Elapsed time: 109.541
108.25user 0.10system 1:49.55elapsed 98%CPU (0avgtext+0avgdata 34284maxresident)k
0inputs+0outputs (0major+600minor)pagefaults 0swaps
0.34秒で終わったはずの処理に、約110秒かかりました。実に300倍以上の速度差です。
(2019/05/20)ここから追記
流石に差があり過ぎるのでちょっと真面目に調べてみました。
まずperfコマンド。
# perf stat -d ./horizontal
................................................................................................................................
Elapsed time: 0.328
Performance counter stats for './horizontal':
332.61 msec task-clock # 0.998 CPUs utilized
1 context-switches # 3.012 M/sec
0 cpu-migrations # 0.000 K/sec
584 page-faults # 1759.036 M/sec
796,318,400 cycles # 2398549.398 GHz
1,620,128,707 instructions # 2.03 insn per cycle
270,765,443 branches # 815558563.253 M/sec
537,741 branch-misses # 0.20% of all branches
269,453,224 L1-dcache-loads # 811606096.386 M/sec
68,209,762 L1-dcache-load-misses # 25.31% of all L1-dcache hits
25,171,068 LLC-loads # 75816469.880 M/sec
13,121,946 LLC-load-misses # 52.13% of all LL-cache hits
# perf stat -d ./vertical
................................................................................................................................
Elapsed time: 113.867
Performance counter stats for './vertical':
113,844.14 msec task-clock # 1.000 CPUs utilized
271 context-switches # 2.380 M/sec
0 cpu-migrations # 0.000 K/sec
584 page-faults # 5.130 M/sec
101,811,970,482 cycles # 894311.255 GHz
21,579,584,738 instructions # 0.21 insn per cycle
4,314,164,817 branches # 37895407.900 M/sec
1,577,318 branch-misses # 0.04% of all branches
4,324,979,654 L1-dcache-loads # 37990404.887 M/sec
9,530,336,462 L1-dcache-load-misses # 220.36% of all L1-dcache hits
4,575,175,715 LLC-loads # 40188114.569 M/sec
4,416,737,363 LLC-load-misses # 96.54% of all LL-cache hits
vertical の発行命令数(instructions)が 215億命令に対して horizontal は16億命令で明らかに1桁少ない……。objdump -d horizontal でアセンブリコードを見てみると
11a8: f3 0f 6f 00 movdqu (%rax),%xmm0
11ac: 48 83 c0 10 add $0x10,%rax
11b0: 66 0f fc c1 paddb %xmm1,%xmm0
11b4: 0f 11 40 f0 movups %xmm0,-0x10(%rax)
11b8: 48 39 f8 cmp %rdi,%rax
11bb: 75 eb jne 11a8 <main+0xe8>
11bd: 45 39 f5 cmp %r14d,%r13d
11c0: 0f 84 fa 00 00 00 je 12c0 <main+0x200>
11c6: 44 89 f0 mov %r14d,%eax
11c9: 48 63 f8 movslq %eax,%rdi
最内ループの処理がSSE命令で最適化されています。paddb はSSE2の命令で、128bit長のレジスタ同士を16個の8bitデータとみなして加算します。-O3 はやりすぎた……。
最適化オプションを -O1 にして、コードを比較してみます。
12b2: 48 01 f8 add %rdi,%rax
12b5: 83 c1 01 add $0x1,%ecx
12b8: 41 39 cc cmp %ecx,%r12d
12bb: 74 19 je 12d6 <main+0xe6>
12bd: 48 89 c2 mov %rax,%rdx
12c0: 4a 8d 34 28 lea (%rax,%r13,1),%rsi
12c4: 85 ed test %ebp,%ebp
12c6: 7e ea jle 12b2 <main+0xc2>
12c8: 80 02 01 addb $0x1,(%rdx)
12cb: 48 83 c2 01 add $0x1,%rdx
12cf: 48 39 f2 cmp %rsi,%rdx
12d2: 75 f4 jne 12c8 <main+0xd8>
12d4: eb dc jmp 12b2 <main+0xc2>
12b4: 48 83 c0 01 add $0x1,%rax
12b8: 4c 39 e8 cmp %r13,%rax
12bb: 74 1b je 12d8 <main+0xe8>
12bd: 48 89 c2 mov %rax,%rdx
12c0: b9 00 00 00 00 mov $0x0,%ecx
12c5: 85 ed test %ebp,%ebp
12c7: 7e eb jle 12b4 <main+0xc4>
12c9: 80 02 01 addb $0x1,(%rdx)
12cc: 83 c1 01 add $0x1,%ecx
12cf: 48 01 f2 add %rsi,%rdx
12d2: 39 cd cmp %ecx,%ebp
12d4: 75 f3 jne 12c9 <main+0xd9>
12d6: eb dc jmp 12b4 <main+0xc4>
とりあえず最内ループの uint8_t 型配列の要素に対する加算はどっちも addb 1命令になっているようです。
もう一度 perf で実行してみます。
# perf stat -d ./horizontal
................................................................................................................................
Elapsed time: 1.803
Performance counter stats for './horizontal':
1,807.77 msec task-clock # 1.000 CPUs utilized
3 context-switches # 1.660 M/sec
0 cpu-migrations # 0.000 K/sec
583 page-faults # 322.634 M/sec
5,550,945,622 cycles # 3071912.353 GHz
17,190,036,098 instructions # 3.10 insn per cycle
4,297,609,139 branches # 2378311643.055 M/sec
545,277 branch-misses # 0.01% of all branches
4,296,486,153 L1-dcache-loads # 2377690178.749 M/sec
68,280,473 L1-dcache-load-misses # 1.59% of all L1-dcache hits
83,020 LLC-loads # 45943.553 M/sec
10,657 LLC-load-misses # 12.84% of all LL-cache hits
# perf stat -d ./vertical
................................................................................................................................
Elapsed time: 113.160
Performance counter stats for './vertical':
113,162.17 msec task-clock # 1.000 CPUs utilized
42 context-switches # 0.371 M/sec
0 cpu-migrations # 0.000 K/sec
583 page-faults # 5.152 M/sec
100,947,266,080 cycles # 892059.756 GHz
21,588,849,896 instructions # 0.21 insn per cycle
4,317,629,703 branches # 38154413.169 M/sec
1,641,850 branch-misses # 0.04% of all branches
4,327,282,369 L1-dcache-loads # 38239712.704 M/sec
9,503,404,594 L1-dcache-load-misses # 219.62% of all L1-dcache hits
4,842,818,386 LLC-loads # 42795447.111 M/sec
4,767,750,184 LLC-load-misses # 98.45% of all LL-cache hits
まず、総発行命令数(instructions)は horizontal が172億命令、verticalが215億命令で桁は揃いました。最内ループの命令数が1個多い分だけverticalの方が少し延びています。
肝心のメモリアクセスはというと、キャッシュへの総アクセス回数はhorizontal、verticalともにほぼ43億回となりました。一方、キャッシュミスの回数はhorizontalが6800万回、verticcalが95億回で2桁程度の差になりました。verticalでキャッシュミスの回数がキャッシュアクセスの回数を上回っているのがどういう集計になっているのかは気になりますが、ひとまずここではおいておきます。
総合的な実行時間は horizontal が1.8秒、vertical が113秒で、ほぼキャッシュミス回数の比を反映しているように見えます。
まとめ
メモリアクセス順序はちゃんと考えてコードを書きましょう。
定量的な評価はきちんと条件をそろえて真面目におこないましょう……。