PHP プログラムの最適化あれこれ
先日から PHP のコードの性能について記事を書いていますが、今回もそういった内容です。
まず、ループカウンタの操作についてです。
以下のようなコードを考えます。計測用のプログラムなので計算に意味はありません。
<?php $result = 0; for ($n = 0; $n < 5000; $n++) { for ($i = 0; $i < 10000; $i++) { $result += $i; } } echo $result . "\n";
実行結果は、私の環境では以下のようになりました*1。
$ time php prog1a.php 249975000000 real 0m2.760s user 0m2.742s sys 0m0.016s
ループカウンタのインクリメントについては、$i++ ではなく ++$i を使えというのが定石のようです*2。早速、そのように書き換えてみます。
<?php $result = 0; for ($n = 0; $n < 5000; ++$n) { for ($i = 0; $i < 10000; ++$i) { $result += $i; } } echo $result . "\n";
何が違うのか確認するため、vld を利用してバイトコードを表示させてみました。最初の $i++ 版では以下になります。
number of ops: 19
compiled vars: !0 = $result, !1 = $n, !2 = $i
line # * op fetch ext return operands
---------------------------------------------------------------------------------
3 0 > ASSIGN !0, 0
4 1 ASSIGN !1, 0
2 > IS_SMALLER ~2 !1, 5000
3 > JMPZNZ 7 ~2, ->16
4 > POST_INC ~3 !1
5 FREE ~3
6 > JMP ->2
(以下省略)これに対して、++$i のように書くと以下のようになります。
number of ops: 17
compiled vars: !0 = $result, !1 = $n, !2 = $i
line # * op fetch ext return operands
---------------------------------------------------------------------------------
3 0 > ASSIGN !0, 0
4 1 ASSIGN !1, 0
2 > IS_SMALLER ~2 !1, 5000
3 > JMPZNZ 6 ~2, ->14
4 > PRE_INC !1
5 > JMP ->2
(以下省略)$i++ と書いた場合には POST_INC, FREE という二命令のところが ++$i と書くことで PRE_INC 一命令になっています。バイトコード命令の個数だけで実行時間を議論するのは乱暴ですが、まあ後者の方が速そうな気はします。
ところで、上記のバイトコード命令列のなかで IS_SMALLER が気になります。昔は、ループを逆順に回すことで 0 との比較にするというようなテクニックもあったとか。以下のようにプログラムを変更して確認してみます。なお最初のプログラムとは $i が一つずれているので計算結果は一致しません。
<?php $result = 0; for ($n = 5000; $n; --$n) { for ($i = 10000; $i; --$i) { $result += $i; } } echo $result. "\n";
この実行時間は (real) 0m1.941s と、ずいぶん速くなりました。バイトコード命令を表示させてみると、確かにさらに一命令削減されています。
number of ops: 15
compiled vars: !0 = $result, !1 = $n, !2 = $i
line # * op fetch ext return operands
---------------------------------------------------------------------------------
3 0 > ASSIGN !0, 0
4 1 ASSIGN !1, 5000
2 > > JMPZNZ 5 !1, ->12
3 > PRE_DEC !1
4 > JMP ->2
(以下省略)次の話題は標準入力からのファイル読み込みです。標準入力から 100 万行読み込んで合計を求めるという、これまた意味のない例を考えます。
<?php $result = 0; for ($i = 1000000; $i; --$i) { $result += (int) fgets(STDIN); } echo $result . "\n";
サンプルデータは seq 1000000 として適当に作っておき、実行させてみます。
$ time php prog2a.php <data.txt 500000500000 real 0m0.425s user 0m0.267s sys 0m0.157s
バイトコード命令を見てみます。ループ中で FETCH_CONSTANT している様子がわかるでしょうか。気に入りません。
number of ops: 14
compiled vars: !0 = $result, !1 = $i
line # * op fetch ext return operands
---------------------------------------------------------------------------------
3 0 > ASSIGN !0, 0
4 1 ASSIGN !1, 1000000
2 > > JMPZNZ 5 !1, ->11
3 > PRE_DEC !1
4 > JMP ->2
5 5 > FETCH_CONSTANT ~3 'STDIN'
6 SEND_VAL ~3
7 DO_FCALL 1 $4 'fgets'
8 CAST ~5 $4
9 ASSIGN_ADD 0 !0, ~5
6 10 > JMP ->3
8 11 > CONCAT ~7 !0, '%0A'
12 ECHO ~7
9 13 > RETURN 1そこで STDIN をループの外に出してみます。
<?php $fh = STDIN; $result = 0; for ($i = 1000000; $i; --$i) { $result += (int) fgets($fh); } echo $result . "\n";
こうするだけで、実行時間は以下のようになりました。元が 0.425 秒なので結構違うものですね。
$ time php prog2b.php <data.txt 500000500000 real 0m0.325s user 0m0.306s sys 0m0.018s
バイトコード命令は以下のようになっています。変数を導入しているので全体の命令数は増えていますが、ループ内は FETCH_CONSTANT, SEND_VAL の二命令が SEND_VAR 一命令に削減されています。
number of ops: 15
compiled vars: !0 = $fh, !1 = $result, !2 = $i
line # * op fetch ext return operands
---------------------------------------------------------------------------------
3 0 > FETCH_CONSTANT ~0 'STDIN'
1 ASSIGN !0, ~0
4 2 ASSIGN !1, 0
5 3 ASSIGN !2, 1000000
4 > > JMPZNZ 7 !2, ->12
5 > PRE_DEC !2
6 > JMP ->4
6 7 > SEND_VAR !0
8 DO_FCALL 1 $5 'fgets'
9 CAST ~6 $5
10 ASSIGN_ADD 0 !1, ~6
7 11 > JMP ->5
9 12 > CONCAT ~8 !1, '%0A'
13 ECHO ~8
10 14 > RETURN 1最後は演算子強度低減 (strength reduction) です。ビットベクトルを扱うときなど、このように整数の除算を行う場面があります。
$result = 0;
for ($n = 5000; $n; --$n) {
for ($i = 10000; $i; --$i) {
$result += (int) ($i / 32);
}
}
echo $result . "\n";
PHP では整数同士の除算でも結果は実数になるので、結果を整数にキャストしています。このコードを実行すると以下のようになります。
$ time php prog3a.php 7789080000 real 0m3.619s user 0m3.421s sys 0m0.194s
これを次のようにシフト演算に変更してみます。
<?php $result = 0; for ($n = 5000; $n; --$n) { for ($i = 10000; $i; --$i) { $result += $i >> 5; } } echo $result . "\n";
このように変更するだけで、大幅に高速化されました。
$ time php prog3b.php 7789080000 real 0m2.495s user 0m2.434s sys 0m0.058s
さて、ここに述べてきたような最適化ですが、同じことを C で書くなら、gcc に任せることができます。
除算で計算するプログラムを prog3a.c とします。
#include <stdio.h> int main() { int n, i; int result = 0; for (n = 5000; n > 0; --n) { for (i = 10000; i > 0; --i) { result += i / 32; } } printf("%d\n", result); return 0; }
シフト演算に「最適化」したプログラムを prog3b.c とします。
#include <stdio.h> int main() { int n, i; int result = 0; for (n = 5000; n > 0; --n) { for (i = 10000; i > 0; --i) { result += i >> 5; } } printf("%d\n", result); return 0; }
それぞれをコンパイルしてアセンブリを出力してみると、この程度のことは gcc の最適化器が勝手に処理してくれることがよくわかります。
$ gcc -O3 -S prog3a.c $ gcc -O3 -S prog3b.c $ diff prog3a.s prog3b.s 1c1 < .file "prog3a.c" --- > .file "prog3b.c"
C ではコンパイラ任せにできることが、PHP では人間が意識して書いてあげないといけないというのは、ちょっと皮肉な話ですね。
