如何避免 Haskell 中惰性设置下的正确性空间泄漏 (2023)

# 如何在惰性求值设置下避免正确性空间泄漏 来源：https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html ## 目录 - 1. [空间泄漏的分类](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#orgbb37ed8) - 2. [避免严格性泄漏](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#org8b2df4b) - 2.1. [对相同表达式重复使用的函数](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#org57a37f7) - 2.2. [使用成本中心和*一个奇特技巧*在运行时捕获它们](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#org09618ff) - 3. [避免活跃性泄漏](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#orgf7b7d1a) - 4. [避免过度共享泄漏](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#orge5c24b9) - 4.1. [合并数据结构上的多次遍历为单次遍历](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#orgc771749) - 4.2. [将生成器的创建移入函数内部，并将其包装在一个简单的函数中](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#org5eb3246) - 4.3. [硬着头皮使用线性类型](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#orgbca2294) - 5. [结论](https://epicandmonicisnotiso.blogspot.com/2023/04/how-to-avoid-correctness-space-leaks-on.html#orgc607dec) 一些在HN（https://news.ycombinator.com/item?id=35305546）上的帖子注意到，在我之前的文章（https://epicandmonicisnotiso.blogspot.com/2023/03/an-apologia-of-lazy-evaluation.html）中，我没有给出关于如何避免空间泄漏的通用建议。考虑到我承认存在一类（b）对正确性有影响的空间泄漏，这一点尤为重要。我们可用的工具分为两类： - 防御性编码模式 - 运行程序性能分析 我认为前者更为重要，我们希望首先避免问题。为了证明和发现空间泄漏，我们将结合手动展开和/或分析一段代码的STG输出来使用。STG代码将被用作操作模型，尽管这只适用于GHC编译的Haskell代码。它一开始令人困惑，但并不难，学会阅读它有许多好处： - 所有分配都在`let`中显式进行，特别是惰性求值对象（thunk）。惰性是显式的。 - 所有求值都发生在`case`表达式中。 - 闭包的自由变量是显式提供的。 - 没有括号，所有对象都是显式构造的、命名的并通过其传递。 - 所有应用都是饱和的。变量名可能有些奇怪，但我们会习惯的:-) 。 ## 1. 空间泄漏的分类 存在其他的空间泄漏分类（http://blog.ezyang.com/2011/05/space-leak-zoo/）。我将使用另一种分类法，并且只限于那些通常引起正确性担忧的泄漏。我们最终得到三种不同的类型： 1. **严格性泄漏**：当一个递归*式*函数生成一系列相互依赖的惰性求值对象（thunk），这些对象仅在被求值后立即被归约为一个值。惰性求值对象的数量与递归数量正相关。 2. **活跃性泄漏**：当一个大值`r`的引用从GC的角度看是活跃的而非死亡的，因为它在流水线的惰性求值对象中被引用。一旦流水线的值被强制求值，该值就被标记为死亡并被回收。 3. **过度共享泄漏**：一个生成器被两个不同的流水线共享。生成器的实际尺寸很大。一旦第一个流水线求值了生成器，其实现的尺寸将保留在内存中，直到第二个流水线消费该值。 这种分类很有用，因为严格性泄漏是*局部程序*属性，它们存在于递归函数定义中，或者在eDSL中绑定表达式的函数（如`>>=`）中预期会出现。活跃性泄漏则是*全局程序*属性，需要预先规划来避免。过度共享泄漏在处理生成器（实现时是大数据结构）时需要小心。 ## 2. 避免严格性泄漏 这些泄漏发生在： - 显式递归函数中 - eDSL的绑定函数（如`>>=`）中 - 预期会被程序员重复调用的函数（如`++`）中。 在编写这类函数时，你应该对此类函数保持注意。最经典的例子是`foldl`函数（https://wiki.haskell.org/Foldr_Foldl_Foldl'）。泄漏完全包含在函数定义中，并且在函数展开时是清楚的。STG证实了我们手动操作能得到的结果。 ```haskell module Gato where myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f acc [] = acc myFoldl f acc (b : bs) = myFoldl f (f acc b) bs ``` 产生以下STG（使用`ghc -c -O1 -ddump-stg-final -ddump-to-file -fforce-recomp`编译）： ``` Rec { Gato.myFoldl [Occ=LoopBreaker] :: forall a b. (a -> b -> a) -> a -> [b] -> a [GblId, Arity=3, Str=<1L>, Unf=OtherCon []] = {} \r [f_s1fN acc_s1fO ds_s1fP] case ds_s1fP of { -- 只对列表进行模式匹配 [] -> acc_s1fO; : b1_s1fR [Occ=Once1] bs_s1fS [Occ=Once1] -> let { -- 惰性求值对象分配 sat_s1fT [Occ=Once1] :: a_aNS [LclId] = -- {acc_s1fO, b1_s1fR, f_s1fN} 是自由变量（也是引用） -- 一个 u-ptable 闭包。 {acc_s1fO, b1_s1fR, f_s1fN} \u [] f_s1fN acc_s1fO b1_s1fR; } in Gato.myFoldl f_s1fN sat_s1fT bs_s1fS; }; end Rec ``` 我们看到在这个函数的递归情况中，唯一的求值发生在列表的模式匹配上。没有进行其他归约。惰性求值对象在递归调用中被传递，所以在下一次迭代中`acc_s1fO`将是一个惰性求值对象，并且会被再次包装。 修复方法是众所周知的：在进行递归调用之前强制求值该惰性求值对象，释放自由变量`{acc_s1fO, b1_s1fR, f_s1fN}`，并将一个值传递给下一个递归调用。这是应成为尾递归函数的通用模式。我们可以用`seq`来实现。 ```haskell myFoldl2 :: (a -> b -> a) -> a -> [b] -> a myFoldl2 f acc [] = acc myFoldl2 f acc (b : bs) = let t = f acc b in t `seq` myFoldl f t bs ``` STG： ``` Gato.myFoldl2 :: forall a b. (a -> b -> a) -> a -> [b] -> a [GblId, Arity=3, Unf=OtherCon []] = {} \r [f_s15n acc_s15o ds_s15p] case ds_s15p of { [] -> acc_s15o; : b1_s15r [Occ=Once1] bs_s15s [Occ=Once1] -> case f_s15n acc_s15o b1_s15r of t_s15t [Occ=Once1] { __DEFAULT -> Gato.myFoldl f_s15n t_s15t bs_s15s; }; }; ``` 这里我们有两个`case`表达式，没有产生分配，很好。 ### 2.1. 对相同表达式重复使用的函数 这里我指的是像`>>=`或`mappend`这样的函数。它们绑定不同的表达式，所以我们可以看到在同一个流水线上有许多这样的应用。这里最有趣的例子是严格写法monad的绑定。 ```haskell instance (Monoid w, Monad m) => Monad (WriterT w m) where return a = writer (a, mempty) m >>= k = WriterT $ do (a, w) <- runWriterT m (b, w') <- runWriterT (k a) return (b, w `mappend` w') ``` 具有以下STG代码： ``` $c>>=_rKER :: forall w (m :: * -> *) a b. (GHC.Base.Monoid w, GHC.Base.Monad m) => Control.Monad.Trans.Writer.Strict.WriterT w m a -> (a -> Control.Monad.Trans.Writer.Strict.WriterT w m b) -> Control.Monad.Trans.Writer.Strict.WriterT w m b [GblId, Arity=4, Unf=OtherCon []] = {} \r [$dMonoid_sKLr $dMonad_sKLs eta_sKLt eta1_sKLu] let { sat_sKLK [Occ=Once1] :: m_aKdo (b_aKdA, w_aKdn) -- 对 f 或 eta1_sKLu 的包装 [LclId] = {$dMonoid_sKLr, $dMonad_sKLs, eta1_sKLu, eta_sKLt} \u [] let { sat_sKLJ [Occ=Once1] :: (a_aKdz, w_aKdn) -> m_aKdo (b_aKdA, w_aKdn) [LclId] = {$dMonoid_sKLr, $dMonad_sKLs, eta1_sKLu} \r [ds_sKLx] case ds_sKLx of { (,) a1_sKLz [Occ=Once1] w1_sKLA [Occ=OnceL1] -> let { sat_sKLI [Occ=Once1] :: (b_aKdA, w_aKdn) -> m_aKdo (b_aKdA, w_aKdn) [LclId] = {$dMonoid_sKLr, w1_sKLA, $dMonad_sKLs} \r [ds1_sKLC] -- 实际使用 mappend 的惰性求值对象 case ds1_sKLC of { -- 捕获 w1_sKLA (,) b1_sKLE [Occ=Once1] w'_sKLF [Occ=Once1] -> let { sat_sKLG [Occ=Once1] :: w_aKdn [LclId] = {$dMonoid_sKLr, w1_sKLA, w'_sKLF} \u [] GHC.Base.mappend $dMonoid_sKLr w1_sKLA w'_sKLF; } in let { sat_sKLH [Occ=Once1] :: (b_aKdA, w_aKdn) [LclId] = CCCS (,)! [b1_sKLE sat_sKLG]; } in GHC.Base.return $dMonad_sKLs sat_sKLH; }; } in let { sat_sKLB [Occ=Once1] :: m_aKdo (b_aKdA, w_aKdn) [LclId] = {eta1_sKLu, a1_sKLz} \u [] eta1_sKLu a1_sKLz; } in GHC.Base.>>= $dMonad_sKLs sat_sKLB sat_sKLI; -- 将惰性求值对象 sat_sKLj 拖到最后。 }; } in GHC.Base.>>= $dMonad_sKLs eta_sKLt sat_sKLJ; } in let { sat_sKLw [Occ=Once1] :: m_aKdo (b_aKdA, w_aKdn) -> Control.Monad.Trans.Writer.Strict.WriterT w_aKdn m_aKdo b_aKdA [LclId] = {} \r [ds_sKLv] ds_sKLv; } in GHC.Base.$ sat_sKLw sat_sKLK; ``` 末尾的那个惰性求值对象就是问题所在，它无法被强制，我们不能使用`seq`来绑定它的求值，因为它发生在`>>=`序列的末尾。**STG向我们澄清了这段代码的操作层面，使末尾的惰性求值对象显式化**。对于这类函数，你必须问自己：如果我们多次调用`>>=`会发生什么？ 例如，让我们手动展开以下定义： ```haskell m >>= \a -> f a >>= g ``` 结果如下： ``` WriterT $ do (a, w) <- runWriterT m (b, w') <- runWriterT $ WriterT $ do (a1, w1) <- runWriterT (f a) (b1, w1') <- runWriterT (g a1) return (b1, w1 `mappend` w1') return (b, w `mappend` w') ``` 现在我们有了两个惰性求值对象，延续了上一段的观点。我们使用的`>>=`越多，末尾就会有越多无法强制的惰性求值对象。**这就是为什么你不应该使用严格或惰性写法变换器（writer transformer），而应在常见用例中使用日志库**。 ### 2.2. 使用成本中心和*一个奇特技巧*在运行时捕获它们 由`cabal build --enable-profiling`插入的成本中心（cost centres）会标记我们程序中的每个顶级定义，并为我们提供被包装表达式所做内存使用和分配的良好统计信息。信息**太多**，无法从噪音中提取出好的信号。正因为这个原因，我更喜欢手动插入`SCC`，就像这样： ```haskell instance (Monoid w, Monad m) => Monad (WriterT w m) where return a = writer (a, mempty) {-# SCC >>= "myBind" #-} m >>= k = WriterT $ do (a, w) <- runWriterT m (b, w') <- ({-# SCC "bind_mine" #-} runWriterT (k a)) return (b, w `mappend` w') ``` 然后只在测试程序中收集这些信息。除此之外，Neil Mitchell描述了一种非常好的技巧（https://neilmitchell.blogspot.com/2015/09/detecting-space-leaks.html）来精确发现这种泄漏。*最终惰性求值对象会在递归调用树中被求值，如果我们限制运行时系统（RTS）可以使用该树的深度，它就会报错并打印一个异常，其中包含触发它的行和函数*。这在大型程序上非常有效，偶尔在你自己的程序上使用一下是个不错的选择。 ## 3. 避免活跃性泄漏 不属于流水线的长生命周期数据结构应该被强制求值为值，以释放捕获的自由变量。这些泄漏通常在使用`put`将计算存储在state monad中、或在`MVar`或其他引用类型上时表现出来。编译器无法对这些值施加需求，因为它对这些值何时（以及是否）会被需求是不透明的，因此它必须完全回退到惰性语义。**这里的通用解决方案是让每个流水线与一个良好的消费者结合**。具体而言，这意味着在流水线的结果值上有严格性注解。注解需要多深取决于上下文。鉴于这些泄漏是程序属性，最好避免它们，而不是用前面的原则来诊断它们。尽管*调用点*成本中心对于诊断可能的罪魁祸首效果最好。 例如，在： ```haskell import Data.Map.Strict import qualified Data.ByteString as B comp :: StateT (Map Char Int) IO () comp = do file <- liftIO (B.readFile "/path/to/big/file") let a :: Map Char Int a = ({-# SCC "my_pipeline" #-} (f . g . h) r) put a ``` 中，值`r`是从文件路径完全读取的（我们不会使用lazy IO）。该引用在`comp`的末尾被语法丢弃，然而`a`的闭包/惰性求值对象保持了一个对`r`值的活跃引用，因此GC无法收集它。我们可以使用该设置的成本中心（SCC）属性来测量该流水线随时间分配了多少总内存。在*调用点*而非顶级标识符上设置它们是一个强大但不常用的工具。解决方案是在`a`的输出值上有一个良好的消费者。在`comp`上单次`deepseq`可以解决这个问题。我们需要在这里使用`deepseq`而不是`seq`，因为`Data.Map.Strict`有需要求值的层次结构。 ```haskell import Data.Map.Strict import qualified Data.ByteString as B import Control.DeepSeq comp :: StateT (Map Char Int) IO () comp = do file <- liftIO (B.readFile "/path/to/big/file") let a :: Map Char Int a = (f . g . h) r a `deepseq` put a ``` 这是基于事件循环组织的程序中最常见的空间泄漏。这里是我一年前在xmonad-contrib中解决的一个泄漏示例（https://github.com/xmonad/xmonad-contrib/pull/653）。 ## 4. 避免过度共享泄漏 这种泄漏在实际程序中并不常见，但在像Project Euler这样的问题中却很普遍。它涉及生成器，即大型数据结构的闭包，这些结构不应被完全求值，而应以惰性方式逐层消费。如果生成器被传递给两个完全求值它们的函数，那么完整的实现将一直存储在堆中，直到第二个函数完成。这里的经典例子是求均值函数。 ```haskell mean :: (Fractional a, Foldable t) => t a -> a mean xs = sum xs / fromIntegral (length xs) ``` 表明此代码存在泄漏的一个好信号是*它获取一个Foldable并多次使用它*。补救措施来自三种不同的方法。 ### 4.1. 合并数据结构上的多次遍历为单次遍历 我首选的方法。你需要使用foldl包（https://hackage.haskell.org/package/foldl）使其符合人体工程学。生成器只被遍历一次，并使用正确的求值以避免严格性泄漏问题。 ### 4.2. 将生成器的创建移入函数内部，并将其包装在一个简单的函数中 这类似于： ```haskell mean :: Int -> Int mean i = let gen () = [1 .. i] in sum (gen ()) / fromIntegral (length (gen ())) ``` 虽然不太美观。 ### 4.3. 硬着头皮使用线性类型 如果我们将标识符的使用限制为只使用一次，上面的代码会发生什么？ ```haskell {-# Language LinearTypes #-} module Gato where import Data.Foldable mean :: (Fractional a, Foldable t) => t a %1 -> a mean xs = sum xs / fromIntegral (length xs) ``` 我们会得到以下错误： ``` > ghci linear.hs GHCi, version 9.2.6: https://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/slack/.ghci [1 of 1] Compiling Gato ( linear.hs, interpreted ) linear.hs:7:6: error: • Couldn't match type ‘'Many’ with ‘'One’ arising from multiplicity of ‘xs’ • In an equation for ‘mean’: mean xs = sum xs / fromIntegral (length xs) | 7 | mean xs = sum xs / fromIntegral (length xs) | ^^ Failed, no modules loaded. ``` 很好，我们怎么从这个错误出发呢？我们基本上必须使`xs`的整个消费过程显式化，并且只对其调用线性函数。这通过使用linear-base包（https://hackage.haskell.org/package/linear-base）可以更容易实现。