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

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 单个元素、遍历、重复时，这真的很糟糕。