Оптимизация простого парсера, который вызывается много раз
-
02-01-2020 - |
Вопрос
Я написал парсер для пользовательского файла, используя attoparsec
.В отчете о профилировании указано, что около 67% выделения памяти выполняется функцией с именем tab
, что также отнимает больше всего времени.А tab
функция довольно проста:
tab :: Parser Char
tab = char '\t'
Весь отчет о профилировании выглядит следующим образом:
ASnapshotParser +RTS -p -h -RTS
total time = 37.88 secs (37882 ticks @ 1000 us, 1 processor)
total alloc = 54,255,105,384 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
tab Main 83.1 67.7
main Main 6.4 4.2
readTextDevice Data.Text.IO.Internal 5.5 24.0
snapshotParser Main 4.7 4.0
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 75 0 0.0 0.0 100.0 100.0
CAF Main 149 0 0.0 0.0 100.0 100.0
tab Main 156 1 0.0 0.0 0.0 0.0
snapshotParser Main 153 1 0.0 0.0 0.0 0.0
main Main 150 1 6.4 4.2 100.0 100.0
doStuff Main 152 1000398 0.3 0.0 88.1 71.8
snapshotParser Main 154 0 4.7 4.0 87.7 71.7
tab Main 157 0 83.1 67.7 83.1 67.7
readTextDevice Data.Text.IO.Internal 151 40145 5.5 24.0 5.5 24.0
CAF Data.Text.Array 142 0 0.0 0.0 0.0 0.0
CAF Data.Text.Internal 140 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD 122 0 0.0 0.0 0.0 0.0
CAF GHC.Conc.Signal 103 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding 101 0 0.0 0.0 0.0 0.0
CAF GHC.IO.FD 100 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 89 0 0.0 0.0 0.0 0.0
main Main 155 0 0.0 0.0 0.0 0.0
Как мне это оптимизировать?
Весь код потому что парсер здесь. Размер файла, который я анализирую, составляет около 77 МБ.
Решение
tab
является козлом отпущения.Если вы определите boo :: Parser (); boo = return ()
и вставьте boo
перед каждым связыванием в snapshotParser
По определению, распределение затрат будет выглядеть примерно так:
main Main 255 0 11.8 13.8 100.0 100.0
doStuff Main 258 2097153 1.1 0.5 86.2 86.2
snapshotParser Main 260 0 0.4 0.1 85.1 85.7
boo Main 262 0 71.0 73.2 84.8 85.5
tab Main 265 0 13.8 12.3 13.8 12.3
Таким образом, похоже, что профилировщик перекладывает вину за распределение результатов анализа, вероятно, из-за обширного встраивания attoparsec
код, как предложил Джон Л. в комментариях.
Что касается проблем с производительностью, ключевым моментом является то, что, поскольку вы анализируете текстовый файл размером 77 МБ для построения списка из миллиона элементов, вы хотите, чтобы обработка файла была ленивой, а не строгой.Как только это будет решено, разделение ввода-вывода и синтаксического анализа doStuff
и построение списка снимков без аккумулятора также полезны.Вот модифицированная версия вашей программы с учетом этого.
{-# LANGUAGE BangPatterns #-}
module Main where
import Data.Maybe
import Data.Attoparsec.Text.Lazy
import Control.Applicative
import qualified Data.Text.Lazy.IO as TL
import Data.Text (Text)
import qualified Data.Text.Lazy as TL
buildStuff :: TL.Text -> [Snapshot]
buildStuff text = case maybeResult (parse endOfInput text) of
Just _ -> []
Nothing -> case parse snapshotParser text of
Done !i !r -> r : buildStuff i
Fail _ _ _ -> []
main :: IO ()
main = do
text <- TL.readFile "./snap.dat"
let ss = buildStuff text
print $ listToMaybe ss
>> Just (fromIntegral (length $ show ss) / fromIntegral (length ss))
newtype VehicleId = VehicleId Int deriving Show
newtype Time = Time Int deriving Show
newtype LinkID = LinkID Int deriving Show
newtype NodeID = NodeID Int deriving Show
newtype LaneID = LaneID Int deriving Show
tab :: Parser Char
tab = char '\t'
-- UNPACK pragmas. GHC 7.8 unboxes small strict fields automatically;
-- however, it seems we still need the pragmas while profiling.
data Snapshot = Snapshot {
vehicle :: {-# UNPACK #-} !VehicleId,
time :: {-# UNPACK #-} !Time,
link :: {-# UNPACK #-} !LinkID,
node :: {-# UNPACK #-} !NodeID,
lane :: {-# UNPACK #-} !LaneID,
distance :: {-# UNPACK #-} !Double,
velocity :: {-# UNPACK #-} !Double,
vehtype :: {-# UNPACK #-} !Int,
acceler :: {-# UNPACK #-} !Double,
driver :: {-# UNPACK #-} !Int,
passengers :: {-# UNPACK #-} !Int,
easting :: {-# UNPACK #-} !Double,
northing :: {-# UNPACK #-} !Double,
elevation :: {-# UNPACK #-} !Double,
azimuth :: {-# UNPACK #-} !Double,
user :: {-# UNPACK #-} !Int
} deriving (Show)
-- No need for bang patterns here.
snapshotParser :: Parser Snapshot
snapshotParser = do
sveh <- decimal
tab
stime <- decimal
tab
slink <- decimal
tab
snode <- decimal
tab
slane <- decimal
tab
sdistance <- double
tab
svelocity <- double
tab
svehtype <- decimal
tab
sacceler <- double
tab
sdriver <- decimal
tab
spassengers <- decimal
tab
seasting <- double
tab
snorthing <- double
tab
selevation <- double
tab
sazimuth <- double
tab
suser <- decimal
endOfLine <|> endOfInput
return $ Snapshot
(VehicleId sveh) (Time stime) (LinkID slink) (NodeID snode)
(LaneID slane) sdistance svelocity svehtype sacceler sdriver
spassengers seasting snorthing selevation sazimuth suser
Эта версия должна иметь приемлемую производительность, даже если вы принудительно сохраните в памяти весь список снимков, как я сделал в main
здесь.Чтобы оценить, что является «приемлемым», имейте в виду, что, учитывая шестнадцать (маленьких, неупакованных) полей в каждом Snapshot
плюс накладные расходы принадлежащий Snapshot
и конструкторы списков, мы говорим о 152 байтах на ячейку списка, что для ваших тестовых данных составляет ~ 152 МБ.В любом случае, эта версия максимально ленивая, в чем вы можете убедиться, удалив разделение в main
, или заменив его на last ss
.
Примечание:Мои тесты проводились с attoparsec-0.12.
Другие советы
После обновления attoparsec до последней версии (0.12.0.0), время выполнения сократится с 38 секунд до 16 секунд.Это более чем 50% ускорение.Кроме того, резко сократился объем потребляемой им памяти.Как заметил @JohnL, при включенном профилировании результаты сильно различаются.Когда я попытался профилировать ее с помощью последней версии библиотеки attoparsec, выполнение всей программы заняло около 64 секунд.