Optimierung eines einfachen Parser, der oft aufgerufen wird

Question

Ich schrieb einen Parser für eine benutzerdefinierte Datei mit attoparsec. Der Profiling-Bericht zeigte, dass rund 67% der Speicherzuweisung in einer Funktion namens tab erfolgt, die auch die meiste Zeit verbraucht. Die tab Funktion ist recht einfach:

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

Der gesamte Profilierung Bericht ist 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 kann ich das optimieren?

Der gesamte Code for the parser is here. Die Datei, die ich analysiere, ist um 77MB.

Answer 1

tab ist ein Sündenbock. Wenn Sie boo :: Parser(); boo = return() definieren und ein boo vor jeder bind in der snapshotParser Definition einzufügen, werden sich die Kostenumlagen so etwas wie:

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 

So scheint es der Profiler für die Zuordnungen der Parsing-Ergebnisse der Schuld verlagert, wahrscheinlich aufgrund zu umfangreichen Inlining von attoparsec Code, wie John L. in den Kommentaren vorgeschlagen.

Bei den Leistungsproblemen besteht der entscheidende Punkt darin, dass Sie beim Analysieren einer 77 MB-Textdatei zum Erstellen einer Liste mit einer Million Elementen die Dateiverarbeitung faul und nicht strikt durchführen möchten. Sobald das erledigt ist, ist das Entkoppeln von E/A und das Parsen in doStuff und das Erstellen der Liste von Snapshots ohne Akkumulator ebenfalls hilfreich. Hier ist eine modifizierte Version Ihres Programms 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 

sollte diese Version noch eine akzeptable Leistung, wenn Sie die ganze Liste von Snapshots in den Speicher erzwingen, wie ich hier in main tat. Um zu beurteilen, was "akzeptabel" ist, bedenken Sie, dass wir angesichts der sechzehn Felder (kleine, ungefüllte) in jedem Snapshot plus overhead der Snapshot und Listenkonstruktoren über 152 Bytes pro Listenzelle sprechen, die auf ~ herunter läuft 152 MB für Ihre Testdaten. In jedem Fall ist diese Version ungefähr so ​​faul wie möglich, wie Sie sehen können, indem Sie die Division in main entfernen oder durch last ss ersetzen.

N.B .: Meine Tests wurden mit Attoparsec-0.12 durchgeführt.

Answer 2

Nach der Aktualisierung des attoparsec auf die neueste Version (0.12.0.0) reduziert sich die Ausführungszeit von 38 Sekunden auf 16 Sekunden. Das ist mehr als 50% Beschleunigung. Auch die von ihm verbrauchte Speichermenge wurde drastisch reduziert. Wie @JohnL bemerkt, sind die Ergebnisse bei aktiviertem Profiling sehr unterschiedlich. Als ich versuchte, es mit der neuesten Version der attoparsec-Bibliothek zu profilieren, dauerte es ungefähr 64 Sekunden, um das gesamte Programm auszuführen.