Haskell: performance of IORefs

Question

我一直在尝试在Haskell中编码一个算法，该算法需要使用大量可变引用，但与纯粹的惰性代码相比，它(也许并不奇怪)非常慢。考虑一个非常简单的例子:

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

在我的机器上运行GHC 7.8.2, main1需要1.2s，使用290MB内存，而main2只需要0.4s，只使用1MB内存。有没有什么诀窍可以防止这种生长，尤其是在太空中?我经常需要IORef s的非基本类型，不像Int，并假设IORef将使用一个额外的指针，就像一个常规的想法，但我的直觉似乎是错误的。

我已经尝试了一个特殊的列表类型与未打包的IORef，但没有显著的差异。

Answer 1

问题在于您使用的mapM，它在时间和空间上总是表现不佳。正确的解决方案是通过使用mapM_和(>=>)来融合中间列表:

import Data.IORef
import Control.Monad
list :: [Int]
list = [1..10^6]
main = mapM_ (newIORef >=> readIORef >=> print) list

它在固定的空间中运行，并提供了出色的性能，在我的机器上运行了0.4秒。

编辑:在回答您的问题时，您也可以使用pipes这样做，以避免必须手动融合循环:

import Data.IORef
import Pipes
import qualified Pipes.Prelude as Pipes
list :: [Int]
list = [1..10^6]
main = runEffect $
    each list >-> Pipes.mapM newIORef >-> Pipes.mapM readIORef >-> Pipes.print

在我的机器上，在固定空间中运行大约0.7秒。

Answer 2

这很可能不是关于IORef，而是关于严格性。IO单子中的操作是串行的——所有之前的操作必须完成才能启动下一个操作。所以

mapM newIORef list

在读取任何内容之前生成一百万个IORef s。

然而,

map runIdentity . map Identity
= map (runIdentity . Identity)
= map id

流非常好，所以我们print列表中的一个元素，然后生成下一个，等等。

如果你想要一个更公平的比较，使用严格的map:

map' :: (a -> b) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = (f x:) $! map' f xs

Answer 3

我发现，解决方案的hack是使用一个懒惰的mapM代替，定义为

lazyMapM :: (a -> IO b) -> [a] -> IO [b]
lazyMapM f [] = return []
lazyMapM f (x:xs) = do
  y <-  f x
  ys <- unsafeInterleaveIO $ lazyMapM f xs
  return (y:ys)

这允许一元版本在相同的1MB和相似的时间内运行。我希望一个懒惰的ST单子可以更优雅地解决这个问题，而不使用unsafeInterleaveIO，作为一个函数:

main = print $ runST (mapM (newSTRef) list >>= mapM (readSTRef))

，但这不起作用(你还需要使用unsafeInterleaveST)，这让我想到Control.Monad.ST.Lazy是多么的懒惰。有人知道吗?:)