Haskell：IORefs的表现 [英] Haskell: performance of IORefs

问题描述

我一直试图在Haskell中编码一个算法，它需要使用大量的可变引用，但与纯粹的惰性代码相比，它可能（并不令人惊讶）很慢。
考虑一个非常简单的例子：

  module Main其中
 
 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标识列表
  

在我的机器上运行GHC 7.8.2， main1 需要1.2s，使用290MB内存，而 main2 只需要0.4s，只用1MB。防止这种增长有什么窍门，特别是在太空中？与 Int 不同，我经常需要 IORef s，并假定 IORef 会使用额外的指针，就像常规的thunk，但我的直觉似乎是错误的。

我已经尝试过一种特殊的列表类型，一个解压缩的 IORef ，但没有显着差异。 解决方案

是你使用 mapM ，它在时间和空间上的大型列表上总是表现不佳。正确的解决方案是使用 mapM _ 和（> =>）来融合中间列表： p>



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

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

编辑：回答你的问题，你也可以用 pipes 来做到这一点，以避免手动融合循环：

 导入Data.IORef 
导入管道
导入限定Pipes.Prelude作为管道
 
 list :: [Int] 
 list = [1..10 ^ 6] 
 
 main = runEffect $ 
 each list>  - > Pipes.mapM newIORef>  - > Pipes.mapM readIORef>  - > Pipes.print 
  

这个运行在我机器上约0.7秒的恒定空间内。

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 IORefs 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.

解决方案

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 using mapM_ and (>=>):

import Data.IORef
import Control.Monad

list :: [Int]
list = [1..10^6]

main = mapM_ (newIORef >=> readIORef >=> print) list

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:

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

This runs in constant space in about 0.7 seconds on my machine.

这篇关于Haskell：IORefs的表现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！