RE: string hash

[Richter, Jörg <Joerg.Richter@...>]

Denis wrote:

> 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).

Considering that this check is in the fast-path and lengths are mostly different
might explain why I have seen this.

> PS: Do you know of some scheme (or reflexion on the topic) to define a
> proportion of big strings to hash?

I am not sure I understand you. Do you mean a scheme like Lua is doing to hash 
not all bytes of the string? If so, no not really. 

Interesting side story: Recently I instrumented most of our hash-tables to dump
a histogram of bucket lengths. Including the Lua string table. The first output was
somewhat shocking because some buckets of the string table had 200 and more 
entries.
Turns out nearly every string in this bucket was a backtrace only differing in one line 
number. Hashing the whole string, or doing lazy interning, would have helped.
But we never noticed any slowdown because of that.
(This was with Lua 5.1)

   Jörg