thanks for your reply
>Is yours a real problem? Do you have a program that does something
>useful to someone that is having performance problems because of
>this hashing?
yes, I am a online game server developer, and we use Lua to write the whole game's logic.
this is the real problem that happened in our server which stuck the server about 10 seconds.
since we didn't know the lua hash detail, so we used a ID generator function like this
function alloc_id(timestamp)
return ((timestamp& 0xffffffff) << 32) | ( small increment count )
end
we found the problem and fix it by change the id to string before put into table.
dst[ tostring(id) ] = info
so if someone don't know the hash detail, may be he will have the same problem.
thank you.
At 2021-03-10 20:47:06, "Roberto Ierusalimschy" <roberto@inf.puc-rio.br> wrote:
>> I found that lua table use 2^n to hash key. normaly we use the prime number to prevent hash collision.
>> now I use lua-5.3.4, and the code below will cost about 6 second because the hash table degenerates into a linked list
>> so why lua table don't use prime number to hash?
>
>Hashing with 2^n has the advantage that we can compute the modulo
>with (x & (size - 1)) (see macro 'lmod'), which is much cheaper
>than the '%' operator.
>
>Nontheless, for several types (all types that use addresses as hashes
>plus floats), Lua hashes with Mersenne numbers (2^n - 1), which are a
>"good approximation" for primes. The choice between the two hashes is
>based on how good we consider the initial hash (before the modulo).
>
>Integer keys tend to be sequential, which gives sequential keys
>after the modulo, which is good for hashes. So, for this quite
>common case, it is not worth paying the price of '%'.
>
>Of course, the worst-case for any hashing algorithm for unknown keys is
>O(n), even with prime sizes.
>
>Is yours a real problem? Do you have a program that does something
>useful to someone that is having performance problems because of
>this hashing?
>
>-- Roberto
