Optimierung eines einfachen Parsers, der viele Male aufgerufen wird

Question

Ich habe einen Parser für eine benutzerdefinierte Datei geschrieben mit attoparsec.Aus dem Profiling-Bericht geht hervor, dass etwa 67 % der Speicherzuweisung in einer Funktion mit dem Namen erfolgt tab, was auch die meiste Zeit in Anspruch nimmt.Der tab Funktion ist ziemlich einfach:

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

Der gesamte Profiling-Bericht lautet wie folgt:

       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

Wie optimiere ich das?

Der gesamte Code denn der Parser ist hier. Die Datei, die ich analysiere, ist etwa 77 MB groß.

Answer 1

tab ist ein Sündenbock.Wenn Sie definieren boo :: Parser (); boo = return () und fügen Sie a ein boo vor jeder Bindung im snapshotParser Definition werden die Kostenzuweisungen etwa so aussehen:

 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

Es scheint also, dass der Profiler die Schuld für die Zuweisungen der Parse-Ergebnisse abwälzt, was wahrscheinlich auf umfangreiches Inlining von zurückzuführen ist attoparsec Code, wie John L in den Kommentaren vorgeschlagen hat.

Was die Leistungsprobleme betrifft, ist der entscheidende Punkt, dass Sie beim Parsen einer 77-MB-Textdatei, um eine Liste mit einer Million Elementen zu erstellen, eine langsame und nicht strenge Dateiverarbeitung wünschen.Sobald das geklärt ist, entkoppeln Sie die E/A und führen das Parsen durch doStuff und das Erstellen der Snapshot-Liste ohne Akkumulator sind ebenfalls hilfreich.Hier ist eine modifizierte Version Ihres Programms, die dies berücksichtigt.

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

Diese Version sollte eine akzeptable Leistung haben, selbst wenn Sie die gesamte Liste der Schnappschüsse in den Speicher zwingen, wie ich es in getan habe main Hier.Um zu beurteilen, was „akzeptabel“ ist, bedenken Sie dies angesichts der jeweils sechzehn (kleinen, nicht ausgepackten) Felder Snapshot plus die Overhead des Snapshot und Listenkonstruktoren sprechen wir von 152 Bytes pro Listenzelle, was sich auf ~152 MB für Ihre Testdaten reduziert.In jedem Fall handelt es sich bei dieser Version um die größtmögliche Faulheit, wie Sie anhand der Entfernung der Unterteilung in sehen können main, oder durch ersetzen last ss.

Hinweis:Meine Tests wurden mit attoparsec-0,12 durchgeführt.

Answer 2

Nach dem Aktualisieren des AttoparSec auf die neueste Version ( 0,12.0.0 ), die Zeit, die zur Ausführung von 38 Sekunden bis 16 Sekunden ausgeführt wird.Das ist mehr als 50% Beschleunigung.Auch der von ihm verbrauchte Speicher reduziert drastisch.Wie @johnl angemerkt, mit der Profilierung aktiviert, variieren die Ergebnisse wild.Wenn ich versuchte, es mit der neuesten Version der Attoparsec-Bibliothek zu profilieren, dauerte er ungefähr 64 Sekunden, um das gesamte Programm auszuführen.