Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

GHC evaluation strategy

I'm a little confused with how the following code executes when compiled with GHC 7.6.3

import qualified Data.Map as M

main = do let m1 = M.fromList $ zip [1..10000000] [1..]
          putStrLn $ "Value = " ++ (show $ M.map (+2) m1 M.! 555)

Compiled with ghc --make -O3, it gets me the following result:

$ /usr/bin/time ./MapLazy
Value = 557
29.88user 2.16system 0:32.12elapsed 99%CPU (0avgtext+0avgdata 2140348maxresident)k
0inputs+0outputs (0major+535227minor)pagefaults 0swaps

Yet, if I change it to just show $ m1 M.! 555, I get much lower memory usage, yet takes almost the same time:

$ /usr/bin/time ./MapLazy
555
23.82user 1.17system 0:25.06elapsed 99%CPU (0avgtext+0avgdata 1192100maxresident)k
0inputs+0outputs (0major+298165minor)pagefaults 0swaps

What's actually happening here? Does the entire Map get instantiated just because I read out a single value? Could I have prevented that somehow? I mean, it's a binary search tree, so I was expecting just the one path I looked up on the new map to be actually evaluated.

like image 483
Samee Avatar asked Mar 07 '14 04:03

Samee


1 Answers

I think I got it. Let's look at the source for Data.Map.map.

map :: (a -> b) -> Map k a -> Map k b
map f m
  = mapWithKey (\_ x -> f x) m

mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
mapWithKey _ Tip = Tip
mapWithKey f (Bin sx kx x l r) 
  = Bin sx kx (f kx x) (mapWithKey f l) (mapWithKey f r)

Now, mapWithKey seems to build just the top constructor of the tree and lazily recursing for the two branches... but:

data Map k a  = Tip 
              | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) 

Above we see that the subtrees are strict fields! So the recursive calls to mapWithKey will be forced, causing the full tree to be updated strictly instead of lazily.

like image 79
chi Avatar answered Nov 09 '22 13:11

chi