y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

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