Как заставить foldl потреблять постоянную память? - PullRequest
Новая
       31

Как заставить foldl потреблять постоянную память?

0 голосов
/ 20 февраля 2019

Мы определяем следующий тип данных Stupid: 

import qualified Data.Vector as V
import Data.List (foldl')
data Stupid = Stupid {content::V.Vector Int, ul::Int} deriving Show

Теперь у меня есть два слегка отличающихся кода. 

foldl' (\acc x->Stupid{content=(content acc) V.// [(x,x+123)],ul=1}) (Stupid {content=V.replicate 10000 10,ul=1}) $ take 100000 $ cycle [0..9999]

занимает постоянную память (~ 100M), тогда как 

foldl' (\acc x->Stupid{content=(content acc) V.// [(x,x+123)],ul=ul acc}) (Stupid {content=V.replicate 10000 10,ul=1}) $ take 100000 $ cycle [0..9999]

занимает огромное количество памяти (~ 8 ГБ).

Теоретически, требуется только одна копия текущего объекта Stupid, хотя и не требуется для обоих случаев.Я не понимаю, почему существует такая разница в потреблении памяти, если я хочу получить доступ и записать ul acc.

Может кто-нибудь объяснить, почему это происходит, и дать обходной путь для постоянной памяти, если мне нужен доступul acc?Спасибо.

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

1 Ответ

0 голосов
/ 20 февраля 2019

Я бы попытался принудительно задать поля Stupid и посмотреть, поможет ли это. 

let f acc x = c `seq` a `seq` Stupid{content=c,ul=a}
       where
       c = content acc V.// [(x,x+123)]
       a = ul acc
in foldl' f (Stupid {content=V.replicate 10000 10,ul=1}) $
   take 100000 $
   cycle [0..9999]

Это должно быть почти эквивалентно форсированию параметров функции: 

foldl' (\acc x -> acc `seq` x `seq` 
        Stupid{content=(content acc) V.// [(x,x+123)],ul=ul acc})
   (Stupid {content=V.replicate 10000 10,ul=1}) $ take 100000 $ cycle [0..9999]

(Это также может быть записано с помощью шаблонов взрыва, если таковые предпочтительнее.)

Другой вариант, более агрессивный, заключается в использовании аннотаций строгости в определении конструктора Stupid. 

data ... = Stupid { content = ! someType , ul :: ! someOtherType }

Это всегда будет принудительно заполнять эти поля во всей программе.

...