Re: Name hashing function causing a perf regression

[Josef Bacik <jbacik@fb.com>]

On 09/12/2014 03:21 PM, Linus Torvalds wrote:
> On Fri, Sep 12, 2014 at 12:11 PM, Andi Kleen <andi@firstfloor.org> wrote:
>> Josef Bacik <jbacik@fb.com> writes:
>>>
>>> So the question is what do we do here?  I tested other random strings
>>> and every one of them ended up worse as far as collisions go with the
>>> new function vs the old one.  I assume we want to keep the word at a
>>> time functionality, so should we switch to a different hashing scheme,
>>> like murmur3/fnv/xxhash/crc32c/whatever?  Or should we just go back to
>>
>> Would be interesting to try murmur3.
>
> I seriously doubt it's the word-at-a-time part, since Josef reports
> that it's "suboptimal for < sizeof(unsigned long) string names", and
> for those, there is no data loss at all.
>
> The main difference is that the new hash doesn't try to finish the
> hash particularly well. Nobody complained up until now.
>
> The old hash kept mixing up the bits for each byte it encounters,
> while the new hash really only does that mixing at the end. And its
> mixing is particularly stupid and weak: see fold_hash() (and then
> d_hash() does something very similar).
>
> So the _first_ thing to test would be to try making "fold_hash()"
> smarter. Perhaps using "hash_long(hash, 32)" instead?
>
>                  Linus
>

Ok with the hash_long(hash, 32) change I get this

[jbacik@devbig005 ~/local] ./hash
Old hash table had 1000000 entries, 0 dupes, 0 max dupes
New hash table had 331504 entries, 668496 dupes, 5 max dupes
We had 292735 buckets with a p50 of 3 dupes, p90 of 4 dupes, p99 of 5 
dupes for the new hash

So that looks much better, not perfect but hlist_for_each through 5 
entries isn't going to kill us, I'll build a kernel with this and get 
back shortly with real numbers.  Thanks,

Josef