[Haskell-cafe] Optimizing a hash function

Ivan Tomac tomac at pacific.net.au
Sat Nov 25 23:12:31 EST 2006


Hi,

Yesterday evening I had a go at porting Bob Jenkins' hash function  
(http://www.burtleburtle.net/bob/c/lookup3.c) to Haskell.

The first version I came up with ran 20 times slower than C.
Thanks to Don Stewart's suggestions on IRC, I managed to improve the  
performance by replacing tuples with a strict type so the current  
version is about 10 times slower than C code.
Is there any way this can be further optimized?

To keep things fair I've simplified the C function so it works on one  
byte at a time as opposed to an int at a time.
The code was compiled with GHC-6.6 on a G5 iMac running OS X 10.4.

Options used to compile the version using the hash function written  
in Haskell:
ghc -O -funbox-strict-fields -fglasgow-exts -fbang-patterns -cpp -o  
test hashByteString.hs test.hs

Options used to compile the version using the hash function in C:
ghc -O -fglasgow-exts -ffi -fbang-patterns -cpp -DCHASH -o ctest  
ctest.c test.hs


Ivan Tomac

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ctest.c
Type: application/octet-stream
Size: 2085 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061126/cb6b900b/ctest.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ctest.h
Type: application/octet-stream
Size: 101 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061126/cb6b900b/ctest-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashByteString.hs
Type: application/octet-stream
Size: 2561 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061126/cb6b900b/hashByteString.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.hs
Type: application/octet-stream
Size: 650 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061126/cb6b900b/test.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.prof
Type: application/octet-stream
Size: 3134 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061126/cb6b900b/test-0001.obj


More information about the Haskell-Cafe mailing list