On Fri, 31 Dec 2010 14:40:44 -0000, Marcin Babij
<marcin.ba...@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
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
