LoginSignup
73
47

More than 5 years have passed since last update.

@NaOHaq(Naoyuki MORITA)

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

Last updated at Posted at 2019-05-20

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

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

発端はこのツイートを見かけたことでした。

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

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

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

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

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

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

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

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;
      }
  }

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

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

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

$ /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コマンド。

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

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 にして、コードを比較してみます。

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

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

まとめ

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

73
47
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
73
47