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,2 с и использует 290 МБ памяти, в то время как main2 занимает всего 0,4 с и использует всего 1 МБ. Есть ли хитрость, чтобы предотвратить этот рост, особенно в космосе? Мне часто нужно IORefs для непримитивных типов в отличие 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 секунд на моей машине.

Answer 2

Это очень вероятно, не о IORef, но о строгости. Действия в IO Монада является последовательной - все предыдущие действия должны быть завершены, прежде чем можно будет запустить следующее. Так

mapM newIORef list

генерирует миллион IORefс, прежде чем что-то читать.

Тем не мение,

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

Я обнаружил, что взлом к ​​решению проблемы заключается в использовании ленивых 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)

Это позволяет монадической версии работать в течение того же 1 МБ и аналогичного времени. Я бы ожидал, что ленивый ST Монада могла бы решить эту проблему более элегантно, не используя unsafeInterleaveIO, как функция:

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

но это не работает (вам также нужно использовать unsafeInterleaveST) что заставляет меня задуматься о том, как ленив Control.Monad.ST.Lazy на самом деле. Кто-нибудь знает?:)