y_uti のブログ

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

データを正しい型で扱うことによる高速化

PHP のようなスクリプト言語では型を意識せずにコードを書いてしまいがちですが、適切な型を付けることで処理速度を大きく改善できる場合があります。そりゃあそうだろうという話なのですが、実際に計測してみると予想以上に大きな効果があって驚きました。

たとえば以下のように、ファイルから配列に値を読み込んで算術演算を繰り返すような処理を考えます。

$ cat prog1.php
<?php
$arr = array();
while ($line = fgets(STDIN)) {
    $arr[] = trim($line);
}

$len = count($arr);
$result = 0;
for ($i = 0; $i < $len; $i++) {
    for ($j = 0; $j < $len; $j++) {
        $result -= $arr[$i] + $arr[$j];
    }
}
print $result . "\n";

5000 行のデータを作って実行してみると、手元の環境ではこのくらいの処理時間がかかりました。

$ for i in `seq 5000`; do echo $RANDOM; done >a.txt
$ time php prog1.php <a.txt
-817097990000

real    0m6.715s
user    0m6.587s
sys     0m0.116s

このプログラムで、配列 $arr に値を設定している部分を以下のように変更してみます。読み込んだ文字列を intval であらかじめ整数に変換したうえで、配列に格納します。

$ diff prog1.php prog2.php
5c5
<     $arr[] = trim($line);
---
>     $arr[] = intval(trim($line));

こちらのプログラムでは、同じデータに対して処理時間はこのようになりました。実行時間 (real) の比較では 58% に短縮されています。

$ time php prog2.php <a.txt
-817097990000

real    0m3.931s
user    0m3.861s
sys     0m0.067s

それぞれがどのように処理されているのか、PHPソースコードを眺めてみました。抜粋箇所は Zend/zend_operators.h の fast_add_function の一部です。オペランドの型を見て効率的な処理が選択されるようになっています。IS_LONG のほか、IS_DOUBLE の場合も高速に実行されるようです。抜粋箇所は __i386__ ですが、この後に __x86_64__ もあります。

static zend_always_inline int fast_add_function(zval *result, zval *op1, zval *op2 TSRMLS_DC)
{
        if (EXPECTED(Z_TYPE_P(op1) == IS_LONG)) {
                if (EXPECTED(Z_TYPE_P(op2) == IS_LONG)) {
#if defined(__GNUC__) && defined(__i386__)
                __asm__(

        ...

        }
        return add_function(result, op1, op2 TSRMLS_CC);
}

一方 prog1.php のように文字列のまま扱った場合は、Zend/zend_operators.c で定義されている add_function 関数が呼ばれます。add_function でも改めて型による分岐が行われますが、文字列の場合はここでも default ケースに落ちていき、変換処理が走るようです。

        default:
                if (!converted) {
                        zendi_convert_scalar_to_number(op1, op1_copy, result);
                        zendi_convert_scalar_to_number(op2, op2_copy, result);
                        converted = 1;