On 07/02/13 06:36, Jeroen De Dauw wrote:
Those benchmarks are only testing some rather small arrays no?
I did some stuff a while back as well: https://github.com/JeroenDeDauw/php/blob/master/profile/array-empty.php
That is an interesting way to do benchmarks. XHProf has a bug in it which caused the times it reported to be off by a factor of 100 or so for about half the runs. I fixed it, and also unrolled the size loop to allow the xhprof_enable() call to be done only once, reducing the effects of inaccurate RDTSC calibration. I increased the iteration count and switched to a normal loop counter instead of range() to avoid thrashing the L2 cache.
The XHProf overhead was distorting the count() case, since it adds a profiling hook to internal function calls. Specifying the XHPROF_FLAGS_NO_BUILTINS flag to xhprof_enable() reduced the time for counting small arrays by a factor of 2.
I added the "!" operator to the list of things to benchmark.
The results were:
* ! and empty() within an error bar of each other, ~700ns per iteration * Triple-equals took 1300ns per iteration * count() took around 3us plus 370ns per array element (determined by linear regression).
The modified script: http://paste.tstarling.com/p/JYnLPi.html The XHProf patch: http://paste.tstarling.com/p/tgCAyC.html
The reason count() is O(N) in this case is because $array is a reference. See zend_send_by_var_helper in zend_vm_def.h:
} else if (PZVAL_IS_REF(varptr)) { zval *original_var = varptr;
ALLOC_ZVAL(varptr); ZVAL_COPY_VALUE(varptr, original_var); Z_UNSET_ISREF_P(varptr); Z_SET_REFCOUNT_P(varptr, 0); zval_copy_ctor(varptr);
If you pass the array as a non-reference parameter, you get O(1) performance of count():
function a( $array ) { for ( $i = 0; $i < 10000000; $i++ ) { $a = count( $array ) == 0; } }
It takes around 2us per iteration that way, regardless of array size.
-- Tim Starling