Haskell 懒惰 Bytestring 的话不懒惰吗？

Question

我有以下 Haskell 程序用于计算整数字符串的最大和子串:

{-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -O2 #-}
import Data.Functor
import Data.Maybe 
import Data.ByteString.Lazy.Char8 (getContents,lines,readInt,words)
import Prelude hiding (getContents,words,lines)

main = do
    cont <- words <$> getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $ map (fst.fromJust.readInt) cont

opt (!c,!m) x = (max 0 (c+x),max m (c+x))

该程序的问题在于它将整个文件读入内存。不带BytesString的对应程序则不存在此问题:

{-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -O2 #-}
import Data.Functor
import Data.Maybe 

main = do
    cont <- words <$> getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $ map read cont
opt (!c,!m) x = (max 0 (c+x),max m (c+x))

它只使用少量的恒定内存，但速度当然非常慢(大约慢了 25 倍)。

只有读取非常大行的程序才会出现此问题。如果输入分布在多个小行上，ByteString 将按预期执行。

有什么办法可以解决这个问题吗？

Answer 1

惰性元组的使用不是最优的。最好重写为:

main = do
    cont <- words <$> getContents
    putStrLn $ show $ sndT $ foldl opt (T 0 0) $ map (fst.fromJust.readInt) cont

sndT :: T -> Int
sndT (T _ m) = m

opt (T c m) x = T (max 0 (c+x)) (max m (c+x))

data T = T {-# UNPACK #-} !Int  {-# UNPACK #-}!Int

所以你得到了一个严格的、未装箱的累加器。然而，你最好将整个事情写成增量左折叠。这就是为什么 readInt 在第二个参数中返回剩余输入的原因。不需要总和。 map 。单词管道。

<小时/>

您提交的版本存在空间泄漏。在大文件上运行，它使用与文件大小成比例的堆(在 640k 条目上)。

$ time ./A +RTS -p -s -K50M < input.txt.2
346882
     326,337,136 bytes allocated in the heap
     302,321,732 bytes copied during GC
      82,617,772 bytes maximum residency (8 sample(s))
       1,466,500 bytes maximum slop
             149 MB total memory in use (0 MB lost due to fragmentation)

  %GC     time      63.8%  (63.9% elapsed)

所以正如你所说，它保留了该文件。

那么什么是保留内存呢？一条线索是带有opt 的foldl。你传递给它一个惰性元组。 foldl 是 lazy in its accumulator .

因此，您只是在构建一长串未评估的 + 操作。 opt 上的 bang 模式没有区别，因为 foldl 从不评估其累加器。只有当你最后检查结果时，整个事情才会崩溃。

这是一次经典的空间泄漏。所以:

• 使用foldl'——它在累加器中是严格的
• 完全避免中间列表(使用 readInt + Expandr)。
• 如果必须遍历列表，请在累加器上使用严格元组以获得更好的性能。