Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:41850 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 53455 invoked from network); 11 Nov 2008 01:24:30 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 11 Nov 2008 01:24:30 -0000 Authentication-Results: pb1.pair.com smtp.mail=shire@tekrat.com; spf=permerror; sender-id=unknown Authentication-Results: pb1.pair.com header.from=shire@tekrat.com; sender-id=unknown Received-SPF: error (pb1.pair.com: domain tekrat.com from 69.63.177.213 cause and error) X-PHP-List-Original-Sender: shire@tekrat.com X-Host-Fingerprint: 69.63.177.213 sizzo.org Linux 2.6 Received: from [69.63.177.213] ([69.63.177.213:58330] helo=sizzo.org) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id CD/80-50375-CCED8194 for ; Mon, 10 Nov 2008 20:24:30 -0500 Received: from [172.23.16.120] (unknown [172.23.16.120]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by sizzo.org (Postfix) with ESMTPSA id 7557E6D4A0E; Mon, 10 Nov 2008 17:24:24 -0800 (PST) To: Stan Vassilev | FM In-Reply-To: X-Priority: 3 References: <7e270cea0810191211w2cb77075y5e0ad78c2f7306f7@mail.gmail.com> <243C7392-C6A0-4EE8-8AAA-34964E78D453@tekrat.com> <4022974B-4A13-4AB0-A282-973503200406@tekrat.com> <38820B1D-6D5F-4B42-9FEE-0CDF23142A57@tekrat.com> <140FB8F69197441FAB5F45A64FDA946E@pc> <753B18C7-AC2F-4C96-B9CF-9FF5A042B96C@tekrat.com> Message-ID: Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v929.2) Date: Mon, 10 Nov 2008 17:24:20 -0800 Cc: X-Mailer: Apple Mail (2.929.2) Subject: Re: [PHP-DEV] An optimization idea From: shire@tekrat.com (shire) On Nov 10, 2008, at 4:28 PM, Stan Vassilev | FM wrote: >> This wouldn't really help with the case here of "if ($array1 == >> $array2)..." though right? (not to say it's not good, just making >> sure I understand ;-) ). > > Yes I'm talking about speeding up scenarios full of hash lookups in > general. Ok, still seems though like this particular optimization might also provide additional benefits (albeit perhaps not nearly as significant). > > >> >> 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... -shire