Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:20200
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Message-ID: <4380C334.9030709@hardened-php.net>
Date: Sun, 20 Nov 2005 19:40:52 +0100
User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716)
MIME-Version: 1.0
To: PHP internals <internals@lists.php.net>
Content-Type: multipart/mixed;
	boundary="------------030509080802040102030207"
Subject: [Fwd: Re: Hash Function change between PHP4 and PHP5]
From: sesser@hardened-php.net (Stefan Esser)

--------------030509080802040102030207
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Here the forwarded answer by Ralf Engelschall, because in the original
name the address of internals was wrong...

Stefan

-- 
--------------------------------------------------------------------------
 Stefan Esser                                               sesser@php.net
 Hardened-PHP Project                         http://www.hardened-php.net/

 GPG-Key                gpg --keyserver pgp.mit.edu --recv-key 0x15ABDA78
 Key fingerprint       7806 58C8 CFA8 CE4A 1C2C  57DD 4AE1 795E 15AB DA78
--------------------------------------------------------------------------


--------------030509080802040102030207
Content-Type: message/rfc822;
 name="Re: Hash Function change between PHP4 and PHP5"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="Re: Hash Function change between PHP4 and PHP5"

X-Account-Key: account9
X-Envelope-From: <rse@engelschall.com>
X-Envelope-To: <php@nopiracy.de>
X-Delivery-Time: 1132511375
Received: from mail.hardened-php.net (hardened-php.net [81.169.159.221])
	by mailin.webmailer.de (8.13.1/8.13.1) with ESMTP id jAKITYG1006991
	for <php@nopiracy.de>; Sun, 20 Nov 2005 19:29:35 +0100 (MET)
Received: from visp1.engelschall.com (visp1.engelschall.com [195.30.6.144])
	by mail.hardened-php.net (Postfix) with ESMTP id F3DFD1200EA
	for <sesser@hardened-php.net>; Sun, 20 Nov 2005 19:11:11 +0100 (CET)
Received: by visp1.engelschall.com (Postfix, from userid 21100)
	id 1F8C01B4484A; Sun, 20 Nov 2005 19:29:39 +0100 (CET)
Received: by en1.engelschall.com (Postfix, from userid 10000)
	id 30613A17D9; Sun, 20 Nov 2005 19:29:13 +0100 (CET)
Date: Sun, 20 Nov 2005 19:29:13 +0100
From: "Ralf S. Engelschall" <rse@engelschall.com>
To: Stefan Esser <sesser@hardened-php.net>
Cc: php-internals@lists.php.net, Andi Gutmans <andi@zend.com>
Subject: Re: Hash Function change between PHP4 and PHP5
Message-ID: <20051120182913.GA45046@engelschall.com>
Reply-To: rse@engelschall.com
References: <43808EBA.6060706@hardened-php.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <43808EBA.6060706@hardened-php.net>
Organization: Engelschall, Germany.
User-Agent: Mutt/1.5.11 OpenPKG/CURRENT

On Sun, Nov 20, 2005, Stefan Esser wrote:

> I just realised, that between PHP4 and PHP5 we changed the hash function
> used within zend_hash.h from DJBX33X to DJBX33A. The diff is here =>
> http://cvs.php.net/diff.php/ZendEngine2/zend_hash.h?ws=0&r1=1.57&r2=1.58&ty=u
>
> Does anyone remember the exact reason for that? Or was the change done
> by accident when the loops were unrolled? I have no idea if there is a
> big difference for our hashing needs, but I am just curious if we
> changed it because of benchmarks...

I don't know anything about the decisions within PHP development,
but the root reference for both are certainly my OSSP act sources:
http://cvs.ossp.org/getfile/ossp-pkg/act/act_hash_fct.c

There I've done in 2002 a comparison of mostly all known
(non-cryptography) hash functions which were in common use at this
time, including DJBX33A and DJBX33X. From my results (see the table
starting in the comment at line 80) you can see that both are more or
less equal, both in speed and distribution. The DJBX33A is the classical
one from DJB while DJBX33X is a revised version from him he used
later (but without any explanations by him or anybody else about the
advantages/disadvantages, although I think it is for just speed).

I guess Andi perhaps has just overlooked the small subtle difference
("+" operation for DJBX33A and "^" for DJBX33X), because as his commit
log for PHP explains, his intention was to provide an optimized version
(via the loop unrolling) plus my explanation about this hash function.
So, the conversion from DJBX33A to DJBX33X was perhaps just by accident.

But it doesn't really hurt: as I said, DJBX33X and DJBX33A are more or
less equal in quality and speed. DJBX33X is even slightly faster on most
processors so choosing DJBX33X is fully ok. At least because of this I
personally also prefer DJBX33X over DJBX33A. No need to change anything
at least... ;-)

                                       Ralf S. Engelschall
                                       rse@engelschall.com
                                       www.engelschall.com



--------------030509080802040102030207--