> -----Original Message----- > From: Andone, Bogdan [mailto:bogdan.and...@intel.com] > Sent: Friday, March 18, 2016 11:58 AM > To: 'Nikita Popov' <nikita....@gmail.com> > Cc: internals@lists.php.net > Subject: RE: [PHP-DEV] Lazy keys comparison during hash lookups > > > -----Original Message----- > > From: Andone, Bogdan [mailto:bogdan.and...@intel.com] > > Sent: Wednesday, March 09, 2016 9:33 AM > > To: 'Nikita Popov' > > Cc: internals@lists.php.net > > Subject: RE: [PHP-DEV] Lazy keys comparison during hash lookups > > > > > > > > > -----Original Message----- > > > From: Andone, Bogdan [mailto:bogdan.and...@intel.com] > > > Sent: Tuesday, March 08, 2016 4:19 PM > > > To: 'Nikita Popov' > > > Cc: internals@lists.php.net > > > Subject: RE: [PHP-DEV] Lazy keys comparison during hash lookups > > > > > > > From: Nikita Popov [mailto:nikita....@gmail.com] > > > > Sent: Tuesday, March 08, 2016 3:43 PM > > > > To: Andone, Bogdan > > > > Cc: internals@lists.php.net > > > > Subject: Re: [PHP-DEV] Lazy keys comparison during hash lookups > > > > >On Tue, Mar 8, 2016 at 2:18 PM, Nikita Popov > > > > ><nikita....@gmail.com> > > > wrote: > > > > >> On Tue, Mar 8, 2016 at 2:01 PM, Andone, Bogdan > > > > <bogdan.and...@intel.com> wrote: > > > > >> Hi Guys, > > > > >> > > > > >> I would like to propose a small change into the DJBX33A hash > > > function > > > > algorithm which will make easier the key matching validations in > > hash > > > > lookup functions. > > > > >> > > > > >> The change addresses the modulo 8 tailing bytes of the key. For > > > these > > > > bytes we can use an 8 bit shift instead of a 5 bit shift; we also > > need > > > > to replace the ADD by XOR, in order to avoid byte level overflows. > > > This > > > > change ensures the uniqueness of the hash function transformation > > for > > > > the tailing bytes: supposing two strings have same partial hash > > value > > > > for the first Nx8 bytes, different combinations of tailing > > characters > > > > (with the same tail size) will always generate different keys. > > > > >> We have the following consequences: > > > > >> If two strings have: > > > > >> - same hash value, > > > > >> - same length, > > > > >> - same bytes for the first Nx8 positions, then they are equal, > > > > >> and the tailing bytes can be skipped during > > > > comparison. > > > > >> > > > > >> There is a visible performance gain if we apply this approach > > > > >> as > > we > > > > can use a lightweight memcmp() implementation based on longs > > > comparison > > > > and completely free of the complexity incurred by tailing bytes. > > > > For Mediawiki I have a 1.7% performance gain while Wordpress > > > > reports > > 1.2% > > > > speedup on Haswell-EP. > > > > >> > > > > >> Let’s take a small example: > > > > >> Suppose we have a key=”this_is_a_key_value”. > > > > >> The hash function for the first N x 8 byes are computed in the > > > > original way; suppose “this_is_a_key_va” (16bytes) will return a > > > partial > > > > hash value h1; the final hash value will be computed by the > > following > > > > sequence: > > > > >> h = ((h1<<8) ^ h1) ^ ‘l’; > > > > >> h = ((h<<8) ^ h) ^ ‘u’; > > > > >> h = ((h<<8) ^ h) ^ ‘e’; > > > > >> or, in only one operation: > > > > >> h = (h1<<24) ^ (h1<<16) ^ (h1<<8) ^ h1 ^ (‘l’<<16) ^ > > ((‘l’^‘u’)<<8) > > > ^ > > > > (‘l’^’u’^‘e’) > > > > >> We can see that ht=(‘l’<<16) ^ ((‘l’^‘u’)<<8) ^ > > > (‘l’^’u’^‘e’) cannot > > > > be obtained by any other 3 characters long tail. The statement is > > not > > > > true if we use ADD instead of XOR, as extended ASCII characters > > might > > > > generate overflows affecting the LSB of the higher byte in the > > > > hash value. > > > > >> > > > > >> I pushed a pull request here: https://github.com/php/php- > > > > src/pull/1793. Unfortunately it does not pass the travis tests > > because > > > > “htmlspecialchars etc use a generated table that assumes the > > > > current hash function” as noticed by Nikita. > > > > >> > > > > >> Let me know your thoughts on this idea. > > > > > > > > > > Hey Bogdan, > > > > > This looks like an interesting idea! I'm somewhat apprehensive > > about > > > > coupling this to a change of the hash function, for two reasons: > > > > > a) This will make it more problematic if we want to change the > > hash > > > > function in the future, e.g. if we want to switch to SipHash. > > > > > b) The quality of the new hash distribution is not immediately > > > clear, > > > > but likely non-trivially weaker. > > > > > So I'm wondering if we can keep the concept of using a > > > > > zend_ulong > > > > aligned memcmp while leaving the hash function alone: The > > zend_string > > > > allocation policy already allocates the string data aligned and > > padded > > > > to zend_ulong boundaries. If we were to additionally explicitly > > > > zero > > > out > > > > the last byte (to avoid valgrind warnings) we should be able to > > > compare > > > > the character data of two zend_strings using a zend_ulong memcmp. > > This > > > > would have the additional benefit that it works for normal string > > > > comparisons (unrelated to hashtables) as well. On the other hand, > > this > > > > is only possible for zend_string to zend_string comparisons, not > > > > for comparisons with static strings. > > > > > Regards, > > > > s/zero out the last byte/zero out the last zend_ulong I'd like to > > > > add another issue with relying on the hash for this > > which > > > I > > > > just remembered: We currently always set the top bit of the hash > > > > for strings (see > > > http://lxr.php.net/xref/PHP_TRUNK/Zend/zend_string.h#351), > > > > in order to ensure that hashes are never zero. This makes the hash > > > non- > > > > unique. > > > > Nikita > > > Yeah... I missed the top bit set, but I think it could be solved > > > somehow. > > Actually setting the top bit is not an issue. The transformation > > unicity shall be ensured for the tailing bytes only which are shifted > > to the left maximum 7(on 64bits)/3(on 32bits) positions; so they will > > never reach the top byte and setting the top bit will not harm in > > terms of tailing bytes. > > > > > Imho the strongest reason against the patch is the dependency > > > between the hash function and the key validation method but I have > > > the impression that this is not be the most dirty hack deployed ever > > > in > > PHP; > > > and I don't know very well what is the degree of compromise > > > acceptable for 1% speedup :-) > > Otherwise the concerns about the quality of the hash function and the > > intention to change it with SipHash or something else, I am afraid it > > will not bring much in terms of collisions reductions; the issue here > > is the fact that hash bucket selection uses only the last few bits of > > the hash value. Not sure how much could help here SipHash... > > Just for defending the technical feasibility of this POC I think that > > injective transformation for last tailing bytes could be deployed over > > theoretically any hash function. > > > > Thanks, > > Bogdan > > > > > On the other hand, your idea to zero the last zend_ulong in the > > > zend_string looks nice. There could be an additional potential gain > > also > > > from lightweight implementation of memcmp(). I will give it a try to > > see > > > if it gets better results than the current proposal. > > > I assume all zend_string allocation functions are located in > > > zend_string.h, correct? > > > > > > Thanks, > > > Bogdan > I worked a little bit of adapting the zend string allocation functions for > ensuring > long size alignment for both Zend and standard allocation, and for zeroing out > the end of the strings. > The sad surprise was to discover that there are other >100 situations, in > extensions mainly, where the zend strings are truncated by directly inserting > '0' > terminators in the middle of strings; all these situations needs to be > revised for > zeroing out the entire memory word enclosing the end of the string. > It will probably take a while for revising most of these places before having > a > correct real life run for being able to validate the POC. > Optimistically speaking, supposing POC will show motivating results, we will > probably need to enforce the Zend interface with respect to string truncation > - > at least a getter/setter pair for ZSTR_LEN where the setter should ensure also > synchronizing the string termination. > I suppose it will be an important effort for the community and I am not sure > how > much willingness will be in it. On the other side, the originally proposed > solution > does not have all this drawbacks and it offers 1% speedup by a localized > change > which could be easily reverted in the case we will get better results by a > better > string alignment in future. > > Thanks, > Bogdan I finalized the POC for ensuring strings granularity to zend_long size; you can find it here: https://gist.github.com/bogdanandone/cfde764f64137b57ce2a6f4a9b52e757 Unfortunately, the effort to zero-out the end of strings generates an overhead higher than the gain incurred by simplified zend_memcpy_aligned memcpy() & memcmp() implementations - I defined a simpler zend_memcpy_aligned() function used in zend_string.h and zend_ulong_memeq() used in zend_hash.c inherited from my original place. Overall I see ~1% loss on Worpress on my platform. I didn't spend time in fine tuning each place needing changes but I don't expect a real difference. Probably this is not the way to go and I finalize with a last buzz for the original patch proposal :)
Thanks, Bogdan
