The pony barn

XXHash for haskell

Posted on January 10, 2014

I recently implemented the xxHash algorithm in Haskell. You may find my implementation on github and a criterion benchmark here.

At first, my implementation’s performance was terrible.

However, with a little tinkering I was able to get the performance up on par with C, mostly due to inlinePerformIO which appears to have unboxed and inlined everything as best as could be expected.

GHC was even smart enough to turn a call to rotateL into what looks like the assembly output of hand written C.

To elaborate:

1. The little rotateL bit from this snippet:

prime1 = 2654435761
prime2 = 2246822519

vx v i = ((v + i * prime2) `rotateL` 13) * prime1

2. Became the core:

(narrow32Word#
   (timesWord#
      (narrow32Word#
	 (or#
	    (uncheckedShiftL# x#2_X1Bh 13)
	    (uncheckedShiftRL# x#2_X1Bh 19)))
      (__word 2654435761)))

3. Which begat:

_c31A:
...
	movl $2654435761,%esi
	movq %rcx,%rax
	shrq $19,%rax
	shlq $13,%rcx
	orq %rax,%rcx
	movl %ecx,%eax
	imulq %rsi,%rax
...

Which looks a lot like like:

#define rotl32(x,r) ((x << r) | (x >> (32 - r))

Neat! Well. I thought so.