[追記あり]キャッシュメモリの恩恵をてっとりばやく体感する

[お詫び] 色々比較がガバガバだったので、ある程度条件を揃えて比較し直したものを後半に追記しました。

# キャッシュの恩恵を体感したい

発端はこのツイートを見かけたことでした。
<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">メモリアクセスが速く見えるのはキャッシュのおかげ、本当にそう（知識として習ったことがあっても実際にCache Disableにしてアプリケーションを動かしたことがある人は少ないと思う。実際オフにするとめっちゃ遅くてびっくりする。）</p>&mdash; hikalium (@hikalium) <a href="https://twitter.com/hikalium/status/1130137418198163456?ref_src=twsrc%5Etfw">2019年5月19日</a></blockquote>

実には、頑張ってプロセッサのキャッシュをdisableにしなくても、キャッシュのおかげでプログラムがどのくらい速くなっているかを体感することは可能です。

# 2次元に配置されたデータへのアクセス

現在の多くの計算機では、プロセッサのキャッシュメモリは「メモリアクセスはシーケンシャルに行われることが多いはず」という前提で作られています。なので、その前提が崩れるとキャッシュの効果がほとんどなくなるどころか、かえってパフォーマンスが低下したりします。

画像などの2次元データに対する処理が典型的ですが、画像を横方向にスキャンしながら処理するのと、縦方向にスキャンしながら処理するのとでは、ときに想像しがたいほどの性能差が生じます。

実際にコードを書いて実験してみました。
https://gist.github.com/naohaq/07582d1eb3dabb93361831e6df4c5cc2

2次元に配置された`uint8_t`型のデータを1つずつインクリメントするだけですが、これを2通りのアクセス順で実行しています。

一方は横方向へのアクセスが連続的になるようなアクセス順、

```c:cache_test.c
  for (int32_t y=0; y<h; y+=1) {
      for (int32_t x=0; x<w; x+=1) {
          pixbuf[y*w + x] += 1;
      }
  }
```

もう一方は縦方向へのアクセスが連続的になるようなアクセス順です。

```c:cache_test.c
  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

まず横方向へ連続的にアクセスするコードを実行してみます。

```console
$ /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秒で実行が終了しました。

次は縦方向です。

```console
$ /usr/bin/time ./vertical
...
```

あれ?(汗)
なんかめちゃくちゃ遅いです。とりあえず終わるまで待ちましょう。

```console
$ /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コマンド](http://int.main.jp/txt/perf/)。

```console:horizontal
# 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
```

```console:vertical
# 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` でアセンブリコードを見てみると

```text: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](https://www.officedaytime.com/tips/simdimg/binop.php?f=paddb) はSSE2の命令で、128bit長のレジスタ同士を16個の8bitデータとみなして加算します。`-O3` はやりすぎた……。

最適化オプションを `-O1` にして、コードを比較してみます。

```text:horizontal
    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>
```

```text:vertical
    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` で実行してみます。

```console:horizontal
# 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

```

```console:vertical
# 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秒で、ほぼキャッシュミス回数の比を反映しているように見えます。

# まとめ
~~メモリアクセス順序はちゃんと考えてコードを書きましょう。~~
定量的な評価はきちんと条件をそろえて真面目におこないましょう……。