Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:25844
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: error (pb1.pair.com: domain php.net from 212.55.154.22 cause and error)
Message-ID: <016801c6e263$be69c400$0100a8c0@pc07653>
To: "Matt W" <php_lists@realplain.com>,
	<internals@lists.php.net>
References: <00dc01c6e231$3d091c80$0201a8c0@pc1>
Date: Wed, 27 Sep 2006 19:35:44 +0100
MIME-Version: 1.0
Content-Type: text/plain;
	format=flowed;
	charset="iso-8859-1";
	reply-type=original
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] array/HashTable filling optimization
From: nlopess@php.net ("Nuno Lopes")

Aaahh nice catch ;)

From a quick lookup in PHP sources I also found these functions were the 
same optimization can be applied:
zend_default_exception_new_ex() - trivial
convert_to_array() - not as easy as others
zend_object_std_init() - possibly
clone_wrapper_hash() - trivial (php-src/main/streams/streams.c)
compiler_globals_ctor()
...


Nuno


----- Original Message ----- 
> Hi all,
>
> I noticed awhile ago how most every use of zend[_u]_hash_init has nSize as
> 0.  Of course it isn't always known how many elements will be added to the
> array (nTableSize), but there are places where an accurate value could be
> used instead of getting the minimum default (8).  For anyone who doesn't
> know, HashTable sizes are a power of 2, and when there are more than that
> many elements, zend_hash_do_resize realloc's more memory to double the 
> table
> size, and then zend_hash_rehash basically goes through and "reinserts" all
> the elements again.
>
> I ran some tests to see the speed improvement from specifying the *actual*
> number of elements in hash_init, thus saving that extra work (_rehash
> mostly).  The "n+1" is with one more element (9, 17, 33...) that triggers
> another rehash when the actual number wasn't specified (most extreme).  (I
> used add_next_index_zval, so the direct zend_hash* functions would give
> slightly higher % I guess, being less overhead, right?)  Results with
> 5.2.0-RC4:
>
>          Elements
>  n   |   n      n+1
> ---------------------
> 8     |    0%   14.2%
> 16    | 11.0%   20.9%
> 32    | 13.5%   22.1%
> 64    | 12.6%   21.3%
> 128   | 11.7%   18.5%
> 256   |  9.3%   16.4%
> 512   |  8.6%   17.0%
> 1024  |  7.9%   15.8%
> 2048  |  4.8%   33.3%
> 4096  |  7.8%   28.3%
> 8192  | 10.2%   58.4%
> 16384 | 24.1%   70.5%
> 32768 | 34.5%   80.4%
> 65536 | 34.8%   68.6%
>
> I haven't looked thoroughly, but the only place I've seen that uses an
> non-zero nSize in hash_init (besides some in the core engine) is the
> unserialize() function. :-/  It seems the most simple and obvious place 
> that
> could be changed is in Zend/zend_variables.c:_zval_copy_ctor_func?  Just
> replace
>
> zend[_u]_hash_init(tmp_ht, 0, ...
> with
> zend[_u]_hash_init(tmp_ht, original_ht->nNumOfElements, ...
>
> Other than that, some of PHP's array functions and array-returning 
> functions
> (database fetch row functions, etc.) are ones I thought of that could be
> optimized like this.  Maybe create an array_init_size() macro to be used 
> in
> places where the number of elements can be easily determined?  Thoughts?
> I'd volunteer to look for places that could be updated and modify them. 
> :-)
>
>
> Thanks,
> Matt
>
> P.S.  I guess the array stuff applies for objects also?  But I don't know
> much about their internals...