Haskell中的调试内存问题

Question

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

我在解决2015/06练习时遇到内存问题，该练习中有一堆说明来打开，关闭和切换网格上的灯光。目的是计算最后点亮的灯的数量。

给定的指令被解析并存储在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

这是计算结果的代码。我试图通过使用类型类来抽象一个灯光是布尔值的事实

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

解决方案将是内部所返回的Integer partA。parse工作并具有类型parse :: String -> [Instruction]

代码编译和运行与小矩阵（10×10例如），只要我转gridWidth和gridHeight1000我面对一个out of memory错误，从显然生成allStepsMatrix功能。

有什么暗示这里可能有问题吗？完整代码在GitHub上

Answer 1

我强烈建议不要使用类型类。类型类应该有规律，而且它们应该是“罕见的”，因为每种类型只有几个有效的实现。我会建议你服用initialState和toggle作为参数，但即使是矫枉过正，因为作出批示，根本就没有与任何类型，它是没有意义的Bool。Matrix Bool直接对 a 进行操作，你就可以剪掉一大块你写的代码。但是，我不会为我的答案更改任何内容。

无论如何，我认为问题可能是懒惰。1000 * 1000 = 1000000，所以每个都有Matrix几兆字节的大小。在 64 位机器上，一个指针是 8 个字节，所以每个 Matrix 至少有 8 MB，再加上一些用于它后面的数据。您将其中的mconcat300 个（这是我从网站上得到的）放在一起，但是，因为您懒惰地这样做，所以所有 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'在恒定的堆栈空间中运行，但foldlorfoldr也可以工作，因为 300 级的堆栈深度算不了什么。这force意味着Matrix评估每个元素的所有元素。以前，每个矩阵通过保存对它的引用来保持前一个矩阵的活动，但现在在评估元素时删除引用，因此 GC 可以及时将它们扔掉。我已经对此进行了测试，它会在合理的时间内以更好的空间使用率终止。