Где утечка памяти при использовании StateT s IO a?

Question

Намерение: Небольшое приложение для изучения Haskell: загружает статью википедии, затем загружает все статьи, связанные с ней, затем загружает все статьи, связанные с ними, и так далее ... до указанной глубины рекурсиидостигнутоРезультат сохраняется в файл.

Подход: Используйте StateT для отслеживания очереди загрузки, загрузки статьи и обновления очереди.Я строю список IO [WArticle] рекурсивно, а затем распечатываю его.

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

Анализ: По литературе я считаю, что это проблема лени и / или строгости.BangPatterns уменьшил потребление памяти, но не решил пропорциональность.Кроме того, я знаю, что все статьи загружаются до начала вывода файла.

Возможные решения:

1) Функция getNextNode :: StateT CrawlState IO WArticle (ниже) уже имеет IO.Одним из решений будет просто записать в него файл и только вернуть состояние.Это означало бы, что файл записан очень маленькими порциями.Не чувствует себя очень Haskell ..

2) Имейте функцию buildHelper :: CrawlState -> IO [WArticle] (ниже) return [IO WArticle].Хотя я бы не знал, как переписать этот код, и в комментариях мне об этом говорили

Являются ли какие-либо из предложенных решений лучше, чем я думаю, или есть лучшие альтернативы?

import GetArticle (WArticle, getArticle, wa_links, wiki2File) -- my own
type URL = Text

data CrawlState =
     CrawlState  ![URL]       ![(URL, Int)]
          --    [Completed]    [(Queue, depth)]
-- Called by user
buildDB :: URL -> Int -> IO [WArticle]
buildDB startURL recursionDepth = buildHelper cs
    where cs = CrawlState [] [(startURL, recursionDepth)]

-- Builds list recursively
buildHelper :: CrawlState -> IO [WArticle]
buildHelper !cs@(CrawlState _ queue) = {-# SCC "buildHelper" #-}
  if null queue
    then return []
    else do
      (!article, !cs') <- runStateT getNextNode cs
      rest <- buildHelper cs'
      return (article:rest)

-- State manipulation
getNextNode :: StateT CrawlState IO WArticle
getNextNode = {-# SCC "getNextNode" #-} do
  CrawlState !parsed !queue@( (url, depth):queueTail ) <- get
  article <- liftIO $ getArticle url
  put $ CrawlState (url:parsed) (queueTail++ ( if depth > 1
          then let  !newUrls  = wa_links article \\ parsed
                    !newUrls' = newUrls          \\ map fst queue
                    in zip newUrls' (repeat (depth-1))
          else []))
  return article

startUrl = pack "https://en.wikipedia.org/wiki/Haskell_(programming_language)"
recursionDepth = 3

main :: IO ()
main =  {-# SCC "DbMain" #-}
  buildDB startUrl recursionDepth
   >>= return . wiki2File
   >>= writeFile "savedArticles.txt"

Полный код на https://gitlab.com/mattias.br/sillyWikipediaSpider. Текущая версия ограничена загрузкой только первых восьми ссылок с каждой страницы, чтобы сэкономить время.Не меняя его, загрузите 55 страниц при использовании кучи ~ 600 МБ.

Спасибо за любую помощь!

Answer 1

Добавление дальнейшего объяснения и построения кода на ответ Данидиаз. Вот окончательный код:

import Streaming
import qualified Streaming.Prelude as S
import System.IO (IOMode (WriteMode), hClose, openFile)

buildHelper :: CrawlState -> Stream (Of WArticle) IO ()
buildHelper cs@( CrawlState _ queue ) = 
  if null queue
    then return ()
    else do
      (article, cs') <- liftIO (runStateT getNextNode cs)
      S.yield article
      buildHelper cs'

main :: IO ()
main = do outFileHandle <- openFile filename WriteMode
          S.toHandle outFileHandle  . S.show . buildHelper $
              CrawlState [] [(startUrl, recursionDepth)]
          hClose outFileHandle

outFileHandle - обычный дескриптор вывода файла.

S.toHandle берет поток String и записывает их в указанный дескриптор.

S.show карты show :: WArticle -> String через поток.

Элегантное решение, которое создает ленивый поток, даже если он создается серией операций ввода-вывода (а именно, загрузкой веб-сайтов), и записывает его в файл по мере появления результатов. На моей машине он все еще использует много памяти (относительно задачи) во время выполнения, но никогда не превышает 450 МБ.

Answer 2

2) Требуется ли [IO WArticle] в этом случае, чтобы я хотел?

Не совсем.Проблема в том, что некоторые действия IO WArticle зависят от результата предыдущего действия: ссылки на будущие страницы находятся на ранее полученных страницах.[IO Warticle] не может этого представить: чисто в том смысле, что вы всегда можете найти действие в списке без выполнения предыдущих действий.

Нам нужен своего рода «эффективный список», который позволяетмы извлекаем статьи одну за другой, постепенно выполняя необходимые эффекты, но не заставляя нас полностью генерировать список за один раз.

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

Примечание: Экземпляры Functor, Applicative и Monad для этих библиотек отличаются от соответствующих экземпляров для чистых списков.Functor экземпляры отображаются на итоговое конечное значение, а не на промежуточные значения, которые получены.Чтобы отобразить полученные значения, они предоставляют отдельных функций .И Monad экземпляры последовательность эффективных списков, вместо того, чтобы пробовать все комбинации.Чтобы попробовать все комбинации, они предоставляют отдельные функции .

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

import Streaming
import qualified Streaming.Prelude as S

buildHelper :: CrawlState -> Stream (Of WArticle) IO ()
buildHelper !cs@(CrawlState _ queue) = 
  if null queue
    then return []
    else do (article, cs') <- liftIO (runStateT getNextNode cs)
            S.yield article
            buildHelper cs'

И затем мы могли бы использовать такие функции, как mapM_ (из Streaming.Prelude, а не из Control.Monad!), Чтобы обрабатывать статьи одну за другой по мере их генерирования.