発端

ローカル環境でPHPのAPIのテストをしているときに、どうにもレスポンスが遅いという事象が発生しました。
普段はどんなにレスポンスが遅くても数秒で返ってきますが、だいたい120秒ほどかかっています。いくらなんでも遅すぎる。
MySQLのロックかなと思い、調べてみたところ原因は以下のコードでした。

        $user_badge_record_map = array_reduce(
            $user_badge_records,
            function (array $result, array $record) {
                $result[$record['user_id']][$record['badge_id']] = $record;

                return $result;
            },
            []
        );

確かに$user_badge_recordsは要素数25000の配列ですが、1つの要素も大きくないため、こんなに時間がかかるはずがありません。

原因は？

試しに動作的に同じになるよう、以下のようなコードに書き換えてみます。

        $user_badge_record_map = [];
        foreach ($user_badge_records as $record) {
            $user_badge_record_map[$record['user_id']][$record['badge_id']] = $record;
        }

結果、1秒もかからずにレスポンスが返ってくるようになりました。どうもarray_reduce関数が原因のようです。

調べてみたところ、phpのGithubに以下のプルリクが出ていました。
array_reduce is slow when $carry is large array

内容を見てみると、「array_reduceはcallback関数実行の際に第一引数$carryのコピーを作ってしまっており、そのサイズが大きくなるとパフォーマンスが落ちる問題がある」と書かれています。

実験してみた

本当にarray_reduceは遅いのか、大きいcarryを作らなければ遅くないのか、実験しました。

実行環境

php -v
PHP 7.1.0 (cli) (built: Dec 2 2016 11:29:13) ( NTS )
Copyright (c) 1997-2016 The PHP Group
Zend Engine v3.1.0-dev, Copyright (c) 1998-2016 Zend Technologies

carryを作るケースの速度の比較実験

単純にrangeで作った数値の配列をarray_reduceとforeachでそれぞれ作りなおし、実行時間を測って比較します。carryには新しい配列が入ります。

array_reduce

$before_list = range(1, $n);
$start_time = microtime(true);

$after_list = array_reduce(
  $before_list,
  function ($result, $number) {
      $result[]= $number;

      return $result;
  },
  []
);

  $end_time = microtime(true);
  echo sprintf("elapsed time = %f", $end_time - $start_time);

$n	実行時間(秒)
10000	0.299
20000	2.99
25000	7.02
30000	12.09

foreach

$before_list = range(1, $n);
$start_time = microtime(true);

$after_list = [];

foreach ($before_list as $value) {
  $after_list[] = $value;
}

$end_time = microtime(true);
echo sprintf("elapsed time = %f", $end_time - $start_time);

$n	実行時間(秒)
10000	0.000683
20000	0.002115
25000	0.002225
30000	0.002680
...	...
1000000	0.079285

実験結果

array_reduceが驚くほど遅い。
100万要素のforeachの時よりも1万要素のarray_reduceの方が4倍くらい遅い。
しかもarray_reduceは実行時間の増大から見て実行時間のオーダーが線形じゃなさそう。

carryを作らないケースの速度の比較実験

rangeで作った数値の配列の総和を出し、実行時間を測って比較します。carryには総和の数値が入ります。

array_reduce

$before_list = range(1, $n);
$start_time = microtime(true);

 $sum = array_reduce(
  $before_list,
  function ($result, $number) {
      $result += $number;

      return $result;
  },
  0
);

$end_time = microtime(true);
echo sprintf("elapsed time = %f, result = %d", $end_time - $start_time, $sum);

$n	実行時間(秒)
10000	0.001123
20000	0.002480
25000	0.003995
30000	0.004477

foreach

$before_list = range(1, $n);
$start_time = microtime(true);

$sum = 0;

foreach ($before_list as $value) {
  $sum += $value;
}

$end_time = microtime(true);
echo sprintf("elapsed time = %f, result = %d", $end_time - $start_time, $sum);

$n	実行時間(秒)
10000	0.000375
20000	0.000480
25000	0.000597
30000	0.001154
...	...
1000000	0.054139

実験結果

array_reduceはforeachよりも4倍くらい遅いが、carryを作成していた時ほどの差はない。
実行時間のオーダーも線形のようである。

まとめ

大きいcarryを作る場合（元の配列から新しい配列を作る場合）はとても遅いので、array_reduceは使わない方が良さそうです。
carryを作らない場合は気にせず使っても大丈夫かと思われます。

参考

2018/03/19追記

配列をオブジェクトにラップして、そのオブジェクトをcarryにするととても高速になる。
オブジェクト自体がコピーされても、内部の配列のコピーが行われないためと思われる。

class A{
  public $list;
}

$a = new A();
$a->list = [];
$before_list = range(1, $n);
$start_time = microtime(true);

$after_list = array_reduce(
  $before_list,
  function ($result, $number) {
    $result->list[]= $number;

    return $result;
  },
  $a
);

$end_time = microtime(true);
echo sprintf("elapsed time = %f, |count| = %d\n", $end_time - $start_time, count($a->list));