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
su, 2006-11-26 kello 15:12 +1100, Ivan Tomac kirjoitti:
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 ...
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
Hi Ivan Tomac, Have you tried -O3 -optc-O3 -funfolding-use-threshold=16 compile flags? Don, Lemmih, Lennart and Bulat helped me to sort out a similar problem a couple of weeks ago. More hints can be found at http://haskell.org/haskellwiki/Performance/GHC Especially, to check generated code by taking a look of core -ddump-simpl > core.txt and to check memory leaks, you could run with +RTS -sstderr br, Isto
Hi, I've seen that guide before and followed the suggestions in there but somehow I missed the -funfolding-use-threshhold option. After setting it to 24 the code now runs about 2-3 times slower than C which is a significant improvement from a factor of 10. Thanks :) Ivan On 27/11/2006, at 12:04 AM, isto wrote:
Have you tried -O3 -optc-O3 -funfolding-use-threshold=16 compile flags? Don, Lemmih, Lennart and Bulat helped me to sort out a similar problem a couple of weeks ago. More hints can be found at http://haskell.org/haskellwiki/Performance/GHC Especially, to check generated code by taking a look of core -ddump-simpl > core.txt and to check memory leaks, you could run with +RTS -sstderr
br, Isto
Yesterday evening I had a go at porting Bob Jenkins' hash function (http://www.burtleburtle.net/bob/c/lookup3.c) to Haskell.
If you need hash functions, I hope that you don't need them to become a hash table necromancer: this dark data structure simply does not fit well into Haskell. Tries are a better alternative: Ralf Hinze. Generalizing generalized tries. Journal of Functional Programming, 10(4):327-351, July 2000 http://www.informatik.uni-bonn.de/~ralf/publications/GGTries.ps.gz Otherwise, take care to conduct hash experiments inside Otiluke's Resilient Sphere only. Regards, apfelmus
participants (3)
-
apfelmus＠quantentunnel.de -
isto -
Ivan Tomac