Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:79797
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.212.174 as permitted sender)
Message-ID: <54920623.20207@gmail.com>
Date: Wed, 17 Dec 2014 22:39:31 +0000
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: internals@lists.php.net
References: <548FEE87.7020602@gmail.com> <alpine.DEB.2.11.1412171204040.4080@whisky.home.derickrethans.nl> <CAFp73Xtk5yTEWhWoaVndXDp09BisPfACPu7ucaX4DQiPaYZ4gg@mail.gmail.com> <CACQesk6GTq0z017_9HvZu5VmUeOABH1gdxYdKKShgEDVxS0DXA@mail.gmail.com> <5491B77A.4020004@gmail.com> <5491FE29.1090106@gmail.com>
In-Reply-To: <5491FE29.1090106@gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] [RFC][VOTE] Objects as Keys
From: rowan.collins@gmail.com (Rowan Collins)

On 17/12/2014 22:05, Rowan Collins wrote:
> For one thing, I think it might be interesting to explore whether real 
> objects as keys is actually as difficult as some people are assuming. 
> I can naively imagine a few ways it could be implemented that seem in 
> my mind to have minimal impact on any array that doesn't use it, but 
> haven't yet seen anyone seriously discuss any possible approaches. 

In fact, to expand on this, I'm going to stick my neck out and tell 
everyone my crackpot theory, which someone who actually understands the 
engine will probably demolish in 5 seconds flat, but makes sense in my 
mind. :P

The implementation of arrays could remain the same, with a single 
pointer to a second "shadow" HashTable, which would only be initialised 
when an object was actually added as a key. Thus the memory overhead 
would be reserving a single pointer per array (not per item), and the 
execution overhead (for any existing array usage) would be a single 
if(shadowPointer) check in a few key places.

The idea would be that the object would still be hashed - e.g. by 
default with spl_object_hash, but with __hash if set - and that key 
would be stored in the normal way. However, an extra entry would be 
added to the shadow array, as though you had also called $shadow[ 
$obj->__hash() ] = $obj.

We might want to do something tricksy to the key, like adding a null 
byte at the beginning, to make it less likely for a scalar key and an 
object hash to collide. This would also allow further short-cutting in 
lookups, since if the first byte was not \0, there would be no chance of 
a match in the shadow array. (If it was \0, there might still not be a 
shadow object, because null-prefixed strings are actually valid scalar 
keys, but this seems unlikely to be a common occurrence.)

Whenever an array key is taken as *input* (e.g. $foo[$bar], 
array_key_exists()), the hash function would be called (much as in the 
current RFC), and the corresponding value could be returned directly - 
the shadow table would not need to be touched, so performance would be 
identical to that of the current proposal.

A lookup in the shadow array would need to happen only when writing to 
the array, and when a key was being given as *output* (e.g. foreach ( $a 
as $k => $v ), array_search(), key()). This would happen at the speed of 
normal random access, and scale with the number of objects used as keys, 
not the number of items in the main array.

Like I say, I'm sure this is full of holes, and I'll leave it there 
before I get too far down a dead end, but I thought it might be a more 
productive line of thought than "this will probably never happen".

Regards,

-- 
Rowan Collins
[IMSoP]