haskell - 调试 Haskell 中的内存问题

Question

我正在尝试用 Haskell 解决整个 Advent of Code 系列问题。

我在解决 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

这是计算结果的代码。我试图通过使用类型类来抽象出光是 bool 值的事实

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内存错误，显然是由allStepsMatrix函数生成的。

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

Answer 1

我强烈建议不要使用类型类。类型类应该有规律，并且它们应该是“稀有的”，因为每种类型只有几个有效的实现。我建议将 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' 允许在恒定的堆栈空间中操作，但 foldl 或 foldr 也可以工作，因为堆栈深度的顺序300 不算什么。 force 意味着每个Matrix 的所有元素都被评估。以前，每个矩阵通过保存对前一个矩阵的引用来保持前一个矩阵的事件状态，但现在，在计算元素时会删除引用，因此 GC 可以及时将它们扔掉。我已经对此进行了测试，它会在合理的时间内终止，并且空间利用率更高。