Устранение неясной утечки пространства на Хаскеле - PullRequest
Новая
       26

Устранение неясной утечки пространства на Хаскеле

8 голосов
/ 22 октября 2011

Итак, после того, как я выжал последний бит производительности из некоторого Хаскелла, который я использую, чтобы разбить данные твита на n-граммы, я столкнулся с проблемой утечки пространства. Когда я выполняю профилирование, GC использует около 60-70% процесса, и для перетаскивания выделяется значительная часть памяти. Надеюсь, какой-нибудь гуру Хаскелла сможет подсказать, когда я ошибаюсь. 

{-# LANGUAGE OverloadedStrings, BangPatterns #-}
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.HashMap.Strict as H
import Text.Regex.Posix
import Data.List
import qualified Data.Char as C

isClassChar a = C.isAlphaNum a || a == ' ' || a == '\'' ||
                a == '-' || a == '#' || a == '@' || a == '%'

cullWord :: B.ByteString -> B.ByteString
cullWord w = B.map C.toLower $ B.filter isClassChar w

procTextN :: Int -> B.ByteString -> [([B.ByteString],Int)]
procTextN n t = H.toList $ foldl' ngram H.empty lines
  where !lines        = B.lines $ cullWord t
        ngram tr line = snd $ foldl' breakdown (base,tr) (B.split ' ' line)
        base          = replicate (n-1) ""

breakdown :: ([B.ByteString], H.HashMap [B.ByteString] Int) -> B.ByteString -> ([B.ByteString],H.HashMap [B.ByteString] Int)
breakdown (st@(s:ss),tree) word =
  newStack `seq` expandedWord `seq` (newStack,expandedWord)
      where newStack     = ss ++ [word]
            expandedWord = updateWord (st ++ [word]) tree

updateWord :: [B.ByteString] -> H.HashMap [B.ByteString] Int -> H.HashMap [B.ByteString] Int
updateWord w h = H.insertWith (+) w 1 h

main = do
  test2 <- B.readFile "canewobble"
  print $ filter (\(a,b) -> b > 100) $ 
     sortBy (\(a,b) (c,d) -> compare d b) $ procTextN 3 test2

1 Ответ

7 голосов
/ 22 октября 2011

Одной небольшой оптимизацией является фильтрация данных (используя HashMap.filter) перед их сортировкой.Это помогло мне сбить 2 секунды с окончательного времени выполнения.Я также использовал последовательности (Data.Sequence) вместо списков (без заметной разницы :-(). Мою версию можно найти здесь .

Просмотр кучипрофиль, я не думаю, что в вашей программе есть утечка пространства: Space profile

Вы просто создаете довольно большую хэш-таблицу (377141 пар ключ-значение) в памяти, а затем отбрасываете еепосле некоторой обработки. Согласно посту Йохана , хеш-таблица такого размера занимает приблизительно 5 * N + 4 * (N-1) слов = 3394265 * 4 байта ~ = 13 МБ, что согласуется с тем, чтопрофиль кучи показывает. Оставшееся место занимают ключи и значения. На моей машине время, проведенное в GC, составляет около 40%, что не кажется необоснованным, если вы постоянно обновляете хэш-таблицу и временные стеки.", не делая с данными ничего сложного для вычислений. Поскольку единственная операция, для которой вам нужна хеш-таблица, это insertWith, возможно, лучше использовать изменяемая структура данных ?

Обновление : Я переписал вашу программу с помощью изменяемой хеш-таблицы. Интересно, что разница в скорости невелика, но использование памяти немного лучше:

enter image description here

Как видите, размер блока, выделенного для хеш-таблицы, остается постоянным на протяжении всего выполнения.

...