Haskell 中的调试内存问题

Question

我正在尝试解决 Haskell 中的整个代码降临系列。

我在解决 2015/06 exercise 时遇到内存问题，其中有一堆指令可以打开、关闭和切换网格上的灯。目标是统计最后点亮的灯的数量。

给定的指令被解析并存储在 Instruction 类型中，这是类型定义：

data Instruction = Instruction Op Range deriving Show
data Op = Off | On | Toggle | Nop deriving Show
data Range = Range Start End deriving Show
type Start = Point
type End = Start
data Point = Point Int Int deriving Show

这是计算结果的代码。我试图通过使用 typeclass

抽象出灯是布尔值这一事实

gridWidth, gridHeight :: Int
gridWidth = 1000
gridHeight = 1000

initialGrid :: Togglable a => Matrix a
initialGrid = matrix gridWidth gridHeight (const initialState)

instance Monoid Op where
  mempty = Nop

instance Semigroup Op where
  _ <> On = On
  _ <> Off = Off
  x <> Nop = x
  Off <> Toggle = On
  On <> Toggle = Off
  Toggle <> Toggle = Nop
  Nop <> Toggle = Toggle

class Togglable a where
  initialState :: a
  apply :: Op -> a -> a

instance Togglable Bool where
  initialState = False
  apply On = const True
  apply Off = const False
  apply Toggle = not
  apply Nop = id

-- Does the Range of the instruction apply to this matrix coordinate?
(<?) :: Range -> (Int, Int) -> Bool
(<?) (Range start end) (x, y) = let
  (Point x1 y1) = start
  (Point x2 y2) = end
  (mx, my) = (x-1, y-1) -- translate from matrix coords (they start from 1!)
  in and [
    mx >= min x1 x2, mx <= max x1 x2,
    my >= min y1 y2, my <= max y1 y2
  ]

stepGenerator :: Instruction -> Matrix Op
stepGenerator (Instruction op r) = let
  g coord = if r <? coord then op else Nop
  in matrix gridWidth gridHeight g

allStepsMatrix :: [Instruction] -> Matrix Op
allStepsMatrix = mconcat.map stepGenerator

finalGrid :: Togglable a => Matrix a -> Matrix Op -> Matrix a
finalGrid z op = fmap apply op <*> z

countOn :: Matrix Bool -> Integer
countOn = toInteger.foldr (\x -> if x then (+1) else id) 0

partA :: Challenge (String -> Integer)
partA = Challenge $ countOn.finalGrid initialGrid.allStepsMatrix.parse

解决方案将是 partA 中的内容返回的整数。 parse 有效并且类型为 parse :: String -> [Instruction]

代码编译并使用小矩阵（例如 10x10）运行，一旦我将 gridWidth 和 gridHeight 变为 1000，我显然会遇到 out of memory 错误从 allStepsMatrix 函数生成。

这里有什么问题的提示吗？完整代码是 on GitHub

Answer 1

我强烈建议不要使用类型类。类型类应该有规律，并且它们应该是 "rare"，从某种意义上说，每个类型只有几个有效的实现。我会建议将 initialState 和 toggle 作为参数，但即使这样也太过分了，因为给定的指令对于任何类型都没有意义Bool。直接对 Matrix Bool 进行操作，就可以截取一大块你写的代码。但是，我不会改变我的答案。

无论如何，我认为问题可能是懒惰。 1000 * 1000 = 1000000，所以每个 Matrix 的大小将是几兆字节。在 64 位机器上，一个指针是 8 个字节，所以每个 Matrix 至少有 8 MB，加上后面的数据还要多一些。您正在 mconcat 将其中的 300 个（这是我从网站上得到的）放在一起，但是，因为您懒惰地这样做，所有 300 个 矩阵同时驻留，所以它是至少 2.4 GB，仅用于结构本身。用 thunk 填充这 3 亿个指针中的每一个的成本也众所周知——一个 thunk 至少是一个指针（8 个字节，指向静态内存中的代码，另外 2.4 GB）加上它的有效负载，在这里，这意味着更多的指针，每一个都会给您的计算机带来另外 2.4 GB 的内存压力。我建议 deepseq:

instance NFData Op where
  rnf Off = ()
  rnf On = ()
  rnf Toggle = ()
  rnf Nop = ()
  -- rnf x = x `seq` () but I like to be explicit
allStepsMatrix :: [Instruction] -> Matrix Op
allStepsMatrix = foldl' (\x y -> force (x <> y)) mempty . map stepGenerator

Usnig foldl' 允许它在常量堆栈中运行 space，但是 foldl 或 foldr 也可以工作，因为 300 数量级的堆栈深度没什么. force 表示每个 Matrix 的所有元素都被评估。以前，每个矩阵通过持有对它的引用来保持前一个矩阵的存活，但现在在评估元素时引用被删除，因此 GC 可以及时将它们扔掉。我已经对此进行了测试，它会在合理的时间内以更好的space用法终止。

Haskell 中的调试内存问题

Debug memory issue in Haskell

haskell

space-leak