performance - Haskell: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.4 秒，仅使用 1MB。有什么技巧可以防止这种增长，尤其是在太空中？我经常需要 IORef s 用于非原始类型，不像 Int ，并假设 IORef会像普通的thunk一样使用一个额外的指针，但我的直觉似乎是错误的。

我已经尝试了一种特殊的列表类型，它带有一个未打包的 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 秒的时间在恒定空间中运行。