mapM seems to be a memory hog (and thus also concatMapM). In the following eg:
main = mapM print ([1..102400] :: [Integer])
memory usage climbs to 1.6M with ghc and needs -K20M, whereas with
main = print ([1..102400] :: [Integer])
memory usage is only 1300 bytes. I instrumented mapM:
main = mapM2 (_scc_ "p" (\x -> print x)) ([1..102400] :: [Integer])
mapM2 :: Monad m => (a -> m b) -> [a] -> m [b] mapM2 f [] = return [] mapM2 f (c:cs) = _scc_ "a" (>>=) (_scc_ "d" f c) (\x -> _scc_ "b" (>>=) (_scc_ "e" mapM2 f cs) (\xs -> _scc_ "f" return (x:xs)))
and found that a and b were the worst heap users (according to hp2ps), ie the two >>='s Why is this so? What can I do about it? My code uses mapM pretty extensively, and I think its suffering from this problem. I notice that ghc does not seem to use mapM except in 2 modules. Another odd thing is that hp2ps says that a & b are the culprits, but the -p and -px options say p is. Why? Sengan
senganb@ia.nsc.com (Sengan Baring-Gould) wrote:
mapM seems to be a memory hog (and thus also concatMapM). In the following eg:
main = mapM print ([1..102400] :: [Integer])
memory usage climbs to 1.6M with ghc and needs -K20M
As a guess: since 'mapM print ([1..102400] :: [Integer])' has type 'IO [()]', perhaps the result of the IO operation -- a list of 100K empty tuples -- is the culprit, even though the result is never used. Does 'mapM_ print ... ' (:: IO ()) perform any better? --Joe English jenglish@flightlab.com
senganb@ia.nsc.com (Sengan Baring-Gould) wrote:
mapM seems to be a memory hog (and thus also concatMapM). In the following eg:
main = mapM print ([1..102400] :: [Integer])
memory usage climbs to 1.6M with ghc and needs -K20M
As a guess: since 'mapM print ([1..102400] :: [Integer])' has type 'IO [()]', perhaps the result of the IO operation -- a list of 100K empty tuples -- is the culprit, even though the result is never used.
Does 'mapM_ print ... ' (:: IO ()) perform any better?
Yes, but in the following eg
main = print $ sum x x = _scc_ "x" [1..102400] :: [Integer]
x takes 1M allocations, and I would think that () would be smaller than an Integer. Therefore I'm not sure that is the reason. The sum is there to force the evaluation. Sengan
senganb@ia.nsc.com (Sengan Baring-Gould) wrote:
mapM seems to be a memory hog (and thus also concatMapM). In the following eg:
main = mapM print ([1..102400] :: [Integer])
memory usage climbs to 1.6M with ghc and needs -K20M
As a guess: since 'mapM print ([1..102400] :: [Integer])' has type 'IO [()]', perhaps the result of the IO operation -- a list of 100K empty tuples -- is the culprit, even though the result is never used.
Does 'mapM_ print ... ' (:: IO ()) perform any better?
Yes, but in the following eg
main = print $ sum x x = _scc_ "x" [1..102400] :: [Integer]
x takes 1M allocations, and I would think that () would be smaller than an Integer. Therefore I'm not sure that is the reason. The sum is there to force the evaluation.
Assuming you are right, why do I see the same 1.6M profile with:
main = mapM2 (_scc_ "p" (\x -> print x)) ([1..102400] :: [Integer]) >> return ()
mapM2 :: Monad m => (a -> m b) -> [a] -> m [b] mapM2 f [] = return [] mapM2 f (c:cs) = _scc_ "a" (>>=) (_scc_ "d" f c) (\x -> _scc_ "b" (>>=) (_scc_ "e" mapM2 f cs) (\xs -> _scc_ "f" return (x:xs)))
Is >>= not lazy? Sengan
Actually I think I figured it out: (>>=) (f c) (\x -> (>>=) (mapM f cs) (\xs -> return (x:xs))) -> (>>=) _(f c)_ (\x -> (>>=) (mapM f cs) (\xs -> return (x:xs))) -> (>>=) (MN c1) (\x -> (>>=) (mapM f cs) (\xs -> return (x:xs))) -> (\(MN c1) \fc2 -> MN $ \s0 -> let (r1,io1,s1) = c1 s0 ( MN c2 ) = fc2 r1 (r2,io2,s2) = c2 s1 in (r2,io1 >> io2,s2)) (MN c1) (\x -> (>>=) (mapM f cs) (\xs -> return (x:xs))) -> (MN $ \s0 -> let (r1,io1,s1) = c1 s0 ( MN c2 ) = (\x -> (>>=) (mapM f cs) (\xs -> return (x:xs))) r1 (r2,io2,s2) = c2 s1 in (r2,io1 >> io2,s2)) -> (MN $ \s0 -> let (r1,io1,s1) = c1 s0 ( MN c2 ) = (>>=) (mapM f cs) (\xs -> return (r1:xs)) (r2,io2,s2) = c2 s1 in (r2,io1 >> io2,s2)) -> (MN $ \s0 -> let (r1,io1,s1) = c1 s0 ( MN c2 ) = (>>=) (mapM f cs) (\xs -> return (r1:xs)) (r2,io2,s2) = c2 s1 in (r2,io1 >> io2,s2)) -> (MN $ \s0 -> let (r1,io1,s1) = c1 s0 ( MN c2 ) = (>>=) (mapM f cs) (\xs -> return (r1:xs)) (r2,io2,s2) = c2 s1 in (r2,io1 >> io2,s2)) So the "return (r1:xs)" will only happen once the whole mapM has completed, leaving, if I only use r1 at first, a whole load of partially evaluated iterations of mapM in the heap. This also means that sequences such as "mapM x >>= mapM y >>= mapM z" are very inefficient and should be replaced by mapM (z.y.x) whereever possible. Agreed? Sengan
Sengan Baring-Gould writes:
Is >>= not lazy?
since no experts have answered yet, this newbie will answer. I think it's strict. somewhere in the compiler doco, IIRC, it says (>>=) was lazy at first, but experience showed it was more confusing for users (Haskell programmers). moreover, from the hslibs documentation, LazyST chapter: "The lazy ST monad tends to be more prone to space leaks than the strict version, so most programmers will use the former unless laziness is explicitly required." http://haskell.org/ghc/docs/latest/set/sec-lazyst.html
participants (3)
-
Joe English -
Richard -
senganb＠ia.nsc.com