Пакетная обработка файлов в Haskell не улучшает профиль пространства
У меня есть простой алгоритм, который нужно реализовать: сравнить каждую строку с другой. Каждая строка содержит одно число, а функция сравнения - расстояние. Итоговым результатом является сумма всех расстояний.
Это можно просто реализовать следующим образом:
sumOfDistancesOnSmallFile :: FilePath -> IO Integer
sumOfDistancesOnSmallFile path = withFile path ReadMode $ \h->do
distances <- liftM ( (map textRead) ) $ hListToEOF Text.hGetLine h
let subSet = drop offset distances
let emptySubSet = null subSet
return $ if (emptySubSet)
then (0)
else (distancesManyToMany subSet)
hListToEOF :: (Handle -> IO a) -> Handle -> IO [a]
hListToEOF func h = do
element <- func h
atEOF <- hIsEOF h
rest <- case(atEOF) of
True -> return []
False -> hListToEOF func h
return $ element:rest
distancesManyToMany :: [Integer]->Integer
distancesManyToMany (x:xs) = distancesOneToMany x xs + (distancesManyToMany xs)
distancesManyToMany _ = 0
distancesOneToMany :: Integer -> [Integer] -> Integer
distancesOneToMany one many = sum $ map (distance one) many
distance :: Integer -> Integer -> Integer
distance a b = (a-b)
Чтобы получить разумно большие данные в каждой строке, я использовал следующий генератор файлов:
createTestFile :: Int -> FilePath -> IO ()
createTestFile n path = writeFile path $ unlines $ map show $ take n $ infiniteList 0 1
where infiniteList :: Integer->Integer-> [Integer]
infiniteList i j = (i+j) * (i+j) : infiniteList j (i+j)
Файл из 2000 строк , из 840 Кбайт займет 1,92 секунды и выделено 1,5 Гбайт с максимальным использованием около 1,5 Мбайт.
Строчный файл 6 Кбайт размером 7,5 Мбайт займет 22 секунды, выделение 34 Гбайт с максимальным использованием памяти около 15 Мбайт
К сожалению, мои данные будут содержать миллионы строк. Сначала я попытался повысить скорость (о чем я спрашивал в двух предыдущих сообщениях о MapReduce в сочетании с Iteratee IO ), но на самом деле проблема ограничения - это пространство.
Промежуточная мысль ]: Это можно решить, прочитав полный файл для каждого числа для сравнения. Это требует много дополнительного времени, потому что файл необходимо открыть и проанализировать для каждой строки, которая должна сравниваться с остальной частью файла. Также количество выделений памяти станет квадратичным. Так что это не очень полезно в качестве окончательного решения
Последний шаг : Это был мой первый шаг к моей цели: массовая казнь. Хочу взять в память несколько k строк. Примените алгоритм ManyToMany к тем, что находятся в памяти. Затем выполните итерацию по оставшейся части файла. На каждом шаге итерации необходимо прочитать и проанализировать только одну последовательную строку, которую затем можно сравнить со всеми элементами в пакете памяти.
Выбрав достаточно большой размер пакета, файл не нужно часто перечитывать . Моя реализация выглядит следующим образом:
sumOfDistancesOnBigFileUsingBatches :: FilePath -> Int -> Int -> IO Integer
sumOfDistancesOnBigFileUsingBatches path batchSize offset = do
(firstResult, maybeRecurse) <- singleResultBatch path batchSize offset
recursiveResult <- case maybeRecurse of
Nothing -> return 0
Just newOffset -> sumOfDistancesOnBigFileUsingBatches path batchSize newOffset
return $ firstResult + recursiveResult
singleResultBatch :: FilePath -> Int -> Int -> IO(Integer, Maybe Int)
singleResultBatch path batchSize offset = withFile path ReadMode $ \h->do
distances <- readDistances h
let (batch, subSet) = splitAt batchSize $ drop offset distances
let batchInner = distancesManyToMany batch
let recursionTerminated = null subSet
let (batchToSubSet, newOffset) = if (recursionTerminated)
then (0, Nothing)
else (distancesSetToSet batch subSet, Just (offset+batchSize))
return (batchInner+batchToSubSet, newOffset)
where
readDistances h = liftM ( (map textRead) ) $ hListToEOF Text.hGetLine h
distancesSetToSet :: [Integer] -> [Integer] -> Integer
distancesSetToSet xs ys = sum $ map (\one->distancesOneToMany one xs) ys
В строчном файле размером 2К с размером пакета 500 он закончился с выделением 2,16 секунды, 2,2 ГБ и примерно 6 МБ необходимого пространства. Это в 4 раза больше, чем в самой простой версии! Это может быть совпадением, но также используются 4 пакета ...
Что меня удивило, так это то, что все необходимое пространство используется сначала, а затем необходимое пространство только уменьшается. Это становится проблемой для строкового файла размером 50 КБ (500 МБ), потому что тогда ему не хватает памяти.
Мой вопрос: почему пакетное решение потребляет больше памяти? Кажется, что для каждого пакета в памяти хранится весь файл, хотя он должен (по крайней мере, это мое намерение) хранить в памяти только один пакет.
EDIT : Я удалил детали файла строк размером 6k и пакетов из 500 строк (я взял неправильный файл профиля)
И в качестве дополнения, вот профиль пространства, сгенерированный с использованием файла строк 2k и пакетов из 500 строк:
РЕДАКТИРОВАТЬ2 : Профилирование с фиксатором привело к появлению:
total time = 2.24 secs (112 ticks @ 20 ms)
total alloc = 2,126,803,896 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
textRead MapReduceTestStrictStrings 47.3 44.4
distance MapReduceTestStrictStrings 25.9 25.3
distancesOneToMany MapReduceTestStrictStrings 18.8 29.5
singleResultBatch MapReduceTestStrictStrings 4.5 0.0
readTextDevice Data.Text.IO.Internal 2.7 0.0
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
main Main 1604 2 0.0 0.0 100.0 100.0
sumOfDistancesOnBigFileUsingBatches MapReduceTestStrictStrings 1605 4 0.0 0.0 100.0 100.0
singleResultBatch MapReduceTestStrictStrings 1606 20 4.5 0.0 100.0 100.0
distancesSetToSet MapReduceTestStrictStrings 1615 3 0.0 0.0 34.8 43.3
distancesOneToMany MapReduceTestStrictStrings 1616 3000 14.3 23.2 34.8 43.2
distance MapReduceTestStrictStrings 1617 1500000 20.5 20.0 20.5 20.0
textRead MapReduceTestStrictStrings 1614 5000 47.3 44.4 47.3 44.4
distancesManyToMany MapReduceTestStrictStrings 1611 2004 0.0 0.0 9.8 11.7
distancesOneToMany MapReduceTestStrictStrings 1612 2000 4.5 6.3 9.8 11.6
distance MapReduceTestStrictStrings 1613 499000 5.4 5.3 5.4 5.3
hListToEOF MapReduceTestStrictStrings 1609 23996 0.9 0.6 3.6 0.6
readTextDevice Data.Text.IO.Internal 1610 1660 2.7 0.0 2.7 0.0
CAF:main4 Main 1591 1 0.0 0.0 0.0 0.0
CAF:main5 Main 1590 1 0.0 0.0 0.0 0.0
main Main 1608 0 0.0 0.0 0.0 0.0
CAF GHC.Num 1580 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD 1526 2 0.0 0.0 0.0 0.0
CAF GHC.IO.FD 1510 2 0.0 0.0 0.0 0.0
CAF System.Event.Thread 1508 3 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 1487 2 0.0 0.0 0.0 0.0
CAF System.Event.Internal 1486 2 0.0 0.0 0.0 0.0
CAF System.Event.Unique 1483 1 0.0 0.0 0.0 0.0
CAF GHC.Conc.Signal 1480 1 0.0 0.0 0.0 0.0
CAF Data.Text.Internal 813 1 0.0 0.0 0.0 0.0
CAF Data.Text.Array 811 1 0.0 0.0 0.0 0.0
Retainer sets created during profiling:
SET 2 = {}
SET 3 = {}
SET 15 = {}
SET 17 = {}
SET 18 = {<>}
SET 44 = {}
SET 47 = {, }
SET 56 = {}
SET 57 = {<>, }
SET 66 = {, }
SET 67 = {, <>, }
SET 72 = {, }
SET 76 = {}
SET 81 = {, , }
SET 83 = {, , , }
SET 86 = {, <>}
SET 95 = {}
SET 96 = {, }
SET 100 = {, }
SET 102 = {, , }
SET 103 = {}
SET 136 = {, }
SET 143 = {, , }
SET 144 = {}
SET 145 = {, }
SET 146 = {}
SET 147 = {, }
SET 148 = {, }
И следующего образа .hp:
РЕДАКТИРОВАТЬ 3: Все предыдущие коды использовали пакеты:
Data.Text.IO
Data.Text
Data.Text.Read
Когда я использую их ленивые версии, общее использование времени / памяти / пространства на самом деле не меняется: 2,62 секунды, выделение 2,25 ГБ и пространство 5,5 МБ
Принятое решение : Ленивые версии не работали, потому что hListToEOF вынудил полное чтение файла (я ожидал, что конструктор: будет работать лениво).
Решение состоит в использовании следующих операций импорта:
import qualified Data.ByteString.Char8 as Str
import qualified Data.Text.Lazy.IO as TextIO
import qualified Data.Text.Lazy as T
import Data.Text.Lazy.Read
и в singleResultBatch функция следующая модификация:
readDistances = liftM ( (map textRead . T.lines)) $ TextIO.readFile path
Тогда и скорость (2,72 с), и распределение памяти (2,3 ГБ) не изменятся, что и ожидается.
Профиль кучи (использование пространства) действительно улучшается (1,8 МБ вместо 5,5 МБ), как видно на:
