Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:80960
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 09:36:53 +0100
To: Xinchen Hui <xinchen.h@zend.com>,
	Dmitry Stogov <dmitry@zend.com>
Cc: 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: <20150122083656.BE4E45F8EE@mx.zeyon.net>
Subject: Re: [PHP-DEV] Improvements to Hastable Bucket structure
From: ben.coutu@zeyos.com (Benjamin Coutu)

Too bad, didn't think Bucket->key->h was so ubiquitous that it actually kil=
ls the benefit of less memory allocation and tighter cache alignment in buc=
ket.=0A=0A=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Original =3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=0AFrom: Xinchen Hui <xinchen.h@zend.com>=0ATo: Dmitry Stogov <dmitry=
@zend.com>=0ADate: Thu, 22 Jan 2015 08:52:35 +0100=0ASubject: Re: [PHP-DEV]=
 Improvements to Hastable Bucket structure=0A=0A=0A=0AHey:=0A=0AOn Thu, Jan=
 22, 2015 at 3:36 PM, Dmitry Stogov <dmitry@zend.com> wrote:=0A> Hi,=0A>=0A=
> Xinchen already tried something similar, but it made PHP slower, because =
it=0A> made access to Bucket->key->h more expensive - two loads with most p=
robably=0A> two CPU cache misses instead of one.=0Ayes, the patch is here: =
https://github.com/laruence/php-src/tree/union-hash-key=0A=0Athanks=0A>=0A>=
 Thanks. Dmitry.=0A>=0A> On Thu, Jan 22, 2015 at 9:43 AM, Benjamin Coutu <b=
en.coutu@zeyos.com> wrote:=0A>>=0A>> Hi,=0A>>=0A>> Currently a hashtable bu=
cket has to store both, the numeric index "h" and=0A>> a potential pointer =
to a string key "key".=0A>>=0A>> There is room for improvement here because=
 "h" and "key" are conceptually=0A>> mutually exclusive. I therefore propos=
e to unionize "h" and "key" to=0A>> effectively save the overhead of having=
 to reserve space for both.=0A>>=0A>> Now, in order to still be able to dis=
tinguish between an integer key and a=0A>> pointer to a string key, one cou=
ld use either of two approaches.=0A>>=0A>> =3D=3D=3D 1. Use flags of embedd=
ed zval (maybe _zval_struct.u1.v.*) =3D=3D=3D=0A>>=0A>> If the is-key-flag =
is set in the embedded zval then its a string key, if=0A>> not then its an =
integer. This is of course only possible if _zval_struct.u1=0A>> is usable =
for this (I could not quickly tell).=0A>>=0A>> =3D=3D=3D 2. Pointer tagging=
 =3D=3D=3D=0A>>=0A>> On a 64/32-bit machine all pointers will be aligned to=
 8/4 bytes meaning=0A>> that their last 3/2 bits will always be zero. We ca=
n exploit this to=0A>> effectively store information about the pointer in t=
hose bits.=0A>>=0A>> We will use the last bit to distinguish between a poin=
ter and an 63/31-bit=0A>> integer, and the second last bit to distinguish b=
etween a pointer to a=0A>> string key or pointer to the overflowing integer=
 (64/32 bit). Here is a=0A>> (8-bit) sample:=0A>>=0A>> LLLLLLL1: integer (e=
ffectively 63/31)=0A>> PPPPPP00: pointer to zend_string (string key)=0A>> P=
PPPPP10: pointer to zend_ulong (in case integer key is > 63/31 bit)=0A>>=0A=
>> One will then be able to use simple shifting and bitwise operations to=
=0A>> extract the correct meaning.=0A>>=0A>> Please let me know your though=
ts!=0A>>=0A>> Cheers,=0A>>=0A>> Ben=0A>>=0A>> --=0A>>=0A>> Benjamin Coutu=
=0A>> Zeyon Technologies Inc.=0A>> http://www.zeyos.com=0A>>=0A>