Лень в сворачивании результата операции карты - PullRequest
Новая
       5

Лень в сворачивании результата операции карты

0 голосов
/ 29 июня 2018

Почему эта функция вызывает высокое использование памяти, и есть ли предложения по сокращению использования памяти?

РЕДАКТИРОВАТЬ : более минимальный пример

Пример (1) GC видит, что каждый элемент не нужен после печати, так как используется мало памяти: 

printThings = readThing >=> mapM_ (parseThing >>> print)

Пример (2) Весь список хранится в памяти 

printThings = readThing >=> map parseThing >>> print

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

У меня есть программа, которая считывает данные, анализирует их и уменьшает их. В качестве минимального примера: 

aFoo :: FilePath -> IO ()
aFoo = readFile >=> lines >>> map convertStringToB >>> reduceBsToC >>> print
reduceBsToC = foldl' bToC base

Если быть более точным, я лениво читаю в файле: 

import Data.ByteString.Lazy.Char8 as B
actualFoo = B.readFile >=> B.split '\n' >>> map convertByteStringToB >>> reduceBsToC >>> print)

Я вижу много использования памяти для этой программы (~ 4 ГБ с моим вводом) для чего-то вроде:

  • Весь файл читается в память
  • Или, что более вероятно, весь результат map сохраняется в памяти

Я ожидал, что [B], созданный map convertByteStringStringToB, будет лениво читаться сгибом. Если я просто печатаю [B], я не вижу такого поведения, и используется гораздо меньше памяти (~ 10 МБ): 

readFoo :: FilePath -> IO [ByteString]
readFoo = B.readFile >=> B.split '\n' >>> return
printFoo :: FilePath -> IO ()
printFoo = readFoo >=> mapM_ (convertByteStringToB >>> print)
-- Lazily reading in file and converting each 'line'

Я знаю, что реализация foldl': 

foldl' f z []     = z
foldl' f z (x:xs) = let z' = z `f` x 
                    in seq z' $ foldl' f z' xs

Я предположил, что (x:xs) использует thunk для представления xs, иначе весь результат операции map будет в памяти.

EDIT

convertByteStringToC и reduceBsToC были запрошены для уточнения:

convertByteStringToC - это мегапарсек функция, которая слишком длинна для этого формата.

reduceBsToC использует fgl . (Упрощенный): * * тысяча шестьдесят-пять 

type MyGraph = Gr UNode UEdge
reduceBsToC :: MyGraph -> B -> MyGraph
reduceBsToC gr End = gr
reduceBsToC gr b = maybe makeDefault setGraph (tryAddToGr gr b)

Ответы [ 2 ]

0 голосов
/ 30 июня 2018

Без добавления полного и поддающегося проверке примера я смог разобраться в проблеме.

Мои вычисления в мегапарсеке лениво оценивались в самом конце во время финального print, то есть весь файл считывался для генерации вычислений, но не выполнялся сразу.

Я добавил строгие поля к конструкторам данных, получив return ed в моих синтаксических анализаторах. E.g.:

data MyParsedData = MyParsedData { value1 :: !Int, value2 :: !Int }

Это вынуждает следующее анализировать сразу после создания MyParsedData, вместо того, чтобы анализ был отложен. 

myParse = do
    val1 <- parseVal1
    val2 <- parseVal2
    return $ MyParsedData val1 val2

Кроме того, я попытался отказаться от строгих полей и вместо этого использовал BangPatterns , что также исправило проблему. Это включало добавление прагмы BangPatterns и ее использование при сопоставлении паттерна с моими данными позже в функции накопления foldl (ссылаясь на исходный вопрос): 

tryAddtoGr gr (MyParsedData !val1 !val2) = ...

Это вызывает выполнение анализа во время фолда.

Уточнение : MyParsedData создается непосредственно перед сопоставлением с шаблоном, когда он используется в сгибе.

0 голосов
/ 29 июня 2018

reduceBsToC создает график Gr. Он представлен в виде Map, который не является ленивой или потоковой структурой (это дерево). Таким образом, фолд накапливает график, возможно, такой же большой, как и исходный список.

...