I have been trying to encode an algorithm in Haskell that requires using lots of mutable references, but it is (perhaps not surprisingly) very slow in comparison to purely lazy code. Consider a very simple example:
module Main where
import Data.IORef
import Control.Monad
import Control.Monad.Identity
list :: [Int]
list = [1..10^6]
main1 = mapM newIORef list >>= mapM readIORef >>= print
main2 = print $ map runIdentity $ map Identity list
Running GHC 7.8.2 on my machine, main1
takes 1.2s and uses 290MB of memory, while main2
takes only 0.4s and uses a mere 1MB. Is there any trick to prevent this growth, especially in space? I often need IORef
s for non-primitive types unlike Int
, and assumed that an IORef
would use an additional pointer much like a regular thunk, but my intuition seems to be wrong.
I have already tried a specialized list type with an unpacked IORef
, but with no significant difference.
This is very likely not about
IORef
, but about strictness. Actions in theIO
monad are serial -- all previous actions must complete before the next one can be started. Sogenerates a million
IORef
s before anything is read.However,
which streams very nicely, so we
print
one element of the list, then generate the next one, etc.If you want a fairer comparison, use a strict
map
:The problem is your use of
mapM
, which always performs poorly on large lists both in time and space. The correct solution is to fuse away the intermediate lists by usingmapM_
and(>=>)
:This runs in constant space and gives excellent performance, running in 0.4 seconds on my machine.
Edit: In answer to your question, you can also do this with
pipes
to avoid having to manually fuse the loop:This runs in constant space in about 0.7 seconds on my machine.
I have found that the hack towards a solution is to use a lazy
mapM
instead, defined asThis allows the monadic version to run within the same 1MB and similar time. I would expect that a lazy
ST
monad could solve this problem more elegantly without usingunsafeInterleaveIO
, as a function:but that does not work (you also need to use
unsafeInterleaveST
), what leaves me thinking about how lazy theControl.Monad.ST.Lazy
really is. Does someone know? :)