Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:51163
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: error (pb1.pair.com: domain nebm.ist.utl.pt from 193.136.128.22 cause and error)
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
To: internals@lists.php.net
References: <op.vok1p6osnpl9ht@pc-mbabij>
Date: Fri, 31 Dec 2010 17:56:48 -0000
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Organization: =?utf-8?Q?N=C3=BAcleo_de_Eng=2E_Biom=C3=A9di?=
 =?utf-8?Q?ca_do_IST?=
Message-ID: <op.volascn0idpuyk@damnation.dulce.lo.geleia.net>
In-Reply-To: <op.vok1p6osnpl9ht@pc-mbabij>
User-Agent: Opera Mail/11.00 (Win32)
Subject: Re: [PHP-DEV] Zend engine's hashtable performance tweaks
From: glopes@nebm.ist.utl.pt ("Gustavo Lopes")

On Fri, 31 Dec 2010 14:40:44 -0000, Marcin Babij  
<marcin.babij@nasza-klasa.pl> wrote:

> Why we do this?
> We run profiling on our production servers and found out that zend_hash_*
> functions take 10-20% CPU time of request. So there is some room for easy
> improvements.
>
> What was done?
> - Hash function in zend_hash.h was rebuilt and became much faster,  
> without losing the most important properties.
> - Hashtable implementation was changed from Simple chaining to Open
> addressing with linear probing, but with linked bucket, not included in
> hash array, which causes:
> -- Bucket structure to lose 2 pointers.
> -- Searching works similar, but don't have to jump with pointers stored  
> in different memory locations, inserting, deleting and rehashing don't  
> need
> to update linked list, but must search for first empty bucket, which is
> fast, because it scans continuous memory.
> -- Load factor decreases from 1.0 to 0.5-0.75 to make less collisions and
> faster hashtable, which in turn increases memory footprint a little.
> - Open addressing doesn't change significantly performance, but next  
> thing was to create new array (arEmpty), which is of size nTableSize  
> bytes,
> which keeps track of used/empty buckets and makes inserting and rehashing
> much faster. In future it can be tested as bit-array with size of
> nTableSize/8 bytes.

Nice work. Only two comments:

This is much faster than just testing the value of the Bucket pointer for  
NULL (BTW, NULL pointer != 0 bit pattern, but I guess this is a lost cause  
in PHP's codebase...)? I'm a bit surprised; though perhaps this could  
allow more cache hits (and indicates changing it into a bit array could  
very well be beneficial).

A patch against trunk would be nicer since that's where there's a chance  
this will be merged to. Also, since you're changing the hash function,  
html_table_gen.php must changed and run to regenerate html_tables.h. See  
http://lxr.php.net/xref/PHP_TRUNK/ext/standard/html_tables/html_table_gen.php#722  
(ignore the comment; there's obviously nothing unrolled).

-- 
Gustavo Lopes