Prestazioni Haskell Regex

Question

Ho esaminato le opzioni esistenti per regex in Haskell e volevo capire da dove proveniva il divario in termini di prestazioni confrontando le varie opzioni tra loro e soprattutto con una semplice chiamata a grep .. .

ho un relativamente piccolo (~ 110M, rispetto a un normale diverse 10s di G nella maggior parte dei miei casi d'uso) file di traccia:

$ du radixtracefile 
113120 radixtracefile 
$ wc -l radixtracefile 
1051565 radixtracefile 

---

• primo luogo ho cercato di trovare il modo molte partite del (arbitrario) modello .*504.*ll erano lì attraverso grep:

$ time grep -nE ".*504.*ll" radixtracefile | wc -l 
309 

real 0m0.211s 
user 0m0.202s 
sys 0m0.010s 

---

• Ho guardato Text.Regex.TDFA (versione 1.2.1) con Data.ByteString:

import Control.Monad.Loops 
import Data.Maybe 
import qualified Data.Text as T 
import qualified Data.Text.IO as TIO 
import Text.Regex.TDFA 
import qualified Data.ByteString as B 

main = do 
    f <- B.readFile "radixtracefile" 
    matches :: [[B.ByteString]] <- f =~~ ".*504.*ll" 
    mapM_ (putStrLn . show . head) matches 

Building and running:

$ ghc -O2 test-TDFA.hs -XScopedTypeVariables 
[1 of 1] Compiling Main    (test-TDFA.hs, test-TDFA.o) 
Linking test-TDFA ... 
$ time ./test-TDFA | wc -l 
309 

real 0m4.463s 
user 0m4.431s 
sys 0m0.036s 

---

• Poi, ho guardato Data.Text.ICU.Regex (versione 0.7.0.1) con supporto Unicode:

import Control.Monad.Loops 
import qualified Data.Text as T 
import qualified Data.Text.IO as TIO 
import Data.Text.ICU.Regex 

main = do 
    re <- regex [] $ T.pack ".*504.*ll" 
    f <- TIO.readFile "radixtracefile" 
    setText re f 
    whileM_ (findNext re) $ do 
     a <- start re 0 
     putStrLn $ "last match at :"++(show a) 

costruzione e la gestione:

$ ghc -O2 test-ICU.hs 
[1 of 1] Compiling Main    (test-ICU.hs, test-ICU.o) 
Linking test-ICU ... 
$ time ./test-ICU | wc -l 
309 

real 1m36.407s 
user 1m36.090s 
sys 0m0.169s 

---

Io uso ghc versione 7.6.3. Non ho avuto l'occasione di testare altre opzioni regex di Haskell. Sapevo che non avrei ottenuto le prestazioni che avevo con grep e ne sono stato più che felice, ma più o meno 20 volte più lento per TDFA e ByteString ... Questo è molto spaventoso. E non riesco davvero a capire perché sia ​​quello che è, poiché ingenuamente penso che fosse un wrapper su un backend nativo ... In qualche modo non sto usando il modulo correttamente?

(E non parlare del combo ICU + Testo che sta attraversando il tetto)

Esiste un'opzione che non ho ancora testato che mi renderebbe più felice?

EDIT:

• Text.Regex.PCRE (versione 0.94.4) con Data.ByteString:

import Control.Monad.Loops 
import Data.Maybe 
import Text.Regex.PCRE 
import qualified Data.ByteString as B 

main = do 
    f <- B.readFile "radixtracefile" 
    matches :: [[B.ByteString]] <- f =~~ ".*504.*ll" 
    mapM_ (putStrLn . show . head) matches 

costruzione e la gestione:

$ ghc -O2 test-PCRE.hs -XScopedTypeVariables 
[1 of 1] Compiling Main    (test-PCRE.hs, test-PCRE.o) 
Linking test-PCRE ... 
$ time ./test-PCRE | wc -l 
309 

real 0m1.442s 
user 0m1.412s 
sys 0m0.031s 

Meglio, ma ancora con un fattore di ~ 7-ish ...

Answer 1

Quindi, dopo aver esaminato un po 'le altre librerie, ho finito per provare PCRE.Ligth (versione 0.4.0.4):

import Control.Monad 
import Text.Regex.PCRE.Light 
import qualified Data.ByteString.Char8 as B 

main = do 
    f <- B.readFile "radixtracefile" 
    let lines = B.split '\n' f 
    let re = compile (B.pack ".*504.*ll") [] 
    forM_ lines $ \l -> maybe (return()) print $ match re l [] 

Ecco quello che uscire da quella:

$ ghc -O2 test-PCRELight.hs -XScopedTypeVariables 
[1 of 1] Compiling Main    (test-PCRELight.hs, test-PCRELight.o) 
Linking test-PCRELight ... 
$ time ./test-PCRELight | wc -l 
309 

real 0m0.832s 
user 0m0.803s 
sys 0m0.027s 

credo che questo sia abbastanza decente per i miei scopi. Potrei provare a vedere cosa succede con le altre librerie quando faccio manualmente la divisione delle righe come ho fatto qui, anche se dubito che farà una grande differenza.