为什么我的可变链表比不可变变体慢？

Question

我有一个用例，我需要一个具有恒定时间插入的结构，然后可以从最旧迭代到最新。基本上是一个队列。不同之处在于插入和迭代发生在单独的步骤中，一个简单的列表几乎就足够了。我只需要在最后做一个反转。这种逆转是我想要摆脱的。

我已经着手在 ST monad 中自己实现它。由此产生的性能慢了 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 单个元素时，真的很糟糕，遍历，重复。

为什么我的可变链表比不可变变体慢？

Why is my mutable linked list slower than the immutable variant?

optimization

haskell

linked-list