Zend engine's hashtable performance tweaks

Sorry for no attachments in previous message, I think my attachments
weren't redirected with message by lists.php.net email confirmation
system. I send them again, and for sure I attach links to public copy of
them over HTTP:
https://gist.github.com/761094 - php-5.3.4-hashtable-optimization.patch
https://gist.github.com/761096 - apc-3.1.6-hashtable-optimization.patch

Hello,
I work for social network company, where we were running optimization
project. One of it's results is patch to Zend engine's Hashtable, which
we
want to share and ask you for comments and improvements.

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.
• More macros were added to replace repetitive constructs.
• New constants were added to allow:
  -- Creating new hashtables of size at least X (where 4 and 8 are
  reasonable), which makes no rehashing and reallocing memory while
  changing
  size to 2 and then to 4.
  -- For small tables it's better to extend them by a factor of 4 times,
  not
  2, to make rehashing cost smaller for most hashtables, of cost of little
  higher memory consumption.
  -- For large tables it's better to have other load factor, closer to 1,
  while for small tables it's better to use load factor closer to 0.5.
• APC was patched to take changes in Bucket structure into account.

How was it tested?
It was tested with make test, where one more (comparing to original
sources) test fails, but it's most probably because
http://bugs.php.net/bug.php?id=48858 - IMO test is badly constructed (is
too simple) and any change of hashing function makes it fail. Also it was
tested on our testing environment and production servers against >30mln
requests to our site, with 120requests/s at peak on Xeon @ 2.50GHz with
8GB RAM running Debian Linux.

What is the gain?
After tests CPU usage dropped by about 4% -6%.
Memory footprint goes up just by few percent.

What can be done in future?

• Make new constants configurable by php.ini.
• Test if changing arEmpty from byte-array to bit-array helps on
  performance.
• Tweak default constants' values using some real-live benchmarks.
• Prove (or modify and prove) hash function to have property, that it has
  no collisions if two keys don't differ on no more than 6 bytes, which
  will
  lead to memcmp omit first (or last) 6 bytes of key. Also simpler thing
  may
  be proven, that is it has no collisions if two keys are not longer than 6
  bytes, which will make most string keys omit memcpy at all.

The patch was created and tested against php-5.3.0, apc-3.1.3p1, then
merged with php-5.3.4, apc-3.1.6 without conflicts, and for these last
versions patches are attached. Also, it shouldn't conflict with
http://wiki.php.net/rfc/performanceimprovements .

hi,

Did you forget to attach the patch? Attach it as .txt so the list
won't reject it.

Cheers,

On Fri, Dec 31, 2010 at 3:40 PM, Marcin Babij
marcin.babij@nasza-klasa.pl wrote:

Hello,
I work for social network company, where we were running optimization
project. One of it's results is patch to Zend engine's Hashtable, which we
want to share and ask you for comments and improvements.

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.
• More macros were added to replace repetitive constructs.
• New constants were added to allow:
  -- Creating new hashtables of size at least X (where 4 and 8 are
  reasonable), which makes no rehashing and reallocing memory while changing
  size to 2 and then to 4.
  -- For small tables it's better to extend them by a factor of 4 times, not
  2, to make rehashing cost smaller for most hashtables, of cost of little
  higher memory consumption.
  -- For large tables it's better to have other load factor, closer to 1,
  while for small tables it's better to use load factor closer to 0.5.
• APC was patched to take changes in Bucket structure into account.

How was it tested?
It was tested with make test, where one more (comparing to original sources)
test fails, but it's most probably because
http://bugs.php.net/bug.php?id=48858 - IMO test is badly constructed (is too
simple) and any change of hashing function makes it fail. Also it was tested
on our testing environment and production servers against >30mln requests to
our site, with 120requests/s at peak on Xeon @ 2.50GHz with 8GB RAM running
Debian Linux.

What is the gain?
After tests CPU usage dropped by about 4% -6%.
Memory footprint goes up just by few percent.

What can be done in future?

• Make new constants configurable by php.ini.
• Test if changing arEmpty from byte-array to bit-array helps on
  performance.
• Tweak default constants' values using some real-live benchmarks.
• Prove (or modify and prove) hash function to have property, that it has no
  collisions if two keys don't differ on no more than 6 bytes, which will lead
  to memcmp omit first (or last) 6 bytes of key. Also simpler thing may be
  proven, that is it has no collisions if two keys are not longer than 6
  bytes, which will make most string keys omit memcpy at all.

The patch was created and tested against php-5.3.0, apc-3.1.3p1, then merged
with php-5.3.4, apc-3.1.6 without conflicts, and for these last versions
patches are attached. Also, it shouldn't conflict with
http://wiki.php.net/rfc/performanceimprovements .

--
Marcin Babij
nasza-klasa.pl

--

--
Pierre

@pierrejoye | http://blog.thepimp.net | http://www.libgd.org

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