PHPコードでキャッシュについて学んでみる

この投稿はブログからの転載になります。

次のコードで速いのはどちらだと思いますか？

Code A

<?php
$a = [[]];
for ($i = 0; $i < 1000; ++$i) {
    for ($j = 0; $j < 1000; ++$j) {
        $a[$i][$j] = 1;
    }
}

Code B

<?php
$a = [[]];
for ($i = 0; $i < 1000; ++$i) {
    for ($j = 0; $j < 1000; ++$j) {
        // flipped!
        $a[$j][$i] = 1;
    }
}

この記事を読めばなんとなくわかるようになると思います。

はじめに

PHPや他のスクリプト系の言語はC言語と違ってメモリの管理について気にすることはほとんどないと思います。

C言語ではメモリを確保するところから解放するところまですべて面倒を見る必要がありますが新しい言語にはガベージコレクタが実装されているので確保したヒープメモリは変数への参照がなくなった時点で解放されます。

変数の値はどこにしまってあるのか

変数の値はどんな言語であろうとメモリに格納されます。メモリに乗り切らない場合はディスクに保存されます。メモリは複数の領域に別れており、

--------- 0xffffffff
 stack
---------
 heap
---------
 static
---------
 code
--------- 0x00000000

という感じになっています。右の16進数はメモリの場所を示すアドレスです。ここでは変数の値はあるアドレスの示す場所に格納されるということがわかれば大丈夫です。

CPUにとってボトルネックとなる処理はメモリへのアクセスとディスクへのアクセスです。メモリの読み込みと書き込み速度は近年急速に早くなったため、今メモリへのアクセスする速度を気にしている人はWeb界隈では特にいないと思います。

キャッシュの登場

パソコンを買うとCPUのスペックのところにL1キャッシュやL2キャッシュという表記を見たことがあると思います。

実はCPUはキャッシュを持っていて、メモリの内容をキャッシュしています。これがL1キャッシュやL2キャッシュです。CPUがメモリへアクセスしようとするときに、キャッシュにすでに値があればメモリへアクセスせずキャッシュの値を利用します。これは書き込みの時でも同じです（write backなら）。

しかし、キャッシュは高速にアクセスできる代わりに非常に高価なので3MBや4MBほどしか持っていません。なのでCPUはあるルールに従ってキャッシュを更新していきます。

キャッシュの特徴

キャッシュは次のことを想定しています。

• spatial locality
• temporal locality

まずspatial localityとは一度アクセスした変数が格納されているアドレスに近いアドレスにある変数にアクセスする可能性が高いということです。例えば最初に出てきたCodeAのように配列の値は連続したアドレスに保存されるため（PHPは厳密にそうかどうかは微妙）一度配列の値にアクセスするとその周辺のアドレスの値全てをキャッシュに格納します。

次にtemporal localityとは一度アクセスしたアドレスには近いうちに再びアクセスする可能性が高いということです。コードを書くときに意識していると思いますが、一度定義した変数はその周辺で何度も使うことが多いと思います。なのでキャッシュを更新する際には最後にアクセスされたのがもっとも古いアドレスを新しくアクセスしたアドレスに置き換えます。

最初のコードを見てみる

まずCodeA,Bについて、自分のPC上（Macbook Pro Mid 2012, Intel Core i5, RAM 16GB）で実行した結果を示します。

$ php codeA.php 
0.061517953872681

$ php codeB.php 
0.12649202346802

なんと二倍も差が出ました！1000x1000の配列なんて普段あまりないとは思いますが、配列にアクセスする順番でこんなにも差が出るのは驚きだと思います。

では理由を考えてみましょう。

配列に一度アクセスするとspatial localityの考えによって、周囲のアドレスに格納されている値が決まったブロック単位でキャッシュされます。なのでCodeAでは一度配列にアクセスするとしばらくはアドレスが連続している配列の値を見に行っているのでメモリへのアクセスが少なく済んでいます。

一方、CodeBでは２次元配列を縦方向に走査しています。1000x1000の２次元配列は長さが1000000の１次元配列と見ることができます。なので毎回離れたアドレスの値にアクセスしに行ってしまっているので、キャッシュが利用されずメモリへのアクセス数が多くなってしまっています。

まとめ

PHPの簡単なコードを通してキャッシュがパフォーマンスに与える影響が分かったと思います。普段意識しないキャッシュについて少しだけ理解を深めてもらえていれば嬉しいです。また、今回C言語ではなくPHPを選択した理由はより多くの人が簡単に読めると思ったからです。

より理解を深めたければパタヘネを読むのが一番いいと思います。