About SpookyHash

I’ve been having some issues with the last couple of labs and a little issue with the package I chose for my assignment. Once again my stubbornness has put me into a tight corner. I know this code is already very efficient, but I like to challenge myself. If you remember, I chose SpookyHash partially because it was Halloween. Ironically, the creator of SpookyHash (Bob Jenkins) gave it that name because it was released on Halloween.

Bob Jenkins created a family of non-cryptic hash functions. For detailed explanations check the wikipedia link above but to summarize:

  1. one_at_a_time:  this, or a variant of this method is what Perl uses for hashing.
  2. lookup2:  32-bit hash values, very little collisions, but still sensitive to hash flooding attacks.
  3. lookup3: consumes input in 96-bit chunks. Improving speed for large keys but leaves the possibility of increased complexity affecting the speed.
  4. SpookyHash: 128-bit hash function which is significantly faster than lookup3.

 

Seeing as how this guy created a family of hash functions, I doubt I’ll be able to make it better in any way. I’ve been looking at the code and have an idea where I want to benchmark and attempt some stuff. I was going to go through the code and see spots where I can do some strength reduction or some loop fission/fusion, but then I realized the compiler is probably already doing that.

Luckily for me this port of it hasn’t been touched for ~4 years. Back then it was more portable then Google’s cityhash, I say back then because I’m sure cityhash has been improved over the years. I couldn’t find a wiki for that but if you google it you can see their GitHub. What I’ve linked there is actually a colleagues analysis of it and I recommend reading it! Since this hasn’t been touched in a while I looked at the makefile and noticed it was being compiled using O2. Of course my first step is going to be to turn that up to O3 and see if there’s any section where vectorization could be useful and play around with that.  Other then that I’m going to explain why this function is as efficient as it is.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s