Re: [PATCH] Fast String Hash

[David Olofson <david@...>]

On Monday 17 December 2007, Mike Pall wrote:
[...]
> The new hash algorithm is a bastardized variant of Bob Jenkins'
> fast rotate-and-mix hash. It hashes up to 12 chars from a string,
> picked from the start, middle and end. The basic ideas are: less
> fetches, more bit mixing, no loops and a constant hash time.

Brilliant! Can I be as rude as to blatantly steal this for EEL? 
(http://eel.olofson.net/ - LGPL license.)

I particularly like the constant hash time part, as I'm into hard real 
time systems. :-)


> CAVEAT: this version relies on UNALIGNED access of 32 bit words
> for speed. I.e. it probably only works on x86 and will certainly
> crash on most other architectures. Sorry, I don't have the time
> right now to add a (fast) replacement with aligned accesses. Feel
> free to adapt the patch to your needs.

Would it be acceptable to just round the middle and end indices down 
to the nearest aligned address?

Could probably be config/compile time detected and used only on 
platforms that need it. Unfortunately though, there are CPU families 
where older ones can't do unaligned access, whereas newer ones can; 
for example MC68000..20 vs MC60030, but well... I guess you'd just 
compile for the most restricted CPUs your code will be used on - just 
as it is with the x86 family and SIMD extensions and whatnot.

BTW, have you considered the penalty of unaligned access in this 
context? (Don't even know if it's significant on modern x86 in 
situations like this...)


//David Olofson - Programmer, Composer, Open Source Advocate

.-------  http://olofson.net - Games, SDL examples  -------.
|        http://zeespace.net - 2.5D rendering engine       |
|       http://audiality.org - Music/audio engine          |
|     http://eel.olofson.net - Real time scripting         |
'--  http://www.reologica.se - Rheology instrumentation  --'