Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:41851
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain Opus1.COM designates 192.245.12.8 as permitted sender)
Date: Mon, 10 Nov 2008 22:36:36 -0800
In-reply-to: <A6FE07AF-3044-4DDC-B08E-D9048659FE9A@tekrat.com>
To: shire <shire@tekrat.com>
Cc: Stan Vassilev | FM <sv_forums@fmethod.com>, internals@lists.php.net
Message-ID: <CA31D996-86AD-4BAE-8160-847B20C0650C@opus1.com>
MIME-version: 1.0
Content-type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
Content-transfer-encoding: 7bit
References: <7e270cea0810191211w2cb77075y5e0ad78c2f7306f7@mail.gmail.com>
 <243C7392-C6A0-4EE8-8AAA-34964E78D453@tekrat.com>
 <EC8C4CC0-4089-422B-9223-CCDD8A796341@pooteeweet.org>
 <e382ba0811050722k34c3c3e6vfe082b0a6adb1e38@mail.gmail.com>
 <4022974B-4A13-4AB0-A282-973503200406@tekrat.com>
 <38820B1D-6D5F-4B42-9FEE-0CDF23142A57@tekrat.com>
 <140FB8F69197441FAB5F45A64FDA946E@pc>
 <753B18C7-AC2F-4C96-B9CF-9FF5A042B96C@tekrat.com>
 <C3A3569A09AF4A82BB215EFD6C2C4B46@pc>
 <A6FE07AF-3044-4DDC-B08E-D9048659FE9A@tekrat.com>
Subject: Re: [PHP-DEV] An optimization idea
From: ron@Opus1.COM (Ronald Chmara)


On Nov 10, 2008, at 5:24 PM, shire wrote:
>>>
>>> It sounds like this would only work if the array contents where  
>>> static though, as you're mapping a constant string to the  
>>> contents of the  hash (or did I misunderstand and you'd be  
>>> mapping string const. values  to hash IDs?).
>> My point is, replacing this process:
>> $a['foo'] or $a->foo -> compute hash of 'foo' -> find item for  
>> hash 'foo' -> many items? -> resolve conflict -> return item
>> With this process:
>> $a[% string_literal_id_5 %] -> lookup item key 5 for array ->  
>> return item
>> Notice we skipped hash generation, and conflict resolution  
>> altogether. We only have the lookup for the integer id.
>> If some additional work is done, even this lookup can be  
>> eliminated and make this an O(1) process.
>> If instead the coder used variable:
>> $a[$bar] or $a->$foo (var array lookup and var var object lookup),  
>> then this optimization can't kick in, and the existing algorithm  
>> will be used.
>> However "static" access is the predominant usage, especially for  
>> objects, but also for arrays, so this should have significant impact.
>
> Thanks for the clarification, this is pretty much the same idea as  
> what I've been interested in working on next.  I think I was more  
> inclined to store an extra hash value within the zvals themselves,  
> with the hope that this could be expanded to non-constant values.   
> I believe ruby implements it's lookups this way (noted just for  
> reference, not as an argument to copy another language ;-)  ).  Any  
> thoughts on reasons not to do this (other than increasing the size  
> of zval struct), it's pretty simple to implement this for static  
> values I believe, dynamic values are a lot more difficult obviously...

Since nobody else has chimed in with the obvious (to me, anyways):

I've worked with some code that uses disgustingly huge (>512Mb)  
arrays, largest implementation was a single 2.5 Gb array (before we  
took the offending programmer into a room and had a... chat).

I'd be interested in seeing some metrics on the needed extra CPU  
ticks for determining if an array (or array sub-element) is static or  
dynamic under the scheme, as well as the extra memory for storing an  
(many?) extra value(s). It sounds like it might be totally livable,  
if done right... done wrong, we could be looking at millions of CPU  
hits for checking millions of single element static arrays.... (and  
yes, storing millions of values as single element arrays is "doing it  
wrong", but I've learned not to underestimate the creativity of  
people who write software).

Oh, and while we're at it, what about "re-assigning" "static" arrays?

The idea sounds good, the corner-cases on mis-implementations are  
where it always becomes amusing.

-Bop