タグ別アーカイブ: performance

phpのcount関数の実装を見る

ご無沙汰しております。
今日は掲題のようにcount関数の実装を見て行きたいと思います。

概要

phpの開発を行ったことがある方であれば、下記のようなコード見たことあると思います。

$something = array('a', 'b', 'c');

for($i=0; $i<count($something); $i++) {
 // do something
}

また下記のようなコードも目にすることがあると思います。

$something = array('a', 'b', 'c');
$count = count($something);

for($i=0; $i<$count; $i++) {
 // do something
}

これらのコードどちらが効率的なのでしょうか。
なんとなく後者のほうが効率が良いようなことは想像に難しくないと思います。
でも、はっきり前者は悪だと断言できる方は実は少ないのではないでしょうか。

後者にしておけば困ったことにはならないでしょう。ただし、コードが一行増える。微々たるものですが。
どちらかと言うと前者のほうがコードとしてはすっきりしていると思います。

それに何より中身がどうなっているのかわからないのが気分的にすっきりしない。
今日はphpのcount関数の実装を確認してみたいと思います。

調査

php公式からソースコードをダウンロードして調査します。
バージョンは現在の最新安定版である5.6.14としました。

zval構造体

まずphpのzend構造体から確認します。
zend.hをみてみましょう。

typedef struct _zval_struct zval;
struct _zval_struct {
    /* Variable information */
    zvalue_value value;       /* value */
    zend_uint refcount__gc;
    zend_uchar type;          /* active type */
    zend_uchar is_ref__gc;
};

typedef union _zvalue_value {
    long lval;        /* long value */
    double dval;      /* double value */
    struct {
        char *val;
        int len;
    } str;
    HashTable *ht;    /* hash table value */
    zend_object_value obj;
    zend_ast *ast;
} zvalue_value;

phpでは変数はzval構造体で表されます。
zval構造体は参照カウントや、変数実体を保持するzvalue_valueという共用体を更に内部で保持します。
union構造体とは宣言された値の内どれか一つを保持する構造体のことです。

phpではlongやdoubleやstringなどの値に応じてzvalue_value共用体が保持する実体を切り替えるようになっています。
配列変数の場合はHashTable構造体を保持することになります。

Hashtable構造体

さらにzend_hash.hファイルを確認してその構造を確認してみましょう。

struct _hashtable;
typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;       /* Used for element traversal */
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
 #if ZEND_DEBUG
    int inconsistent;
 #endif
} HashTable;

hashtable構造体については詳細な説明は今回は割愛します。
いったんデータ構造を確認したら今度はcount関数の実装を見てみることにしましょう。

count関数

array.cファイルを覗いてみます。

PHP_FUNCTION(count)
{
    zval *array;
    long mode = COUNT_NORMAL;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z|l", &array, &mode) == FAILURE) {
        return;
    }

    switch (Z_TYPE_P(array)) {
        case IS_NULL:
            RETURN_LONG(0);
            break;
        case IS_ARRAY:
            RETURN_LONG (php_count_recursive (array, mode TSRMLS_CC));
            break;
        case IS_OBJECT: {
#ifdef HAVE_SPL
            zval *retval;
#endif
            /* first, we check if the handler is defined */
            if (Z_OBJ_HT_P(array)->count_elements) {
                RETVAL_LONG(1);
                if (SUCCESS == Z_OBJ_HT(*array)->count_elements(array, &Z_LVAL_P(return_value) TSRMLS_CC)) {
                    return;
                }
            }
#ifdef HAVE_SPL
            /* if not and the object implements Countable we call its count() method */
            if (Z_OBJ_HT_P(array)->get_class_entry && instanceof_function(Z_OBJCE_P(array), spl_ce_Countable TSRMLS_CC)) {
                zend_call_method_with_0_params(&array, NULL, NULL, "count", &retval);
                if (retval) {
                    convert_to_long_ex(&retval);
                    RETVAL_LONG(Z_LVAL_P(retval));
                    zval_ptr_dtor(&retval);
                }
                return;
            }
#endif
        }
        default:
            RETURN_LONG(1);
            break;
    }
}

ごちゃごちゃと記述してありますが、今回は単純な配列な値の場合を確認します。
すると対象は一行だけでphp_count_recursiveを呼び出していることがわかります。

さらにphp_count_recursiveをおってみましょう。

PHPAPI int php_count_recursive(zval *array, long mode TSRMLS_DC) /* {{{ */
{
    long cnt = 0;
    zval **element;

    if (Z_TYPE_P(array) == IS_ARRAY) {
        if (Z_ARRVAL_P(array)->nApplyCount > 1) {
            php_error_docref(NULL TSRMLS_CC, E_WARNING, "recursion detected");
            return 0;
        }

        cnt = zend_hash_num_elements(Z_ARRVAL_P(array));
        if (mode == COUNT_RECURSIVE) {
            HashPosition pos;

            for (zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(array), &pos);
                zend_hash_get_current_data_ex(Z_ARRVAL_P(array), (void **) &element, &pos) == SUCCESS;
                zend_hash_move_forward_ex(Z_ARRVAL_P(array), &pos)
            ) {
                Z_ARRVAL_P(array)->nApplyCount++;
                cnt += php_count_recursive(*element, COUNT_RECURSIVE TSRMLS_CC);
                Z_ARRVAL_P(array)->nApplyCount--;
            }
        }
    }

    return cnt;
}

ここでも型チェックや再帰的に関数を呼び出している部分がありますが、本質的な部分は一行だけです。
変数cntを代入しているzend_hash_num_elementsを見てみましょう。
実装はzend_hash.cにあります。

ZEND_API int zend_hash_num_elements(const HashTable *ht)
{
    IS_CONSISTENT(ht);

    return ht->nNumOfElements;
}

IS_CONSISTENTマクロはハッシュテーブルが破壊されていないかどうかを確認するものです。
さてここでようやく実装が見えましたね。
count関数の行っていることはhashtable構造体のnNumOfElementsを返却しているだけなのです。

結論

冒頭で出した2つのコードのパフォーマンスの違いはそこまで大きくないでしょう、ビッグオー的に計算量で表すとどちらもO(1)になるからです。

ただ実装で言うとメソッドの呼び出しが3つほど噛まれていますので、関数スタックにガツガツと何度も積み上げられることになります。
特にパフォーマンスに気を使う部分であれば、count関数の呼び出しは一度だけに限定するほうが良いでしょう。

個人的にはfor文の中に挟み込む方式は、あまり推奨しないかな。
コードは行儀、シンプルに誰でもわかるように書きべきでしょう。


str_replace, preg_replaceのパフォーマンス検証と呼び出しの最適化

概要

PHPでは文字列を置換するのにstr_replaceとpreg_replaceという関数を用いることができます、今回はそれぞれのパフォーマンスについて考察していきたいと思います。

予想としては当然preg_replaceのほうがコストが高く付くと思います、実際本当にそうなのか。またどの程度のパフォーマンスの開きが出るのかをいくつかのサンプルを用意して比較します。
簡単な表現から、多少複雑な表現まで検証してみます。
またそれぞれの関数の使用時の最適化についても調べたいと思います。

ちなみに当然ですがPHPの 公式マニュアル では特別な必要性がない限りstr_replaceを使用することを推奨しています。

preg_replaceとstr_replaceを理解する

preg_replaceとstr_replaceについてはご存じの方も多いかと思いますが、その名のごとくある文字列を対象として、特定の単語を別の単語で置き換えることのできる関数になります。
その違いも簡単で、str_replaceは特定の単語を検索置換するのに対して、preg_replaceは正規表現を用いて検索置換が行えます。

str_replaceについて簡単な例を示します。

$before = "this is test.";
$after = str_replace("this", "that", $before);
var_dump($after); // "that is test."

シンプルですね。文字列の置換ができます。

つづいてpreg_replaceについても簡単な例を示します。

$before = "this costs 1000yen. it costs 2000yen.";
$after = preg_replace("/(\d+)yen/", "¥$1", $before);
var_dump($after); // "this costs ¥1000. it costs ¥2000."

こちらも単純に正規表現を用いての置換ができることがわかりました。シンプルです。

性能を検証する

さて気になるパフォーマンスを見て行きましょう。
今回はテストケースを3つ用意しました。
1. 単純なパターンの単数の置換
2. 単純なパターンの複数の置換
3. 複雑なパターンの単数の置換

検証したPHPのバージョンは下記になります

$ php -v
PHP 5.4.30 (cli) (built: Jul 29 2014 23:43:29)
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.4.0, Copyright (c) 1998-2014 Zend Technologies

単純なパターンの単数の置換を実行した際のパフォーマンス

ここでは単純なパターンでの一つの文字列の置換を実行します。
用意する計測するコードは下記のようになります。

<?php
if (!isset($argv[1])) {
  echo 'usage -- php profile.php {try_count}' . PHP_EOL;
}
$count = intval($argv[1]);
echo "run test {$count} times." . PHP_EOL;

$subject = "this is test sentence one. this is test sentence two. this is test sentence three. this is test sentence four. this is test sentence five. this is test sentence six. this is test sentence seven. this is test sentence eight. this is test sentence nine. this is test sentence ten.";
echo "check performance of str_replace." . PHP_EOL;
$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $subject = str_replace('this', 'that', $subject);
}
$end = microtime(true);
var_dump($end - $start);

echo "check performance of preg_replace" . PHP_EOL;
$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $subject = preg_replace('/this/', 'that', $subject);
}
$end = microtime(true);
var_dump($end - $start);

計測します。

$ php profile_test_2.php 100000
run test 100000 times.
check performance of str_replace.
double(0.15461802482605)
check performance of preg_replace
double(0.35560202598572)

このような単純なパターンでも約二倍程度の性能差があることが見て取れました。
予想通りの結果となり、検索置換をアプリケーションで行うようであれば特別な理由なくpreg_replaceを使用するべきでないですね。

単純なパターンの複数の置換を実行した際のパフォーマンス

続いて複数文字列を置換する際のパフォーマンスについて検証します。
下記のようにサンプルプログラムを用意します。

<?php
if (!isset($argv[1])) {
  echo 'usage -- php profile.php {try_count}' . PHP_EOL;
}
$count = intval($argv[1]);
echo "run test {$count} times." . PHP_EOL;

$subject = "this is test sentence one. this is test sentence two. this is test sentence three. this is test sentence four. this is test sentence five. this is test sentence six. this is test sentence seven. this is test sentence eight. this is test sentence nine. this is test sentence ten.";
$source = array('one', 'two', 'three', 'four', 'five', 'six', 'seven', 'nine', 'ten');
$dest = array(1,2,3,4,5,6,7,8,9,10);
echo "check performance of str_replace." . PHP_EOL;
$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $subject = str_replace($source, $dest, $subject);
}
$end = microtime(true);
var_dump($end - $start);


$source = array('/one/', '/two/', '/three/', '/four/', '/five/', '/six/', '/seven/', '/nine/', '/ten/');
$dest = array(1,2,3,4,5,6,7,8,9,10);
echo "check performance of preg_replace" . PHP_EOL;
$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $subject = preg_replace($source, $dest, $subject);
}
$end = microtime(true);
var_dump($end - $start);

計測します。

$ php profile_test_1.php 100000
run test 100000 times.
check performance of str_replace.
double(0.53684210777283)
check performance of preg_replace
double(1.4594769477844)

ここでも2倍から3倍程度の性能差が確認できました。
置換対象が複数になることでその性能差が開いていることが確認できます。

ここでちょっと気になるのは、str_replace, preg_replaceのそれぞれの性能を先の検証パターンと比較した時に性能が線形に悪化しているわけではなさそうだということです。
これについては別件として最後に検証を行うこととします。

複雑なパターンの単数の置換を実行した際のパフォーマンス

最後に複雑な正規表現を用いた際のパフォーマンスの違いについて見てみます。
下記のプログラムのように検索する表現を無駄に複雑にしてみます。

<?php
if (!isset($argv[1])) {
  echo 'usage -- php profile.php {try_count}' . PHP_EOL;
}
$count = intval($argv[1]);
echo "run test {$count} times." . PHP_EOL;

$subject = "this is test sentence one. this is test sentence two. this is test sentence three. this is test sentence four. this is test sentence five. this is test sentence six. this is test sentence seven. this is test sentence eight. this is test sentence nine. this is test sentence ten.";
echo "check performance of str_replace." . PHP_EOL;
$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $subject = str_replace('this', 'that', $subject);
}
$end = microtime(true);
var_dump($end - $start);

$subject = "this is test sentence one. this is test sentence two. this is test sentence three. this is test sentence four. this is test sentence five. this is test sentence six. this is test sentence seven. this is test sentence eight. this is test sentence nine. this is test sentence ten.";
echo "check performance of preg_replace" . PHP_EOL;
$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $subject = preg_replace('/([a-z]+) (is) (test)/', '$1 $2 $3', $subject);
}
$end = microtime(true);
var_dump($end - $start);

計測します。

$ php profile_test_3.php 100000
run test 100000 times.
check performance of str_replace.
double(0.14943814277649)
check performance of preg_replace
double(2.3758080005646)

すさまじい差ですね。(こんなケースはないかと思いますが)
正規表現による検索が、検索パターンによってコストが増大していることがわかります。

(番外編)置換対象が複数ある場合の関数呼び出し時の最適化について

検証パターン2の考察時にも触れましたが、複数の検索置換を行うときにstr_replace, preg_replaceは同様のインタフェースを用意しており、検索パターンと置換パターンを配列で渡すことができます。
複数の置換を実行するときに、置換を一回一回実行する方法と、置換パターンを配列で渡し一度に実行する方法の実装の仕方によってどれだけ差が出るかということを検証します。

プログラムを用意します。
一回一回実行する方法では、置換を行い、置換後の文字列に対して再度置換を行い、、、を繰り返します。

<?php
if (!isset($argv[1])) {
  echo 'usage -- php profile.php {try_count}' . PHP_EOL;
}
$count = intval($argv[1]);
echo "run test {$count} times." . PHP_EOL;

$subject = "this is test sentence one. this is test sentence two. this is test sentence three. this is test sentence four. this is test sentence five. this is test sentence six. this is test sentence seven. this is test sentence eight. this is test sentence nine. this is test sentence ten.";
echo "check performance of multiple call." . PHP_EOL;
$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $subject = str_replace('one', 1, $subject);
  $subject = str_replace('two', 2, $subject);
  $subject = str_replace('three', 3, $subject);
  $subject = str_replace('four', 4, $subject);
  $subject = str_replace('five', 5, $subject);
  $subject = str_replace('six', 6, $subject);
  $subject = str_replace('seven', 7, $subject);
  $subject = str_replace('eight', 8, $subject);
  $subject = str_replace('nine', 9, $subject);
  $subject = str_replace('ten', 10, $subject);
}
$end = microtime(true);
var_dump($end - $start);

$subject = "this is test sentence one. this is test sentence two. this is test sentence three. this is test sentence four. this is test sentence five. this is test sentence six. this is test sentence seven. this is test sentence eight. this is test sentence nine. this is test sentence ten.";
echo "check performance of single call." . PHP_EOL;
$start = microtime(true);
$source = array('one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten');
$dest = array(1,2,3,4,5,6,7,8,9,10);
for($i=0; $i<$count; $i++) {
  $subject = str_replace($source, $dest, $subject);
}
$end = microtime(true);
var_dump($end - $start);

計測してみます。

 $ php profile_test_4.php 100000
run test 100000 times.
check performance of multiple call.
double(1.2376821041107)
check performance of single call.
double(0.51983189582825)

!!!
をを。思った以上に差が出てきた
約倍程度のパフォーマンスの差がでています。

と余談なんですが、他のPCでも同じプログラムの実行を行ったところ、上記の結果ほどの差は出なかった。
その際のバージョンは5.4.30であった。

$ php profile_test_4.php 100000
run test 100000 times.
check performance of multiple call.
float(0.44886112213135)
check performance of single call.
float(0.36096215248108)

なんだかしこり残るのでphpのバージョンを5.6にあげて検証してみます。

$ php -v
PHP 5.6.6 (cli) (built: Feb 20 2015 22:35:31)
Copyright (c) 1997-2015 The PHP Group
Zend Engine v2.6.0, Copyright (c) 1998-2015 Zend Technologies
    with Zend OPcache v7.0.4-dev, Copyright (c) 1999-2015, by Zend Technologies
    with Xdebug v2.2.5, Copyright (c) 2002-2014, by Derick Rethans
...
$ php profile_test_4.php 100000
run test 100000 times.
check performance of multiple call.
double(1.22190117836)
check performance of single call.
double(0.46425199508667)

悪化した!?!?!?

ここから考察できるのはどうやらphp5.4.30以降str_replaceの性能は悪くなっているようである。

どちらにしても最適化された呼び出しとしては配列で一度に渡したほうが高速である。

以上、もろもろパフォーマンスについて検証しました、参考にしていただければと思います。