Проблемы кучи в Haskell со стилем передачи параметров - PullRequest
Новая
       12

Проблемы кучи в Haskell со стилем передачи параметров

14 голосов
/ 21 июня 2011

Вот простая программа, которая отправляет мою кучу в Kingdom Come: 

intersect n k z s rs c
  | c == 23   = rs
  | x == y    = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1)
  | x < y     = intersect (n+1) k (z+1) s rs c
  | otherwise = intersect n (k+1) z s rs c
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))
p = intersect 1 1 1 0 [] 0

main = do
  putStr (show p)

Программа вычисляет пересечение двух бесконечных рядов, останавливаясь, когда достигает 23 элементов.Но это не важно для меня.

Интересно то, что, насколько я могу судить, здесь не должно быть много того, что сидит в куче.Функция intersect является рекурсивной со всеми рекурсиями, записанными как хвостовые вызовы.Государство накапливается в аргументах, а их мало.5 целых чисел и небольшой список кортежей.

Если бы я был игроком, делающим ставки, я бы поспорил, что в аргументах так или иначе создается thunks, особенно в аргументах, которые не оцениваютсяданная рекурсия.Но это просто дикая догадка.

В чем здесь проблема?И как можно это исправить?

Ответы [ 2 ]

36 голосов
/ 21 июня 2011

Если у вас проблема с кучей, запустите профилировщик кучи , например: 

$ ghc -O2 --make A.hs -prof -auto-all -rtsopts -fforce-recomp
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A.exe ...

Который при запуске: 

$ ./A.exe +RTS -M1G -hy

Создает A.hp выходной файл: 

$ hp2ps -c A.hp

Вроде так:

enter image description here

Таким образом, ваша куча заполнена Integer, что указывает на некоторую проблему в накоплении параметров ваших функций - где все Integer s.

Изменение функции так, чтобы она была строгой в ленивых Integer аргументах (исходя из того факта, что вы никогда не проверяли их значение), например: 

{-# LANGUAGE BangPatterns #-}

intersect n k !z !s rs c
  | c == 23   = rs
  | x == y    = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1)
  | x < y     = intersect (n+1) k (z+1) s rs c
  | otherwise = intersect n (k+1) z s rs c
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))

p = intersect 1 1 1 0 [] 0

main = do
  putStr (show p)

И ваша программа теперь работает в постоянном пространстве со списком выдаваемых вами аргументов (хотя не завершается для c == 23 в любое разумное время).

enter image description here

9 голосов
/ 22 июня 2011

Если все в порядке, чтобы получить результирующий список в обратном порядке, вы можете воспользоваться ленью Хаскелла и вернуть список по мере его вычисления, вместо того, чтобы передавать его рекурсивно в качестве накопительного аргумента.Это не только позволяет вам потреблять и распечатывать список во время его вычисления (тем самым устраняя одну утечку места), вы также можете принять решение о том, сколько элементов вы хотите получить из intersect: 

{-# LANGUAGE BangPatterns #-}

intersect n k !z s
  | x == y    = f : intersect (n+1) (k+1) (z+1) (z+s)
  | x < y     = intersect (n+1) k (z+1) s
  | otherwise = intersect n (k+1) z s
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))
p = intersect 1 1 1 0

main = do
  putStrLn (unlines (map show (take 23 p)))

Как отметил Дон, мы должны быть осторожны, чтобы накапливающиеся аргументы оценивались своевременно, а не накапливали большие громы.Делая аргумент z строгим, мы гарантируем, что все аргументы будут востребованы.

Выводя по одному элементу на строку, мы можем наблюдать за полученным результатом: 

$ ghc -O2 intersect.hs && ./intersect
[1 of 1] Compiling Main             ( intersect.hs, intersect.o )
Linking intersect ...
(1,3,1)
(3,15,4)
(10,120,14)
(22,528,36)
(63,4095,99)
(133,17955,232)
(372,139128,604)
(780,609960,1384)
...
...