Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:80952
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain zeyos.com designates 109.70.220.166 as permitted sender)
Date: Thu, 22 Jan 2015 07:43:03 +0100
To: Dmitry Stogov <dmitry@zend.com>,
	Xinchen Hui <xinchen.h@zend.com>,
	Nikita Popov <nikita.ppv@gmail.com>,
	"internals@lists.php.net" <internals@lists.php.net>
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset="UTF-8"
Message-ID: <20150122064308.3877D5F8EC@mx.zeyon.net>
Subject: [PHP-DEV] Improvements to Hastable Bucket structure
From: ben.coutu@zeyos.com (Benjamin Coutu)

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 m=
utually exclusive. I therefore propose to unionize "h" and "key" to effecti=
vely save the overhead of having to reserve space for both.

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.

=3D=3D=3D 1. Use flags of embedded zval (maybe _zval_struct.u1.v.*) =3D=3D=
=3D

If the is-key-flag is set in the embedded zval then its a string key, if no=
t then its an integer. This is of course only possible if _zval_struct.u1 i=
s usable for this (I could not quickly tell).

=3D=3D=3D 2. Pointer tagging =3D=3D=3D

On a 64/32-bit machine all pointers will be aligned to 8/4 bytes meaning th=
at their last 3/2 bits will always be zero. We can exploit this to effectiv=
ely 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 stri=
ng key or pointer to the overflowing integer (64/32 bit). Here is a (8-bit)=
 sample:=0A=0ALLLLLLL1: integer (effectively 63/31)
PPPPPP00: pointer to zend_string (string key)=0APPPPPP10: pointer to zend_u=
long (in case integer key is > 63/31 bit)

One will then be able to use simple shifting and bitwise operations to extr=
act the correct meaning.

Please let me know your thoughts!

Cheers,

Ben

--=20

Benjamin Coutu
Zeyon Technologies Inc.
http://www.zeyos.com