Re: scm_string_hash suboptimal?

[Rob Browning]

Florian Weimer <address@hidden> writes:

> Looking for a good hash function for strings, I stumbled across
> scm_string_hash guile-core/libguile, but it doesn't look too well:

Actually the current hash in symbols.c actually downcases all the
characters, so it's even less discriminating.  (Shouldn't we have a
separate string hasher that's case sensitive?)

After you posted I was kind of curious, knowing that a faster hash
algorithm (and one that minimizes collisions) might help the
performance of guile and many guile apps substantially, and so I
started poking around on the web for hash table related information.
I also realized that most of the hash algorithms only work on one byte
of data at a time, and on modern CPU's, unless the compiler's *really*
smart, that might not give you the best performance (though it'd be
hard to say without testing).  Given that, it seemed like working on
32 bit chunks until you get down to the last few bytes might be
preferable

So is anyone here well versed in the "state of the art" hash-table
wise?  If there is a "right thing", I'd be happy to read up on it and
perhaps implement it.  It would also be nice if I could add
dynamically resizing tables, if anyone knows of a good documented
algorithm.

Just poking around randomly with google, I came across a somewhat
interesting algorithm, but it's a lot more thorough than what we're
doing, and I have no idea if it's actually any good -- hasn't been
debunked, or whatever:

  http://burtleburtle.net/bob/hash/evahash.html

Thanks

-- 
Rob Browning <address@hidden> PGP=E80E0D04F521A094 532B97F5D64E3930