RE: [Haskell-cafe] Re: Haskell Speed

From: Isaac Gouy To: haskell-cafe@haskell.org Subject: [Haskell-cafe] Re: Haskell Speed Date: Thu, 29 Dec 2005 13:00:15 -0800 (PST)

--- Isaac Gouy wrote:

...

We'll be happy to also show a Haskell program that uses Data.HashTable - first, someone needs to contribute that program.

Someone did: k-nucleotide Haskell GHC #2 http://shootout.alioth.debian.org/gp4/benchmark.php?test=knucleotide&lang=all

To comment some observation on this program. Most of the pressure now is on Data.HashTable. I've susspected such large memory usage on substring from array conversions, so mad version with data MyString = MakeMyStrinf { buf :: Ptr Char, size :: Int } and there was no substrings in map or anywhere else, but memory consumption remains. So after eliminating inserts and updates into HashTable memory was ok. Finally I've realized that updates into hash table actually increase memory usage to large extent instead to keep memory same on average. So I guess this is bug in HashTable? Second in this test, hash function needs to be very strong, as even with following I got longest chain of 16 elements. myHashString = fromIntegral . ff''' . ff'' . ff' . foldr f 0 where f c m = f'' $ f' (ord c + m) f' m = m + (m `shiftL` 10) f'' m = m `xor` (m `shiftR` 6) ff' m = m + (m `shiftL` 3) ff'' m = m `xor` (m `shiftR` 11) ff''' m = m + (m `shiftL` 15) Default hashString has longestChain of 18 elements. Perhaps someone can explain if such a memory leaks from HashTable updates are normal or are bugs? All in all functional version consumes less memory and is twice as fast. Greetings, Bane. _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/