うわっ…PHPのarray_reduce、遅すぎ…？

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

```php
        $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つの要素も大きくないため、こんなに時間がかかるはずがありません。

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

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

結果、1秒もかからずにレスポンスが返ってくるようになりました。どうも[array_reduce関数](http://php.net/manual/ja/function.array-reduce.php)が原因のようです。

調べてみたところ、[phpのGithub](https://github.com/php/php-src)に以下のプルリクが出ていました。
[array_reduce is slow when $carry is large array](https://github.com/php/php-src/pull/2931)

内容を見てみると、「`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`

```php
$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`

```php
$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`

```php
$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`

```php
$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を作らない場合は気にせず使っても大丈夫かと思われます。


## 参考
* [array_reduce is slow when $carry is large array](https://github.com/php/php-src/pull/2931)
* [今朝の array_reduce の実行速度](http://y-uti.hatenablog.jp/entry/2013/04/17/222134)

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

```php
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));
```