[Shootout-list] ghc && strictness && hashes

Greg Buchholz sleepingsquirrel@member.fsf.org
Wed, 6 Oct 2004 16:21:32 -0700 (PDT)


--0-1612193893-1097104892=:17148
Content-Type: text/plain; charset=us-ascii
Content-Id: 
Content-Disposition: inline

  There seems to be a little bit of a bug in the ghc version of
"Hashes, part II".  Because Haskell is lazy by default, the
FiniteMaps (hashes) don't actually get fully populated (because
they're never used).  Instead of measuring how long it takes to do
a number of hash insertions, what we're measuring is how fast we
can throw a bunch of unevaluated thunks onto the heap.  That's
also why the current program consumes a whopping 109MB.  I've
attached a program to cure this problem, unfortunately it runs
slower than the original.  The key to getting the FiniteMaps
populated is the strictness provided by the 'seq' operator (thanks
to Ketil Malde).  If anyone has any further ideas I'd be
interested in hearing them.

Thanks,

Greg Buchholz


		
_______________________________
Do you Yahoo!?
Declare Yourself - Register online to vote today!
http://vote.yahoo.com
--0-1612193893-1097104892=:17148
Content-Type: text/x-haskell; name="hash2.hs"
Content-Description: hash2.hs
Content-Disposition: inline; filename="hash2.hs"

-- By Bryn Keller
--
import System (getArgs)
import Data.FiniteMap

get fm k = lookupWithDefaultFM fm 0 k
keys = map (\x -> "foo_" ++ show x) [0..9999]
hash1 = listToFM $ zip keys [0..9999]
hash2 = listToFM $ zip keys (repeat 0)
update k fm = let x = (get hash1 k + get fm k) in x `seq` addToFM fm k x
--update k fm = addToFM_C (+) fm k (get hash1 k)

main = do
  [n] <- getArgs
  let res = foldr update hash2 (concat $ replicate (read n) keys)
  putStrLn $ unwords $ map show [get hash1 "foo_1",
                                 get hash1 "foo_9999",
                                 get res "foo_1",
                                 get res "foo_9999"]


--0-1612193893-1097104892=:17148--