読者です 読者をやめる 読者になる 読者になる

y_uti のブログ

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

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 では人間が意識して書いてあげないといけないというのは、ちょっと皮肉な話ですね。

*1:今回の記事については CentOS 6.5 の yum でインストールされる PHP 5.3.3 で確認しています。

*2:Google で「PHP 最適化」「PHP optimization」で検索した結果より。