Hatena::ブログ(Diary)

hnwの日記 このページをアンテナに追加 RSSフィード

[プロフィール]
 | 

2013年11月2日(土) PHPのジェネレータはイテレータより速い このエントリーを含むブックマーク このエントリーのブックマークコメント

先日の記事「PHPのジェネレータの実装を調べてみた」で僕は次のように書きました。


GeneratorクラスはIteratorインターフェースを実装しており、対応するPHPメソッドを持っています。また、Cで実装した場合のみ指定できるイテレータ関数も実装しています。このように両方が指定されている場合、foreachループではCの関数が呼ばれ、イテレータメソッドを明示的に指定した場合はPHPメソッドの方が呼ばれます。


ところで、イテレータに対応するPHPメソッドとC関数となぜ2つとも実装する必要があるのでしょうか。実は、PHPメソッドの方だけ実装すれば正常に動作します。C関数を実装する理由は速度面のメリットからだというのが僕の理解です。C関数関数ポインタで単に呼び出せるのに対し、PHPメソッドの呼び出しは命令実行器の状態保存・復元の必要があるなど、呼び出しのコストがやや高いのです。


PHPのジェネレータの実装を調べてみた - hnwの日記


PHPイテレータをforeach文でループさせる場合、内部的に呼ばれる処理の候補としてC関数PHPメソッドと2種類あること、C関数の方が速度の観点で有利であること、ジェネレータを作った場合はC関数が使われることを紹介しています。


別の言い方をすると、PHPIteratorインターフェースを実装した場合は必ずPHPメソッドが使われますので、それよりは同じ動作のジェネレータを作った方が速いということになりそうです。本稿ではこれを確認してみましょう。


ベンチマークテスト

1から指定された数までの整数を順に返すようなイテレータとジェネレータを作り、その実行時間を比較してみました。


<?php
class MyIterator implements Iterator
{
    protected $value, $max;
    
    function __construct($max)
    {
        $this->max = $max;
    }
    function rewind()
    {
        $this->value = 1;
    }
    function valid()
    {
        return ($this->value <= $this->max);
    }
    function next()
    {
        $this->value++;
    }
    function current()
    {
        return $this->value;
    }
    function key()
    {
        return $this->value;
    }
}

class MyGenerator implements IteratorAggregate
{
    protected $max;
    function __construct($max)
    {
        $this->max = $max;
    }
    function getIterator() {
        $value = 1;
        while ($value <= $this->max) {
            yield $value;
            $value++;
        }
    }
}

function testTraversable($name, Traversable $iter) {
    //$format = "%2$.10f\n";
    $format = "%s : %.10f seconds\n";
    $startTime = microtime(true);
    foreach ($iter as $value) {
        // nop
    }
    printf($format, $name, microtime(true) - $startTime);
}

function test($count) {
    $format = "%-16s (%8d)";
    testTraversable(
        sprintf($format, "MyGenerator", $count),
        new MyGenerator($count)
    );
    testTraversable(
        sprintf($format, "MyIterator", $count),
        new MyIterator($count)
    );
}

test(1000);
test(10000);
test(100000);
test(1000000);

手元のMacOSX上のPHP 5.5.5での結果は次の通りです。結果の単位は秒です(以降の結果も同様)。


ループ回数 generator iterator
1000 0.0025 0.0071
10000 0.027 0.077
100000 0.26 0.77
1000000 2.64 7.58

同じ機能を持つイテレータとジェネレータとではジェネレータの方がおよそ3倍速いことがわかりました。



上の結果を両対数グラフにしてみました。当然ですが、ループ回数にかかわらずほぼ一定の速度比であることがわかります。(対数の差は比を表すため)。


PHPメソッド呼び出しとC関数呼び出しの差

ジェネレータよりイテレータの方が不利な理由として、ジェネレータのイテレーション処理はC関数が呼ばれるのに対し、イテレータの場合はPHPメソッド呼び出しになるためだと紹介しました。これはどれくらい不利になるのでしょうか。


これを確認するため、ジェネレータでPHPメソッドを利用するようにしてみましょう。これはPHP本体を以下のように2行コメントアウトすれば実現できます。


*** php-5.5.5-orig/Zend/zend_generators.c	2013-10-15 22:49:47.000000000 +0900
--- php-5.5.5/Zend/zend_generators.c	2013-11-01 10:40:59.000000000 +0900
***************
*** 725,732 ****
--- 725,734 ----

  	/* get_iterator has to be assigned *after* implementing the inferface */
  	zend_class_implements(zend_ce_generator TSRMLS_CC, 1, zend_ce_iterator);
+ 	/*
  	zend_ce_generator->get_iterator = zend_generator_get_iterator;
  	zend_ce_generator->iterator_funcs.funcs = &zend_generator_iterator_functions;
+ 	*/

  	memcpy(&zend_generator_handlers, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
  	zend_generator_handlers.get_constructor = zend_generator_get_constructor;

この修正をしたPHPで同じベンチマークテストを行った結果が以下になります。


ループ回数 generator(C) iterator generator
(PHP method)
1000 0.0025 0.0071 0.010
10000 0.027 0.077 0.10
100000 0.26 0.77 1.02
1000000 2.64 7.58 9.95


generator(C)が通常の5.5系のジェネレータ実装、generator(PHP method)が上のパッチを当てたPHPによるジェネレータ実装です。


この結果を見ると、PHPメソッドを利用するジェネレータはPHPで実装したイテレータよりも遅くなっていることがわかります。これは、イテレータに対応するPHPメソッドの呼び出し(1ループあたりnext(),valid(),current()の3回)に加え、ジェネレータ関数の再開・停止の分だけ遅くなっているためだと考えられます。


また、generator(C)とiteratorとgenerator(PHP)の実行時間の比はおおよそ1:3:4程度です。PHP関数メソッド呼び出しとジェネレータ関数の再開&停止のコストを同一視すると、関数の呼び出し回数の比だと言えそうです。


forループとも比較してみる

今回のイテレータは単純なforループでも実現できる内容です。また、ArrayIteratorに巨大な配列を渡しても実現できます。これらとも速度を比べてみましょう。


ループ回数 ArrayIterator for loop generator iterator
1000 0.00020 0.00025 0.0025 0.0071
10000 0.0019 0.0023 0.027 0.077
100000 0.021 0.024 0.26 0.77
1000000 0.20 0.23 2.64 7.58


速いように思われたジェネレータも、forループやArrayIteratorと比べると一桁遅いことがわかりました。遅い原因は、先ほどの推測と同じくジェネレータ関数の再開・停止のコストだと考えられます。ジェネレータによるループはジェネレータ関数呼び出し1回分程度、自前実装したイテレータではメソッド呼び出し3回分程度、それぞれ速度面でペナルティがあるというのは知っておいて損はないでしょう。


もっとも、今回のベンチマークテストではループ内で何もしていないときの実行時間を比較していますが、実戦ではループ内で意味のある処理を行うでしょうから、これらの差は相対的に縮まるはずです。また、個人的にはこのレベルの速度差はそこまで重要ではなく、大抵の場合は読みやすさ・保守性の高さの方が重要だと考えています。ですから、forループより遅いとしてもジェネレータで書きたい状況はあるはずです。


また、ArrayIteratorは確かに高速ですが、大きい配列を扱うとnewするときのコストが大きくなりすぎて使い物にならないこともあるでしょう(上のベンチマークテストはインスタンスを作った後のループ時間を測定しており、配列の大きさの悪影響は現れていません)。ジェネレータは省メモリかつ速度もそこそこで拡張性が高いので、PHP 5.5以降では活躍するはずです。


まとめ

トラックバック - http://d.hatena.ne.jp/hnw/20131102
 | 
ページビュー
1818641