Re: Zend engine's hashtable performance tweaks

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