GHC 紧凑区域中的可变数组

Question

我想弄清楚是否可以将 MutableArray# 放入一个紧凑的区域。 ghc devs 明确不鼓励这样做 the documentation 因为它允许用户指向 Compact 之外的东西。除此之外，我仍然有兴趣尝试这样做，理解我将负责确保数组只指向事物在同一个 Compact.

我的想法是在紧凑区域添加一个 Array# 然后尝试使用 unsafeThawArray#:

解冻它

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

然后我应该能够使用 writeArray#，前提是 (a) 我的一切写入 MutableArray# 是在同一个紧凑区域和 (b) I 在将所有内容写入数组之前，使用 seq 将所有内容评估为 WHNF。我认为这会很安全。我确实有一个担忧基于 stg_unsafeThawArrayzh commentary:

A MUT_ARR_PTRS lives on the mutable list, but a MUT_ARR_PTRS_FROZEN normally doesn't...

我不太了解 GHC 的内部结构，但这是我对评论的理解：有一个叫做 mutable 列表的东西，它有一堆 mutable 数组和偶尔会被 GC 扫描。就我的目的而言，这是有问题的，因为这意味着 unsafeThawArray# 将导致 GC 开始扫描紧凑区域中的内容。这不好。但是，也许我的理解是错误的，那就太好了。

如果unsafeThawArray#不能做我需要的，我在想unsafeCoerce#会这样做，但我再次想听听对此主题有知识的人的意见。谢谢，如果我能澄清任何事情，请告诉我。

编辑：只是对未来读者的评论。仔细考虑之后，我意识到使用 SmallArray# 而不是 Array# 会更好。它应该使写入更快。比较 writing to MutableArray# with the code for writing to SmallMutableArray# 的代码。当所有内容都在紧凑堆上时，MutableArray# 保持更新的卡 table 毫无价值，因为它永远不会被扫描。

Answer 1

这是一个有趣的想法，虽然它非常微妙，但我相信你可以摆脱它。

正如您所指出的，垃圾收集器需要跟踪哪些数组是 mutable，因为它们可能包含对驻留在比数组本身更年轻的代中的对象的引用。此列表中的对象将在收集年轻代时作为根。

要了解原因，假设您分配了（在第 0 代的 nursery 中）一个 mutable 数组，其中包含一些指向其他新分配的堆对象的指针。在垃圾回收时，数组及其内容都将移至第 1 代，这意味着我们在第 0 代进行清理时不需要遍历它。

现在想象一下，我们在第 0 代中分配了一个新的堆对象，并改变了一个数组元素来引用它。现在考虑当我们对 nursery 进行垃圾回收时会发生什么：如果我们只查看第 0 代中的引用，我们会错误地得出结论，我们新分配的对象已经死了。这显然是错误的：我们的新对象是通过其对第 1 代数组的引用而存在的。

因此，我们必须为每一代维护一个 mutable 对象列表，我们将在收集年轻代时将其作为根进行清理。

但是，正如您的直觉所暗示的那样，这在紧凑区域中应该是不必要的，因为无论如何我们都不应该清除该区域的内容。此外，由于 MutableArray# 和 Array# 的堆表示相同（信息 table 指针除外），您使用 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

GHC 紧凑区域中的可变数组

Mutable Array in GHC Compact Region

haskell

ghc

一个例子