GHC紧凑区域中的可变阵列

Question

我想弄清楚是否有可能MutableArray#在一个紧凑的区域.ghc开发人员 和文档明确表示不这样做, 因为它允许用户指向外部的东西Compact.除此之外,我仍然有兴趣尝试这样做,理解我将负责确保数组仅指向相同的内容Compact.

我的想法是添加Array#一个紧凑区域,然后尝试使用unsafeThawArray#以下方法解冻它:

unsafeThawArray# :: Array# a -> State# s -> (#State# s, MutableArray# s a#)

我应该能够使用writeArray#,前提是(a)我写入的所有内容都MutableArray#在同一个紧凑区域中,(b)seq在将其写入数组之前,我将所有内容评估为WHNF .我认为这是安全的.我确实有一个基于 stg_unsafeThawArrayzh评论的问题:

MUT_ARR_PTRS存在于可变列表中,但是MUT_ARR_PTRS_FROZEN通常不会...

我不太了解GHC的内部结构,但这里是我对评论的理解:有一种叫做可变列表的东西,它有一堆可变数组,偶尔由GC扫描.就我的目的而言,这是有问题的,因为这意味着unsafeThawArray#将导致GC开始在紧凑区域中扫描事物.这不好.但是,也许我的理解是错误的,这将是伟大的.

如果unsafeThawArray#不能做我需要的事情,那我就是想这样unsafeCoerce#做,但我想再次听取有关这个主题的知识渊博的人的意见.谢谢,让我知道我是否可以澄清任何事情.

编辑:只是对未来读者的评论.在考虑了这个之后,我意识到使用SmallArray#而不是Array#更好.它应该使写入更快.将写入MutableArray#的代码与写入SmallMutableArray#的代码进行比较.MutableArray#当一切都在紧凑的堆上时,保持更新的卡表是毫无价值的,因为它永远不会被扫描.

Answer 1

这是一个有趣的想法,虽然它是一个非常微妙的,我相信你可以逃脱它.

正如您所指出的,垃圾收集器需要跟踪哪些数组是可变的,因为它们可能包含对居住在年轻代中的对象的引用,而不是数组本身.此列表中的对象将在收集年轻一代时充当根源.

为了了解原因,假设你在一个可变数组(在托儿所,第0代)中分配了一些指向其他新分配的堆对象的指针.在垃圾收集中,数组及其内容都将移动到第1代,这意味着当我们清除第0代时不需要遍历它.

现在假设我们在第0代中分配一个新的堆对象,并改变一个数组元素来引用它.现在考虑当我们垃圾收集托儿所时会发生什么:如果我们只查看第0代中的引用,我们将错误地断定我们新分配的对象已经死亡.这显然是错误的:我们的新对象是通过第1代数组中的引用实现的.

出于这个原因,我们必须为每一代维护一个可变对象列表,当我们收集年轻一代时,我们将作为根源进行清理.

然而,正如你的直觉所暗示的那样,在紧凑的区域中这应该是不必要的,因为我们不应该正在清理区域的内容.而且,由于堆表示MutableArray#和Array#相同(除了信息表指针),你的使用unsafeCoerce#应该没问题.

所有这一切自然取决于仔细保留紧凑区域服从的闭合不变量.这要求所有计算最终都会减少到该区域中的某种查找.严格来说,即使这还不够,因为Haskell的语义不能保证不会产生副本,但在GHC Haskell的情况下,这应该不是问题.

一个例子

这是我用来测试这个的小游乐场.

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE BangPatterns #-}

import GHC.IO
import GHC.Compact
import GHC.Exts hiding (toList)

data Wombat = Wombat String deriving Show

n = 10000

wombats :: [Wombat]
wombats = take n $ cycle $ map Wombat [ "harry", "jerry", "carry", "larry", "fred" ]

main :: IO ()
main = do
    c <- fromListM (length wombats) wombats >>= compact
    let arr = getCompact c
    flip mapM_ [1..n-1] $ \i -> do
        swapMutArray i ((i+2) `mod` n) arr
    mapM_ print (toList arr)
    return ()

(!) :: MutArray a -> Int -> a
(!) (MutArray a) (I# n) =
    case indexArray# a n of
      (# x #) -> x

data MutArray a = MutArray (Array# a)

getMutArray :: MutArray a -> MutableArray# s a
getMutArray (MutArray arr) = unsafeCoerce# arr

fromListM :: Int -> [a] -> IO (MutArray a)
fromListM = \n@(I# n#) xs ->
    IO $ \s0 -> case newArray# n# x0 s0 of
                  (# s1, arr #) -> unIO (go arr (n-1) xs) s1
  where
    x0 = error "hi"
    go arr (-1) [] = IO $ \s0 -> case unsafeFreezeArray# arr s0 of
                                   (# s1, arr' #) -> (# s1, MutArray arr' #)
    go arr n@(I# n#) (x:xs) = do
        IO $ \s0 -> case writeArray# arr n# x s0 of s1 -> (# s1, () #)
        go arr (n-1) xs
    go _ _ _ = error "uh oh"

toList :: Show a => MutArray a -> [a]
toList arr@(MutArray arr#) = go 0
  where
    !len = I# (sizeofArray# arr#)
    go n
      | n == len = []
      | otherwise = (arr ! n) : go (n + 1)

writeMutArray :: Int -> a -> MutArray a -> IO ()
writeMutArray (I# i) x arr =
    IO $ \s0 -> case writeArray# (getMutArray arr) i x s0 of s1 -> (# s1, () #)

swapMutArray :: Int -> Int -> MutArray a -> IO ()
swapMutArray m@(I# m#) n@(I# n#) arr = do
    !x <- IO $ readArray# (getMutArray arr) m#
    !y <- IO $ readArray# (getMutArray arr) n#
    writeMutArray n x arr
    writeMutArray m y arr