Re: [PATCH] Fast String Hash

[Mike Pall <mikelu-0712@...>]

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