PHP の配列の局所性
PHP で、整列済み配列を走査する処理を書いていたところ、メモリアクセスの局所性によると思われる速度低下が見られて面白かったので、記事にしてみます。
例として配列の総和を計算するコードを考えます。
<?php $n = intval(trim(fgets(STDIN))); $array = array(); for ($i = 0; $i < $n; $i++) { $array[] = intval(trim(fgets(STDIN))); } $begin = microtime(true); $result = 0; for ($k = 0; $k < 25; $k++) { for ($i = 0; $i < $n; $i++) { $result += $array[$i]; } } $end = microtime(true); print $result . "\n"; print ($end - $begin) . " sec.\n";
前半はデータ読み込み部なので本質ではありません。ファイルから $n 個の整数を読み込み、配列 $array に格納します。処理の本体は後半部分で、ここで $array の要素の総和を 25 回繰り返し計算します。この部分の所要時間を計測します。
データファイルとして 1 から 200,000 までの数値をシャッフルしたものを用意しました。まずは前述のコードを用いて、整列せずそのまま総和をとります。実行時間は以下のようになりました。
$ php prog1.php <data.txt 500002500000 0.43170785903931 sec.
次に、読み込んだ配列を整列してから同じ処理を行ってみます。$array に値を読み込んだ後に sort 関数で整列します。
$ diff prog1.php prog2.php 7c7,8 < --- > $begin0 = microtime(true); > sort($array); 17a19 > print ($begin - $begin0) . " sec.\n";
このコードを実行すると以下のようになりました。sort に 0.23 秒かかっていますが、その後の本体の処理に要する時間が 1.27 秒と、先ほどのプログラムの 3 倍近い時間がかかっています。
$ php prog2.php <data.txt 500002500000 0.23132014274597 sec. 1.2686989307404 sec.
さて、配列の各要素は互いに異なる整数値なので、次のように一見無駄なことをしても計算結果は同じになります。array_flip で配列のキーと値を交換して、それを ksort でキーの昇順に整列。さらに array_keys でキーの配列を得ています。全体として、sort 関数で整列したのと同じことになります。
$ diff prog2.php prog3.php 8c8,10 < sort($array); --- > $array = array_flip($array); > ksort($array); > $array = array_keys($array);
これを実行した結果が以下です。もちろん整列処理に要する時間は大幅に増えていますが、本体の計算時間は最初のプログラムと同程度になりました。
$ php prog3.php <data.txt 500002500000 0.31067204475403 sec. 0.45993399620056 sec.
この先は PHP のランタイムの実装を追うことになるのですが、どうやら array_keys の中で配列の再割当が発生し、その際に要素が綺麗に並べられるようです。
perf などを使ってキャッシュミスを調べるのが直接的だと思いますが、手元の VMware 上の linux では調べられないようなので、とりあえず $result への加算が発生する際のオペランドのアドレスを調べればよいかなと考え、PHP 5.5.6 の Zend/zend_operators.c にある add_function 関数に printf を挟んでみました。下記の 818 行目です。
816 switch (TYPE_PAIR(Z_TYPE_P(op1), Z_TYPE_P(op2))) { 817 case TYPE_PAIR(IS_LONG, IS_LONG): { 818 printf("%x %x\n", op1, op2); 819 long lval = Z_LVAL_P(op1) + Z_LVAL_P(op2);
これをビルドして実行してみると、こんな感じになりました。prog1 と prog3 では何となく綺麗に並んでいるのに対して prog2 は sort したままの状態なのでアドレスはぐちゃぐちゃです。
$ ./php prog1.php <data.txt | head -n 10 529f9650 529f9680 529f9650 529fa0f0 529f9650 529fa178 529f9650 529fa200 529f9650 529fc970 529f9650 529fc9f8 529f9650 529fca80 529f9650 529fcb08 529f9650 529fcb90 529f9650 529fcc18 $ ./php prog2.php <data.txt | head -n 10 d7e97a70 cfe9ce48 d7e97a70 cfcf5c18 d7e97a70 ceca74e0 d7e97a70 d016e070 d7e97a70 cf4c7ce0 d7e97a70 cff80168 d7e97a70 ced42b18 d7e97a70 d03846f0 d7e97a70 cf72fdf0 d7e97a70 d016b9a8 $ ./php prog3.php <data.txt | head -n 10 1e7c91e8 29530278 1e7c91e8 295301f0 1e7c91e8 29530168 1e7c91e8 295300e0 1e7c91e8 29530058 1e7c91e8 2952ffd0 1e7c91e8 2952ff48 1e7c91e8 2952fec0 1e7c91e8 2952fe38 1e7c91e8 2952fdb0