Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:92918
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain zend.com designates 157.56.111.110 as permitted sender)
To: Matt Wilmas <php_lists@realplain.com>, "internals@lists.php.net"
	<internals@lists.php.net>
CC: Nikita Popov <nikita.ppv@gmail.com>, Xinchen Hui <laruence@php.net>
Thread-Topic: New HashTable implementation?
Thread-Index: AQHRoaq+UID7yar2ukuSm9Qd4neWEp+gkoux
Date: Fri, 29 Apr 2016 07:51:53 +0000
Message-ID: <BY2PR0201MB178472FF9F141CE65F60BC30BF660@BY2PR0201MB1784.namprd02.prod.outlook.com>
References: <70BE415E8A7D439FBBEB3817F61577D5@pc1>
In-Reply-To: <70BE415E8A7D439FBBEB3817F61577D5@pc1>
Accept-Language: en-US
Content-Language: en-US
spamdiagnosticoutput: 1:23
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 29 Apr 2016 07:51:53.4720
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 32210298-c08b-4829-8097-6b12c025a892
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY2PR0201MB1783
Subject: Re: New HashTable implementation?
From: dmitry@zend.com (Dmitry Stogov)

Hi Matt,

I also tried different hash functions (including mumur3) and came to simila=
r result.
Faster function but more hash collisions.
Actually these collisions occurs not because of different hash values, but =
because of small hash array size.
Also the way we transform hash value into hash array index (use low bits) a=
lso may matter.
If we decrease hash load-factor, we get less collisions, but use more memor=
y and this also leads to cache misses increase.

You are welcome to try Robin-Hood, in case you get positive results we may =
switch to it (however I'm sceptical)

Thanks. Dmitry.

________________________________________
From: Matt Wilmas <php_lists@realplain.com>
Sent: Friday, April 29, 2016 3:04:44 AM
To: internals@lists.php.net
Cc: Dmitry Stogov; Nikita Popov; Xinchen Hui
Subject: New HashTable implementation?

Hi all,

Last June, it was briefly mentioned about changing PHP's string hash
function [1] (DJB33 *seems* pretty horrible, after all, as far as
collisions...).  So 8 months ago I tried almost, if not, a half-dozen of
them (including Murmur3) that were simple enough to quickly toss in.

The result?  In all cases, I believe, fewer instructions (in zend_hash_find=
,
and the hashing function), BUT also a slight-to-small increase in cache
misses in Wordpress and other scripts...

And in a test filling an array with a million "string_$i" keys (high
collision pattern for DJB33?), the speed was halved by the *huge* cache mis=
s
increase. :-/

I couldn't quite understand what was happening, where, if there were fewer
collisions...  Misses all spread out in the hash-array?

So there didn't seem to be anything useful to gain there.


Now, after seeing Bogdan's hash optimization idea last month [2], and
reading Nikita's blog post again, I had some ideas I'd like to try --
assuming nobody else is planning major changes. :-)  Besides Nikita, I'm
addressing Dmitry and Xinchen because your names are on some minor hash
items on the 7.1 ideas wiki [4].

I'm thinking of a Robin Hood implementation with Universal hashing [5] (of
int keys and the string hashes).  I haven't touched any code yet, but think
I've worked out all the details in my head, and am ready to take a stab at
it.  I think it's fairly simple to get the basics working; and when I see
how that goes, I can do the additional optimizations I have in mind that it
allows (including reduced memory, on 64-bit at least).

Question: Can I use zval.u1.v.reserved ?  I guess I'll find out otherwise.
:-O


The string hash function itself is really a separate thing [6], but fasthas=
h
[7] (not to be confused with "superfast") looks like a good one that I
missed before...  After thinking about things, I think we could even
keep/use a 64-bit hash on 32-bit arch.


Well, just wanted to mention it first if anyone has a comment. :-)  Should
be interesting, but no idea how it'll perform (lookups should be very, very
fast (upsizing also); but cache factors and inserts/deletes are wildcards).
Wish me luck!?


Thanks,
Matt

[1] https://marc.info/?l=3Dphp-internals&m=3D143444845304138&w=3D2
[2] https://marc.info/?t=3D145744248100001&r=3D1&w=3D2
[4] https://wiki.php.net/php-7.1-ideas
[5] https://en.wikipedia.org/wiki/Universal_hashing
[6] https://github.com/rurban/smhasher
[7] https://github.com/rurban/smhasher/blob/master/doc/fasthash64