[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: [PATCH] Fast String Hash**
**From**: Mike Pall <mikelu-0712@...>
**Date**: Thu, 20 Dec 2007 01:13:00 +0100

David Manura wrote:
> t = {}
> function t.a() if 0 then end end
> function t.b() end
> function t.c() end
> function t.d() end
> for n=1,20000000 do t.a() t.b() end
>
> That runs about 5% slower here with patch.
This is due to a hash collision between 'a' and 'b' in a
4-element table. An unfortunate coincidence, have a look at the
hash values and their 2 least-significant bits:
Lua hash Fast hash
a 00000080 886025fd
b 00000083 6479e2ed
c 00000082 79566169
d 00000085 3fdf0296
If you use 'e' instead of 'b', you'll find it runs 5% faster with
the patch. :-)
No matter how good the hash function is, the probability of at
least one collision for 4 keys in a 4-element table is rather
high. Which implies that one really wants a larger minimum hash
table size unless memory is at a premium.
BTW: 'if 0 then' -- umm, wanna confuse newbies? :-)
[Hint: if you come from C, Python or PHP -- this code snippet
does not do what you might think it does.]
--Mike