Re: string hash
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: string hash
- From: spir <denis.spir@...>
- Date: 2012年12月13日 12:17:01 +0100
On 13/12/2012 08:21, Richter, Jörg wrote:
Strings are stored in a hash table but the string hash value is reduced
modulo the size of the hash table and so it helps to compare string hash
values for colliding strings before resorting to memcmp. See
http://www.lua.org/source/5.2/lstring.c.html#luaS_newlstr
After reading this I applied the same optimization to my hash table
implementation.
Are you sure this is worthwhile? My unrepresentative performance tests are
somewhat slower (2-3%) than without this extra compare.
But I have no performance tests for Lua to double check.
Perhaps anyone can run their tests with "h == ts->tsv.hash &&" commented out.
Jörg
I'll do some perf tests probably later today. It's for a plain C string pool
(don't know if it looks like Lua's, haven't checked).
As with lua strings, since they know their sizes and thus I can use memcmp
instead of strcmp, size equality must be checked before, so there is a second
filter there anyway (after the one due to hash & modulo). This may explain why
yet another filter on hash alone possibly does not help much (except maybe if
strings commonly have same size).
Denis
PS: Do you know of some scheme (or reflexion on the topic) to define a
proportion of big strings to hash?