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

Question

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

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

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

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

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

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

2) Иметь функцию buildHelper :: CrawlState -> IO [WArticle] (ниже) возврат [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

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!) обрабатывать статьи одну за другой по мере их создания.

Answer 2

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

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 МБ.