2

我正在尝试我在互联网上遇到的“所有可能的”技巧，使用“所有可能的”组合!, seq, deepseq, ... 但我找不到在以下程序中抑制内存泄漏的方法

{-# LANGUAGE BangPatterns #-}

import Data.List
import Control.DeepSeq

foldl'' f z (x:xs) = let z' = f z x in z' `deepseq` foldl'' f z' xs 
foldl'' _ z [] = z

statistics :: [[Double]] -> [(Double, Double)]
statistics (z:zs) = normalize $ foldl'' go acc zs
  where acc = map (\x -> (x, x^2)) z
        go = zipWith (\(a, b) x -> (a + x, b + x^2))
        n  = 1 + (length zs)  
        dn = fromIntegral n
        normalize = map (\(a, b) -> (a / dn, (b - a^2 / dn) / dn))

main =  mapM_ (putStrLn . show) (statistics ps)
   where ps = take nn $ unfoldr (Just . splitAt mm) $ map sin [1..]
         nn = 1000
         mm = 1000

它计算“mm来自nn测量的变量”的均值和方差。

你能给我一个提示吗？

编辑

正如答案中指出的那样，问题出在调用length. 所以更好的版本可能是

{-# LANGUAGE BangPatterns #-}

import Data.List
import Control.DeepSeq

foldl'' f z (x:xs) = let z' = f z x in z' `deepseq` foldl'' f z' xs 
foldl'' _ z [] = z

statistics :: [[Double]] -> [(Double, Double)]
statistics (z:zs) = normalize $ foldl'' go acc zs
   where acc = (1, map (\x -> (x, x^2)) z)
         go = \(n, abs) xs -> (n + 1, zipWith (\(a, b) x -> (a + x, b + x^2)) abs xs)
         normalize (n, abs) = map (\(a, b) -> (a / n, (b - a^2 / n) / n)) abs

main =  mapM_ (putStrLn . show) (statistics ps)
   where ps = take nn $ unfoldr (Just . splitAt mm) $ map sin [1..]
         nn = 100
         mm = 1000000

但如果mm是大的，它仍然会泄漏，因为zipWith. 相反，我尝试过

zipWith' f xs ys = go f [] xs ys
   where go f zs (a:as) (b:bs) = 
             let zs' = (f a b) : zs in go f zs' as bs
         go _ zs _ _ = foldl' (\x y -> y : x) [] zs

但没有成功。

编辑

第二个改进示例的分析输出以及 fornn=100和mm=1e6：

   leak +RTS -p -h -RTS

total time  =        5.18 secs   (5180 ticks @ 1000 us, 1 processor)
total alloc = 4,769,555,408 bytes  (excludes profiling overheads)

    COST CENTRE       MODULE  %time %alloc

    main              Main     67.4   64.0
    main.ps           Main     18.1   21.6
    statistics.go.\   Main      6.7   11.7
    statistics.go.\.\ Main      5.3    1.9
    foldl''           Main      1.5    0.0


                                               individual     inherited
 COST CENTRE                 no.     entries  %time %alloc   %time %alloc

 MAIN                         46           0    0.0    0.0   100.0  100.0
  main                        94           0   67.4   64.0    67.4   64.0
  CAF                         91           0    0.0    0.0    32.6   36.0
   main                       92           1    0.0    0.0    32.6   36.0
    main.mm                   97           1    0.0    0.0     0.0    0.0
    main.nn                   96           1    0.0    0.0     0.0    0.0
    main.ps                   95           1   18.1   21.6    18.1   21.6
    statistics                93           1    0.0    0.0    14.5   14.4
     statistics.normalize    106           1    0.4    0.4     0.8    0.5
      statistics.normalize.\ 107      100000    0.4    0.1     0.4    0.1
     statistics.acc          102           1    0.2    0.3     0.3    0.3
      statistics.acc.\       104      100000    0.1    0.0     0.1    0.0
     statistics.go           100           1    0.0    0.0     0.0    0.0
     foldl''                  98          30    1.5    0.0    13.5   13.6
      foldl''.z'              99          29    0.0    0.0    12.0   13.6
       statistics.go         101           0    0.0    0.0    12.0   13.6
        statistics.go.\      103          29    6.7   11.7    12.0   13.6
         statistics.go.\.\   105     2900000    5.3    1.9     5.3    1.9

在此处输入图像描述

似乎，就像 Thomas M. DuBuisson 所建议的那样，“泄漏”与 的构造有关ps，但它还能如何构造呢？

4

1 回答 1

3

主要是猜测，但您调用length xsget 会n强制输入 list 的脊椎xs，从而产生大量 thunk。要进行快速测试，请使用1000代替dn并查看它是否有帮助。

对于完全懒惰，您可以尝试定义 normalize 而不必预先计算列表的长度。但这可能很难实现......

在您编辑的代码中，我相信没有真正的空间泄漏，只是昂贵的数据结构。切换到未装箱的向量后，代码运行速度更快，内存为 133MB。V.请注意，除了向函数添加一些内容外，我什么都不做改变：

{-# LANGUAGE BangPatterns #-}

import Data.List
import Control.DeepSeq
import qualified Data.Vector.Unboxed as V

foldl'' f z (x:xs) = let z' = f z x in z' `deepseq` foldl'' f z' xs 
foldl'' _ z [] = z

statistics :: [V.Vector Double] -> V.Vector (Double, Double)
statistics (z:zs) = normalize $ foldl'' go acc zs
   where acc = (1, V.map (\x -> (x, x^2)) z)
         go = \(n, abs) xs -> (n + 1, V.zipWith (\(a, b) x -> (a + x, b + x^2)) abs xs)
         normalize (n, abs) = V.map (\(a, b) -> (a / n, (b - a^2 / n) / n)) abs

main =  V.mapM_ (putStrLn . show) (statistics ps)
   where ps = take nn $ map V.fromList $ unfoldr (Just . splitAt mm) $ map sin [1..]
         nn = 100
         mm = 1000000

运行它+RTS -s会给出这些统计信息（我在输出运行时按了 Ctrl-C，因此执行时间很短）：

   3,009,534,792 bytes allocated in the heap
     324,022,224 bytes copied during GC
      51,390,128 bytes maximum residency (16 sample(s))
       4,896,504 bytes maximum slop
             133 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0      5617 colls,     0 par    0.20s    0.20s     0.0000s    0.0006s
  Gen  1        16 colls,     0 par    0.10s    0.10s     0.0063s    0.0322s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    1.39s  (  5.59s elapsed)
  GC      time    0.30s  (  0.30s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    1.70s  (  5.89s elapsed)

  %GC     time      17.8%  (5.1% elapsed)

  Alloc rate    2,163,064,609 bytes per MUT second

  Productivity  82.2% of total user, 23.7% of total elapsed

最大驻留大约为 50MB，这很好地对应于在V.zipWith. 堆上的 50MB 数据和使用中的 133MB 内存之间的差异来自于我们有一个复制垃圾收集器（这使需求加倍）以及可能来自运行时系统或其他组件的一些开销。

于 2013-08-20T15:01:28.440 回答