Bug #77556 [Opn->Nab]: COUNT_RECURSIVE is suprisingly slow
| From: | nikic@php.net | Date: | Fri, 01 Feb 2019 14:58:30 +0000 |
| Subject: | Bug #77556 [Opn->Nab]: COUNT_RECURSIVE is suprisingly slow | ||
| References: | 1 | Groups: | php.bugs |
| Request: | Send a blank email to php-bugs+get-219329@lists.php.net to get a copy of this message | ||
Edit report at https://bugs.php.net/bug.php?id=77556&edit=1
ID: 77556
Updated by: nikic@php.net
Reported by: ivan dot enderlin at hoa-project dot net
Summary: COUNT_RECURSIVE is suprisingly slow
-Status: Open
+Status: Not a bug
Type: Bug
Package: Performance problem
Operating System: macOS
PHP Version: 7.3.1
Block user comment: N
Private report: N
New Comment:
COUNT_RECURSIVE also needs to iterate over the inner arrays to check whether they contain arrays
that also need to be recursively counted. You are using domain knowledge (that arrays are
singly-nested) to avoid that extra recursion step, and can thus do this much more efficiently.
It's basically 100000 vs 100000^2 operations.
Previous Comments:
------------------------------------------------------------------------
[2019-02-01 14:52:47] ivan dot enderlin at hoa-project dot net
Description:
------------
I discovered
COUNT_RECURSIVE and thought it would speed up my algorithm. But instead,
it slowed it down. It initially used array_sum + array_map. See the test
script.
This result is surprising because array_map creates a new array, so the memory
allocations should be slower than just iterating and counting. It proofs to be true with the last
test in the script (see âmanualâ) where it is faster than all the previous solutions.
Test script:
---------------
<?php
const LENGTH = 100000;
$a = array_fill(0, LENGTH, array_fill(0, LENGTH, 42));
echo 'expected: '; var_dump(LENGTH * LENGTH);
echo "\n\n";
$_ = microtime(true);
echo 'count recursive: '; var_dump(count($a, COUNT_RECURSIVE) - count($a));
echo 'time: ', number_format((microtime(true) - $_) / 1000, 6), "\n\n";
$_ = microtime(true);
echo 'sum + map: '; var_dump(array_sum(array_map('count', $a)));
echo 'time: ', number_format((microtime(true) - $_) / 1000, 6), "\n\n";
$_ = microtime(true);
echo 'sum + map + closure: '; var_dump(array_sum(array_map(function (array $v) { return
count($v); }, $a)));
echo 'time: ', number_format((microtime(true) - $_) / 1000, 6), "\n\n";
$_ = microtime(true);
echo 'manual: ';
$i = 0;
foreach ($a as $aa) {
$i += count($aa);
}
var_dump($i);
echo 'time: ', number_format((microtime(true) - $_) / 1000, 6), "\n\n";
/**
* Output:
*
* expected: int(10000000000)
*
*
* count recursive: int(10000000000)
* time: 0.012170
*
* sum + map: int(10000000000)
* time: 0.000005
*
* sum + map + closure: int(10000000000)
* time: 0.000007
*
* manual: int(10000000000)
* time: 0.000002
*/
Expected result:
----------------
COUNT_RECURSIVE should be as fast as or faster than array_sum +
array_map.
COUNT_RECURSIVE should be as fast as the âmanualâ test, or even faster
because it's written in C directly.
Actual result:
--------------
COUNT_RECURSIVE is way too slow :-).
------------------------------------------------------------------------
--
Edit this bug report at https://bugs.php.net/bug.php?id=77556&edit=1