PHPでの添字配列結合は破壊的操作が圧倒的に早い

添字配列(リスト型配列)の話です。
Packed arraysでしか確認してません。

$all_names = []; に $names1 = [田中, 鈴木, 吉田, ...], $names2 = [...] のような配列を単純に追加し続けるコードを書いた時、何も考えずにarray_merge()を使って詰んだのでメモ。

まとめ

• 添字配列(リスト型配列)同士の結合は非破壊的操作array_merge()より、破壊的操作array_push()のほうが遥かに早い
  • 実測でarray_mergeはO(n^3)、array_pushはO(n)
• 破壊的操作では array_push($array, ...$items)とforeach ($items as $item) {$array[] = $item;} どちらでも良い
• ユーザ入力を処理する箇所でarray_mergeを繰り返すコードがあるとDoS脆弱性になる可能性あり

当たり前だよなぁ

※100回繰り返しの平均、ただしarray_merge 100000回だけは重すぎて1回のみ

非破壊的操作(array_merge)と破壊的操作(array_push)の違い

• 非破壊的操作(array_merge): 結合後の配列を新たに作成する = 全体分のメモリを新規確保＆全数コピー(※)
• 破壊的操作(array_push): 今ある配列を拡張して、追加分だけコピー(※)

※値(文字列)そのものではなくポインタ(を持つzval)だけだと思うけど
　参考 分かりやすい絵 PHP Extension 開発入門 10.1.文字列の内部構造

セキュリティ面

もしユーザ入力の処理でarray_merge()を繰り返すコードがある場合、通常の入力であれば問題なく動いていても、悪意ある入力を与えることでDoSが可能になるかもしれず、注意を要する。
実測で処理時間は以下の通りで、配列の数が増えると急激に増加する。

• array_merge(): O(n^3)
• array_push(): O(n)

例えばMultiple selectやJSONなどから配列型のデータ入力を受け入れる処理に対し、巨大な配列を送りつけるなどが考えられる。

検証コード

以下コードでPHP 8.1で確認。

<?php
declare(strict_types=1);

$add_loop_num = (int)$argv[1]; #配列を足す回数
$total_try = 100; #試行回数(100回平均)
if (!$add_loop_num) {
    die;
}

$total_time = 0;
$memory_init = memory_get_usage();
for ($try = 1; $try <= $total_try; $try++) {
    $start = microtime(true);

    $all_names = [];
    for ($i = 1; $i <= $add_loop_num; $i++) {
        $names = get_names();

        $all_names = array_merge($all_names, $names); //← ここの処理差し替えで時間比較

        // array_push($all_names, ...$names);
        
        // foreach ($names as $name) {
        //     $all_names[] = $name;
        // }
    }

    $took = microtime(true) - $start;
    $total_time += $took;
}
$memory_used = memory_get_usage() - $memory_init;

echo "took: ", $total_time/$total_try * 1e3 , " ms\n"; //ms単位
echo "memory: ", $memory_used/1024/1024, " MB\n";

function get_names()
{
    return ['A', 'B', 'C', 'D', 'E'];
}