Ottimizzazione di un semplice parser che è chiamato molte volte

Question

Ho scritto un parser per un file personalizzato utilizzando attoparsec. Il rapporto di profilazione ha indicato che circa il 67% dell'allocazione della memoria viene eseguita in una funzione denominata tab, che consuma anche la maggior parte del tempo. La funzione tab è piuttosto semplice:

tab :: Parser Char
tab = char '\t'

.

L'intero rapporto di profilazione è il seguente:

       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

.

Come posso ottimizzare questo?

L'intero codice per il parser è qui. Il file che sto analizzando è in giro77 MB.

Answer 1

tab è un capro espiatorio. Se si definisce boo :: Parser (); boo = return () e inserisci un boo prima di ogni legame nella definizione snapshotParser, le allocazioni dei costi diventeranno qualcosa come:

 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

.

Quindi sembra che il profiler stia spostando la colpa per le allocazioni dei risultati Parse, probabilmente a causa di un ampio deline del codice attoparsec, come John l suggeriti nei commenti.

Per quanto riguarda i problemi di performance, il punto chiave è che, poiché si sta analizzando un file di testo da 77 MB per creare un elenco con un milione di elementi, si desidera che il trattamento dei file sia pigro e non rigoroso. Una volta che è stato risolto, disaccoppiando I / O e analizzazione in doStuff e costruire anche l'elenco delle istantanee senza un accumulatore. Ecco una versione modificata del tuo programma in considerazione.

{-# 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

.

Questa versione dovrebbe avere prestazioni accettabili anche se costringe l'intera lista di istantanee in memoria, come ho fatto in main qui. Per valutare ciò che è "accettabile", tenere presente che, dato i sedici (piccoli (piccoli, unboxed) campi in ogni Snapshot più il overhead dei costruttori di Snapshot e Elenco, stiamo parlando di 152 byte per cella di lista, che si riducono a ~ 152 MB per i dati del test. In ogni caso, questa versione è il più pigro possibile, come puoi vedere rimuovendo la divisione in main o sostituirlo da last ss.

n.b.: I miei test sono stati fatti con ATTOPASEC-0.12.

Answer 2

Dopo aver aggiornato l'Attoparsec all'ultima versione ( 0,12.0.0 ), il tempo impiegato per eseguire ridurre da 38 secondi a 16 secondi.Questo è più del 50% di velocità.Anche la memoria consumata da esso ridotta drasticamente.Come ha notato @johnl, con il profilazione abilitato, i risultati sono osservati selvaggiamente.Quando ho provato a rivelarlo con l'ultima versione della libreria Attoparsec, ci sono voluti circa 64 secondi per eseguire l'intero programma.