112

Does count() really count the all the elements of a PHP array, or is this value cached somewhere and just gets retrieved?

Mark Amery
  • 143,130
  • 81
  • 406
  • 459
Dexter
  • 3,072
  • 5
  • 31
  • 32
  • 7
    Why not test it? it's simple enough to do a loop that adds elements to an array and counts each time and do some timing. – Marc B Apr 29 '11 at 17:26
  • 3
    Take a look at this question: http://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions – The Pixel Developer Apr 29 '11 at 17:29
  • Google keywords - this question could also be formulated as: Does PHP count() iterates over array or does it retrieve count from array property ? – jave.web Sep 01 '15 at 12:07

3 Answers3

166

Well, we can look at the source:

/ext/standard/array.c

PHP_FUNCTION(count) calls php_count_recursive(), which in turn calls zend_hash_num_elements() for non-recursive array, which is implemented this way:

ZEND_API int zend_hash_num_elements(const HashTable *ht)
{
    IS_CONSISTENT(ht);

    return ht->nNumOfElements;
}

So you can see, it's O(1) for $mode = COUNT_NORMAL.

John Carter
  • 53,924
  • 26
  • 111
  • 144
Vladislav Rastrusny
  • 29,378
  • 23
  • 95
  • 156
  • 8
    What does `IS_CONSISTENT(ht)` do though? – Matt Apr 29 '11 at 17:43
  • 1
    Thanks! I wasn't quite sure where in the source I should look or where to get the source (without having to check it out of a repository). – Dexter Apr 29 '11 at 17:51
  • 4
    @Matt It's checking if hash structure is valid, as I can see. It's defined in zend_hash.c and it's O(1) also. – Vladislav Rastrusny Apr 29 '11 at 18:09
  • 17
    Cannot miss to vote up for someone looking for the answer in the PHP's source code :) – Yasen Jul 17 '12 at 13:24
  • In which file of the source code can zend_hash_num_elements be found? :-) – Phil Dec 10 '12 at 16:17
  • 1
    @Matt IS_CONSISTENT() is just a sanity check on the array https://github.com/php/php-src/blob/PHP-5.3/Zend/zend_hash.c#L51 – John Carter Apr 20 '13 at 22:04
  • @VladislavRastrusny and how is it for mode `COUNT_RECURSIVE` if I may ask please? – jave.web Sep 01 '15 at 12:11
  • @jave.web I believe, it will be O(n) where n is the total number of array elements (including nested arrays). When `COUNT_RECURSIVE` is enabled, each array element type needs to be tested. – Vladislav Rastrusny Sep 03 '15 at 09:12
  • @VladislavRastrusny thanks, I thought so, its quite sad that multidimensional array doesn't have extra property to count all array elements at init. – jave.web Sep 04 '15 at 07:30
  • @jave.web It would slow access since on each array modification that information needs to be cached. – Vladislav Rastrusny Sep 04 '15 at 08:25
  • @jave.web What if you add some array containing strings and arrays to the main array? PHP will need to scan each element of new array to check if it is an array to update caching information of the main array. – Vladislav Rastrusny Sep 04 '15 at 11:04
  • @VladislavRastrusny as I said , it does it anyway - when it is storing count member for each stored array - in that moment - it definitely knows a) it is storing array b) it is a subarray – jave.web Sep 04 '15 at 11:30
10

In PHP 5+ the length is stored in the array so the counting is not done each time.

EDIT: You also might find this analysis interesting: PHP Count Performance. Although the length of the array is maintained by the array, it still seems as though it is faster to hold on to it if you are going to call count() many times.

jberg
  • 4,758
  • 2
  • 20
  • 15
  • 1
    I think you may be correct that the change was made starting with PHP 5. However, I haven't yet found the proof that PHP 4 was O(n) for count(); I just see anecdotal comments. Are you able to find proof (ie the count() implementation for PHP 4)? Thanks, – Kristopher Windsor Jan 16 '16 at 00:46
  • I know it is an old question, but unfortunatly the link does not work any more. Maybe the is another source on this topic that someone can recover. – Robin Bastiaan Nov 08 '22 at 09:24
6

PHP stores the size of an array internally, but you're still making a function call when which is slower than not making one, so you'll want to store the result in a variable if you're doing something like using it in a loop:

For example,

$cnt = count($array);
for ($i =0; $i < $cnt; $i++) {
   foo($array[$i]);
}

Additionally, you can't always be sure count is being called on an array. If it's called on an object that implements Countable for example, the count method of that object will be called.

mfonda
  • 7,873
  • 1
  • 26
  • 30
  • As a follow up you might want to read http://josephscott.org/archives/2010/01/php-count-performance/ It basically details how getting the array length is o(1) and the impact of the repeated function calls. – TheClair Apr 29 '11 at 17:32
  • 1
    is making a function call always slower than not making one? I would not be surprised to find the interpreter to have inline optimization. – corsiKa Apr 29 '11 at 17:34
  • 1
    `the count method of that object will be called`, can you please explain this a bit – Steel Brain Aug 02 '14 at 09:09
  • 1
    @SteelBrain if a class implements the `Countable` interface, then calling `count($object)` is the same thing as calling `$object->count()`. See http://3v4l.org/oYSSC for example. – mfonda Aug 05 '14 at 18:03
  • `you're still making a function call when which is slower than not making one` This statement can be wrong. If you are doing manual traversal, that is `O(n)` operation. But if you just want to retrieve a pre calculated value, then operation is `O(1)`. – Jamshad Ahmad Apr 16 '20 at 21:59