超長い文字列や配列でも実体が同じなら中身の大きさには依存しない

手元にあった PHP 7.1.10 で試してます。


PHP の配列で、連想配列なのかいわゆる添字が順序通りのただの配列なのかを調べるには、下記の方法が一番手っ取り早いと思います。

array_values($arr) === $arr;

がしかし、配列の === は配列の要素の値の比較も行われるため、これだと配列の中に超でかい文字列や配列が入っているときに超遅くなります。

比較する必要があるのはキーだけなはずなのに配列の要素の値に依存して実行時間が変わるのはイケていないので array_keys でキーだけ取り出して比較したり愚直に foreach で回す方が良いですね・・・そんなふうに考えていた時期が俺にもありました。

いろんなパターンでベンチして最適な方法さがすぞー!と意気込んだところ↑のパターンが概ね良好でした(要素数が少ないときや早期にミスマッチが判断できるときは foreach のが早いこともある)。

<?php
namespace array_values {
    function isSequence($arr)
    {
        return $arr === array_values($arr);
    }
    $namespaces[] = __NAMESPACE__;
}

namespace array_keys {
    function isSequence($arr)
    {
        return array_keys($arr) === array_keys(array_keys($arr));
    }
    $namespaces[] = __NAMESPACE__;
}

namespace range {
    function isSequence($arr)
    {
        if (count($arr) === 0) {
            return true;
        } else {
            return array_keys($arr) === range(0, count($arr) - 1);
        }
    }
    $namespaces[] = __NAMESPACE__;
}

namespace foreach_ {
    function isSequence($arr)
    {
        $j = 0;
        foreach ($arr as $i => $v) {
            if ($i !== $j++) {
                return false;
            }
        }
        return true;
    }
    $namespaces[] = __NAMESPACE__;
}

namespace {
    function test($ns)
    {
        $func = "$ns\\isSequence";

        assert($func([]) === true, "$func([]) === true");
        assert($func([2, 4, 6]) === true, "$func([2, 4, 6]) === true");
        assert($func([2, 4, 'x' => 6]) === false, "$func([2, 4, 'x' => 6]) === false");
        assert($func([2 => 2, 1 => 4, 0 => 6]) === false, "$func([2 => 2, 1 => 4, 0 => 6]) === false");
    }

    $data = [
        '[]' => [],
        '[2,4,6]' => [2, 4, 6],
        '[x:9]' => ['x' => 9],
        '[1:1,0:0]' => [1 => 1, 0 => 0],
        '[0..10000]' => range(0, 10000),
        '{0..10000, x:x}' => range(0, 10000) + ['x' => 'x'],
        '[0, 0..100000]' => [0, range(0, 100000)],
        '{x:x, z: 0..100000}' => ['x' => 'x', 'z' => range(0, 100000)],
        '[0, x..x]' => [0, str_repeat("x", 100000)],
        '{x:x, z: x..x}' => ['x' => 'x', 'z' => str_repeat("x", 100000)],
    ];

    foreach ($namespaces as $ns) {
        test($ns);
    }

    foreach ($namespaces as $ns) {
        $results = [];
        foreach ($data as $name => $arr) {
            $func = "$ns\\isSequence";
            for ($i=0, $t=microtime(true)+1; microtime(true)<$t; $i++) {
                $func($arr);
            }
            printf("%-16s%-24s%d\n", $ns, $name, $i);
            $results[] = $i;
        }
        printf("%-16s%-24s%d ... %d\n", $ns, "", min($results), max($results));
    }
}
array_values    []                      3947641
array_values    [2,4,6]                 3383804
array_values    [x:9]                   3956602
array_values    [1:1,0:0]               3893512
array_values    [0..10000]              5912
array_values    {0..10000, x:x}         6079
array_values    [0, 0..100000]          3246093
array_values    {x:x, z: 0..100000}     3820617
array_values    [0, x..x]               3392908
array_values    {x:x, z: x..x}          3945126
array_values                            5912 ... 3956602
array_keys      []                      3104513
array_keys      [2,4,6]                 2405964
array_keys      [x:9]                   2596304
array_keys      [1:1,0:0]               2524770
array_keys      [0..10000]              3455
array_keys      {0..10000, x:x}         3429
array_keys      [0, 0..100000]          2456517
array_keys      {x:x, z: 0..100000}     2541887
array_keys      [0, x..x]               2523583
array_keys      {x:x, z: x..x}          2530141
array_keys                              3429 ... 3104513
range           []                      5123887
range           [2,4,6]                 1966400
range           [x:9]                   2065069
range           [1:1,0:0]               2093647
range           [0..10000]              4480
range           {0..10000, x:x}         4243
range           [0, 0..100000]          1963215
range           {x:x, z: 0..100000}     2149248
range           [0, x..x]               2077303
range           {x:x, z: x..x}          2039283
range                                   4243 ... 5123887
foreach_        []                      5173692
foreach_        [2,4,6]                 3569323
foreach_        [x:9]                   4653941
foreach_        [1:1,0:0]               4681362
foreach_        [0..10000]              4177
foreach_        {0..10000, x:x}         4102
foreach_        [0, 0..100000]          4032628
foreach_        {x:x, z: 0..100000}     4661640
foreach_        [0, x..x]               4007409
foreach_        {x:x, z: x..x}          4776680

実体が同じなら文字列や配列の中身は比較されない

ということのようです。

<?php
function func($a, $b, $name)
{
    for ($i=0, $t=microtime(true)+1; microtime(true)<$t; $i++) {
        $a === $b;
    }
    printf("%10d ... %s\n", $i, $name);
}

$a = str_repeat('x', 1024*1024*10);
$b = $a;
func($a, $b, 'same huge str');

$a = str_repeat('x', 1024*1024*10);
$b = str_repeat('x', 1024*1024*10);
func($a, $b, 'diff huge str');

$a = 'x';
$b = 'x';
func($a, $b, 'diff tiny str');
  11970864 ... same huge str
       782 ... diff huge str
  11892552 ... diff tiny str

最初のパターンはちょうでかい文字列ですけど実体が同じ変数の比較なので1文字の文字列の比較と差がありません。 一方で2番目のパターンは同じ文字列ではあるものの実体が異なるので超遅いです。

配列でも同様です。

<?php
function func($a, $b, $name)
{
    for ($i=0, $t=microtime(true)+1; microtime(true)<$t; $i++) {
        $a === $b;
    }
    printf("%10d ... %s\n", $i, $name);
}

$a = range(1, 1000000);
$b = $a;
func($a, $b, 'same huge arr');

$a = range(1, 1000000);
$b = range(1, 1000000);
func($a, $b, 'diff huge arr');

$a = [];
$b = [];
func($a, $b, 'diff tiny arr');
  11500321 ... same huge arr
        82 ... diff huge arr
  11197598 ... diff tiny arr

PHP の変数は Copy on Write になっており単に = でコピーしただけなら実際に確保されている文字列や配列のためのメモリ領域は共有されており、なんらかの変更を行ったときに実際の領域がコピーされます。

そして、2つの変数を比較するとき、変数の中身が同じ実体で同じ領域を指しているのであれば、中身を比較するまでもなく「一致」と判断することができるのでしょう(ソースは見ていないけどたぶん)。

配列のキーも文字列のサイズには依存しない

PHP の配列はハッシュテーブルなので文字列をキーにする場合は文字列を元にハッシュ値を計算する必要があります。なので、あまりに巨大な文字列をキーにすると計算のコストが増大して性能が劣化する・・・そんなふうに考えていた時期が俺にもありました。

<?php
function func($arr, $key, $name)
{
    $arr[$key] = 1;
    for ($i=0, $t=microtime(true)+1; microtime(true)<$t; $i++) {
        $v = $arr[$key];
    }
    printf("%10d ... %s\n", $i, $name);
}

$key = str_repeat('x', 1024*1024*10);
$arr[$key] = 1;
func($arr, $key, 'same huge str');

$key = str_repeat('x', 1024*1024*10);
$arr[$key . ''] = 1;
func($arr, $key, 'diff huge str');

$key = 'x';
$arr[$key . ''] = 1;
func($arr, $key, 'diff tiny str');
  11339929 ... same huge str
       781 ... diff huge str
  11241169 ... diff tiny str

最初のパターンは超でかい文字列をキーにしているのでハッシュ値の計算のために性能が劣化しそうなものですが、キーが短いときと代わりありません。

文字列自体が配列のキーとして使うときのためのハッシュ値を持っているとでもいうの・・・

zend_stringに関するメモ - Qiita

struct _zend_string {
        zend_refcounted_h gc;
        zend_ulong        h;                /* hash value */
        size_t            len;
        char              val[1];
};

あ、持ってるっぽい、なるほど。

PHP 5.4.16

まだまだ現役?? の PHP 5.4.16 で試してみました。

# str.php
      1801 ... same huge str
       816 ... diff huge str
   5962900 ... diff tiny str

# arr.php
   5819125 ... same huge arr
        47 ... diff huge arr
   5843144 ... diff tiny arr

# key.php
        85 ... same huge str
        84 ... diff huge str
   6210093 ... diff tiny str

配列の比較だけは PHP 7 と同じような傾向ですが、文字列の比較と配列のキーはご覧の有様でした。

さいごに

PHP 7 なめてた。

例えば PSR-7 を実装したリクエストオブジェクトのアトリビュートに何か入れるとき、名前の競合を避けるためにクラス名を使いたかったりすることあるんですけど、

$request = $request->withAttribute(HogeAttr::class, new HogeAttr($hoge));

今日日の PHP は名前空間が付いていてクラス名の完全修飾名は長くなりがちなので、リクエストオブジェクトの中でアトリビュート名が配列のキーとして持たれることを考えるとクラス名よりも短い文字列の定数とかを別に用意するのが良いだろうかと思ったのだけど・・・

$request = $request->withAttribute(HogeAttr::NAME, new HogeAttr($hoge));
// or
$request = $request->withAttribute('hoge', new HogeAttr($hoge));

そんなこと考える必要は無いということですね。むしろクラスがロードされた時点で存在していることが明らかであるクラス名の文字列の方が好ましいでしょう(::class が使えるならですけど)。

DI コンテナのオブジェクトの ID も同じです。PSR-11 で ID にはクラス名やインタフェース名を使うのを奨励、みたいなことが書かれてた気がしますが、PHP 7 ならクラス名やインタフェース名が超長くてもノーコストなのですね(コンテナの実装に依る)。