Утечка пространства только в определенных случаях в интерпретаторе GHC при выполнении: concat!!N - PullRequest
Новая
       6

Утечка пространства только в определенных случаях в интерпретаторе GHC при выполнении: concat!!N

25 голосов

Я определяю свою собственную версию concat, myConcat: 

module Eh where

myConcat []          = []
myConcat ([]:os)     = myConcat os
myConcat ((x:xs):os) = x : myConcat (xs:os)

(!!!)  :: [a] -> Int -> a
xs     !!! n | n < 0 = error "negative index"
[]     !!! _         = error "index too large"
(x:_)  !!! 0         = x
(_:xs) !!! n         = xs !!! (n-1)

Если я сделаю myConcat <some huge list> !! n в интерпретаторе GHC, он украдет мою память со скоростью 300 МБ / с, и мне придется убить ее, прежде чем она сможет вызвать убийцу ООМ. Обратите внимание, что я загружаю Eh как «интерпретированный», я не компилирую его перед загрузкой. 

code run in the GHC interpreter        space leak?
myConcat (repeat [1,2,3,4]) !! (10^8)  Yes
concat (repeat [1,2,3,4]) !! (10^8)    No
myConcat (repeat [1,2,3,4]) !!! (10^8) No
concat (repeat [1,2,3,4]) !!! (10^8)   No

Теперь, если я скомпилирую Eh (ghc --make -O2 Eh.hs), а затем загрузлю его в интерпретатор и перезапущу эти тесты, ни один из них не утечет пространство. То же самое, если я скомпилирую каждый тестовый пример вместо того, чтобы запускать их в интерпретаторе.

Что происходит?

Я использую GHC 6.12.3.

1 Ответ

1 голос
/ 28 октября 2011

Проблема здесь в строгости. Оценка в Haskell не является строгой, поэтому вычисления обычно выполняются, только если их результаты действительно необходимы. Вместо этого создается так называемый поток, представляющий еще не выполненное вычисление.

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

Haskell Wiki , вероятно, объясняет это лучше.

Чтобы исправить вашу myConcat функцию, вы должны убедиться, что она не создает миллионы громад, если принудительно выполнить строгую оценку вручную. Один (не очень красивый) способ сделать это может быть: 

myConcat []          = []
myConcat ([]:os)     = myConcat os
myConcat ((x:xs):os) = ((:) $! x) myConcat (xs:os)
...