Haskell: как избавиться от утечки памяти

Question

Я пытался «всевозможные» трюки. Я наткнулся на интернет, с «всеми возможными» комбинациями !, 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 измерений».

Не могли бы вы дать мне подсказку?

EDIT

Как указано в ответах, проблема заключается в вызове 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 

но безуспешно.

EDIT

Профилирующая выход для второго усовершенствованного примера и nn=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 

Кажется, как Томас М. Dubuisson предположил, что " утечка "связана со строительством ps, но как еще он может быть построен?

Answer 1

В основном угадайте, но ваш звонок length xs для получения n заставляет позвоночник входного списка xs, создавая много thunks. Для быстрого теста используйте 1000 вместо dn и посмотрите, поможет ли он.

Для полной лени, вы можете попытаться определить нормализацию без предварительной подсчета длины списка. Но это, вероятно, довольно сложно сделать ...

В вашем отредактированном коде я считаю, что это не настоящая космическая утечка, а просто дорогие структуры данных. Код работает намного быстрее и в 133 МБ оперативной памяти после переключения на распакованные векторы. Обратите внимание, как у меня было ничего не менять, но добавить немного 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 

максимальная ординатура составляет примерно 50 МБ, что хорошо соответствует трем копиям векторов Unboxed 1000000 пара двойников, находящимся в прямом эфире, в то же время в течение V.zipWith. Разница между 50 МБ данных в куче и используемой 133 МБ памяти исходит из того факта, что у нас есть копировальный сборщик мусора (который удваивает спрос) и, вероятно, некоторые накладные расходы из системы времени выполнения или других компонентов.