Re: Name hashing function causing a perf regression

[Josef Bacik <jbacik@fb.com>]

On 09/12/2014 06:01 PM, Linus Torvalds wrote:
> On Fri, Sep 12, 2014 at 2:25 PM, Josef Bacik <jbacik@fb.com> wrote:
>>
>> Ok I have a good direction to take this in, so far the best results have
>> been to change fold_hash() to hash_64(hash, 32) and change d_hash to do this
>>
>> static int *d_hash(int *table, unsigned long parent, unsigned int hash)
>> {
>>          hash += (unsigned long) parent / L1_CACHE_BYTES;
>>          hash += hash_32(hash, d_hash_shift);
>>          return table + (hash & d_hash_mask);
>> }
>>
>
> It really should be sufficient to just do
>
>    static int *d_hash(int *table, unsigned long parent, unsigned int hash)
>    {
>          hash += (unsigned long) parent / L1_CACHE_BYTES;
>          return table + hash_32(hash, d_hash_shift);
>    }
>
> because the hash_32() function should already reduce the hash to its
> second argument (d_hash_shift) and mix around the bits sufficiently.
>
> I'm a *bit* nervous about the cost of this all, especially on CPU's
> where integer multiplies are expensive, but obviously we need to
> improve on the final hashing.
>
> Just out of interest, how good/bad does the hash look if the *only*
> change you do is the above d_hash() thing (ie just leave the
> fold_hash() thing alone?)
>
>


[jbacik@devbig005 ~/local] ./hash
Old hash table had 1000000 entries, 0 dupes, 0 max dupes
New hash table had 62200 entries, 937800 dupes, 90 max dupes
Fnv hash table had 988406 entries, 11594 dupes, 3 max dupes
We had 49800 buckets with a p50 of 8 dupes, p90 of 45 dupes, p99 of 80 
dupes for the new hash

"New hash" is the number you want.  Not as bad as originally, not as 
good as replacing fold_hash with hash_64 and not changing d_hash.  Thanks,

Josef