Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:26412
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 64.233.162.193 as permitted sender)
DomainKey-Status: good
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
        s=beta; d=gmail.com;
        h=received:in-reply-to:references:mime-version:x-priority:content-type:message-id:cc:content-transfer-encoding:from:subject:date:to:x-mailer:sender;
        b=ngZ2DgqPAffw6c3IBhse9WkSEFrQWcOl8wHwoqf4x7xcSYbxBDCDnuZvsIb9WqdOo16et76qitQr52Dn3RNafdgjuy81RtGyvsGXpp/uE1hUR6jDa2Ui6goqc06HgI258JOpvNAzGXcWDhRA7lRpFFJoJopYBlqlquHFuOEGgwg=
In-Reply-To: <00db01c700d6$221c7480$0201a8c0@pc1>
References: <00dc01c6e231$3d091c80$0201a8c0@pc1> <016801c6e263$be69c400$0100a8c0@pc07653> <00db01c700d6$221c7480$0201a8c0@pc1>
Mime-Version: 1.0 (Apple Message framework v752.3)
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
Message-ID: <7DFBDE72-4CC9-4B88-A052-AE681FD07682@prohost.org>
Cc: internals@lists.php.net,
 Dmitry Stogov <dmitry@zend.com>
Content-Transfer-Encoding: 7bit
Date: Tue, 7 Nov 2006 15:35:04 -0500
To: Matt Wilmas <php_lists@realplain.com>
Sender: Ilia Alshanetsky <iliaal@gmail.com>
Subject: Re: [PHP-DEV] array/HashTable filling optimization
From: ilia@prohost.org (Ilia Alshanetsky)

Looks like a good optimization to me.


On 5-Nov-06, at 7:30 AM, Matt Wilmas wrote:

> Hi Nuno,
>
> Late reply, but I'm glad the idea was able to be used. :-)
>
>
> To the other hash people: While checking how Ilia made implode()  
> faster in
> 5.2, I think I found another optimization that can be done.  In
> zend_hash_copy/merge, it seems the zend_hash_quick_* functions can  
> be used
> instead for associative entries, thus saving the key from being hashed
> again, right?  I just checked, and it's definitely faster, how much  
> so being
> dependent on the key length of course...
>
> Patches for this simple additional optimization (hopefully):
> http://realplain.com/php/hash_quick_copy.diff
> http://realplain.com/php/hash_quick_copy_5_2.diff
>
>
> Thanks,
> Matt
>
>
> ----- Original Message -----
> From: "Nuno Lopes"
> Sent: Wednesday, September 27, 2006
>
>> 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...
>
> -- 
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

Ilia Alshanetsky