Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:80954
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.192.52 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <20150122064308.3877D5F8EC@mx.zeyon.net>
References: <20150122064308.3877D5F8EC@mx.zeyon.net>
Date: Thu, 22 Jan 2015 06:49:18 +0000
Message-ID: <CAKxcST-D-msCVVxvKn-vsmaxH5vBQXGH1-KS0vLaYzC0D1Gu7Q@mail.gmail.com>
To: Benjamin Coutu <ben.coutu@zeyos.com>
Cc: Nikita Popov <nikita.ppv@gmail.com>, PHP Internals List <internals@lists.php.net>, 
	Dmitry Stogov <dmitry@zend.com>, Xinchen Hui <xinchen.h@zend.com>
Content-Type: multipart/alternative; boundary=001a11c2c01e3babfb050d381238
Subject: Re: [PHP-DEV] Improvements to Hastable Bucket structure
From: dragoonis@gmail.com (Paul Dragoonis)

--001a11c2c01e3babfb050d381238
Content-Type: text/plain; charset=UTF-8

On 22 Jan 2015 06:43, "Benjamin Coutu" <ben.coutu@zeyos.com> wrote:
>
> Hi,
>
> Currently a hashtable bucket has to store both, the numeric index "h" and
a potential pointer to a string key "key".
>
> There is room for improvement here because "h" and "key" are conceptually
mutually exclusive. I therefore propose to unionize "h" and "key" to
effectively save the overhead of having to reserve space for both.

This conceptually makes sense if you I deed just need one or the other but
not both.

Have you implemented this yet ? Have you benchmarked it ?

>
> Now, in order to still be able to distinguish between an integer key and
a pointer to a string key, one could use either of two approaches.
>
> === 1. Use flags of embedded zval (maybe _zval_struct.u1.v.*) ===
>
> If the is-key-flag is set in the embedded zval then its a string key, if
not then its an integer. This is of course only possible if _zval_struct.u1
is usable for this (I could not quickly tell).
>
> === 2. Pointer tagging ===
>
> On a 64/32-bit machine all pointers will be aligned to 8/4 bytes meaning
that their last 3/2 bits will always be zero. We can exploit this to
effectively store information about the pointer in those bits.
>
> We will use the last bit to distinguish between a pointer and an
63/31-bit integer, and the second last bit to distinguish between a pointer
to a string key or pointer to the overflowing integer (64/32 bit). Here is
a (8-bit) sample:
>
> LLLLLLL1: integer (effectively 63/31)
> PPPPPP00: pointer to zend_string (string key)
> PPPPPP10: pointer to zend_ulong (in case integer key is > 63/31 bit)
>
> One will then be able to use simple shifting and bitwise operations to
extract the correct meaning.
>
> Please let me know your thoughts!
>
> Cheers,
>
> Ben
>
> --
>
> Benjamin Coutu
> Zeyon Technologies Inc.
> http://www.zeyos.com
>
>
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php
>

--001a11c2c01e3babfb050d381238--