为什么我的可变链表慢于不可变变量？

Question

我有一个用例,我需要一个具有恒定时间插入的结构,然后可以从最旧到最新迭代.基本上是一个队列.区别在于插入和迭代在单独的步骤中发生到一个简单的列表ALMOST足够好.我只需要在最后做一个反向.这反过来是我想要摆脱的.

我打算在STmonad中自己实现这个.由此产生的性能慢4倍.我将包含所有相关代码(它是自包含的)以及我用来对其进行基准测试的函数.您可以在安装timeit软件包的情况下自行编译.

{-# LANGUAGE ViewPatterns #-}
module LinkedListSpecial where

import Prelude hiding (mapM_)
import Control.Monad.ST
import Data.STRef
import Data.Foldable (mapM_, foldlM, forM_)
import System.TimeIt

data LLN s a = Stub (STRef s (Maybe (LLN s a)))
             | LLN a (STRef s (Maybe (LLN s a)))

getRef :: LLN s a -> STRef s (Maybe (LLN s a))
getRef (Stub ref)  = ref
getRef (LLN _ ref) = ref

emptyNode :: ST s (LLN s a)
emptyNode = fmap Stub (newSTRef Nothing)

makeNode :: a -> ST s (LLN s a)
makeNode x = fmap (LLN x) $! newSTRef Nothing

append :: LLN s a -> a -> ST s (LLN s a)
append (getRef -> ref) x = do
    new <- makeNode x
    writeSTRef ref (Just new)
    return new

iter :: (a -> ST s ()) -> LLN s a -> ST s ()
iter f (Stub ref) = do
    next <- readSTRef ref
    mapM_ (iter f) next
iter f (LLN x ref) = do
    f x
    next <- readSTRef ref
    mapM_ (iter f) next

fromList :: [a] -> ST s (LLN s a, LLN s a)
fromList xs = do
    f <- emptyNode
    l <- foldlM append f xs
    return (f, l)

test :: IO ()
test = do
    let seedList = [1..1000000]
    print "Normal list"
    timeIt $ print $ runST $ do
        ref <- newSTRef []
        forM_ seedList (\i -> modifySTRef' ref (i :))
        list <- readSTRef ref
        return (sum list :: Integer)
    print "Linked list"
    timeIt $ print $ runST $ do
        (listBegin, _) <- fromList seedList
        s <- newSTRef (0 :: Integer)
        iter (\i -> modifySTRef' s (+ i)) listBegin
        readSTRef s

如果有更优秀的优化人员告诉我可以改进的地方,我将不胜感激.

编辑:运行编译代码时性能下降不那么激烈,但我的列表仍然是慢两倍.

Answer 1

简单的原因是GHC的运行时系统(特别是垃圾收集器)的权衡旨在尽可能快地生成不可变数据,代价是代码中的单词速度突变指向盒装值.特别是,GC系统进行了大量优化,假设值最多变异一次(延迟评估).当这些条件不成立时,它会增加一大堆开销,因为它必须解决这些优化问题.

至于解决它,似乎有人提到差异列表,他们确实工作.但是,不需要使用包.它是一种足够简单的数据类型,您可以将其用于内联,除非您需要包提供的实例.

基本思想是你不使用列表,而是使用函数.

nil :: [a] -> [a]
nil = id

snoc :: a -> ([a] -> [a]) -> [a] -> [a]
snoc x f = f . (x :)

toList :: ([a] -> [a]) -> [a]
toList f = f []

这使您在执行大量snoc操作的用例中获得了非常好的性能,然后将其一次性转换为列表.当你的模式是单个元素,遍历,重复时,这真的很糟糕snoc.