Haskell Regex performance

Question

Przeglądałem istniejące opcje dla regex w Haskell, i chciałem zrozumieć, skąd wzięła się luka w wydajności, porównując różne opcje ze sobą, a zwłaszcza z prostym wywołaniem grep .. .

mam stosunkowo małe (~ 110M, w porównaniu do zwykłych kilku 10s G w większości moich przypadków użycia) pliku śledzenia:

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

---

• raz pierwszy starał się znaleźć jak wiele dopasowań (arbitralnych) wzór .*504.*ll się tam przez grep:

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

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

---

• I spojrzał Text.Regex.TDFA (wersja 1.2.1) z 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 

Budowa i działanie:

$ 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 

---

• Potem spojrzał na Data.Text.ICU.Regex (wersja 0.7.0.1) z obsługą 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) 

budowania i uruchamiania:

$ 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 

---

Używam wersji ghc 7.6.3. Nie miałem okazji testowania innych opcji wyrażeń regularnych Haskell. Wiedziałem, że nie dostanę tego, co miałem z grepem i byłem z tego zadowolony, ale mniej więcej 20 razy wolniej niż TDFA i ByteString ... To bardzo przerażające. I naprawdę nie mogę zrozumieć, dlaczego tak właśnie jest, a naiwnie, że to było opakowanie w natywnym backend ... Czy w jakiś sposób nie używam tego modułu poprawnie?

(I niech nie wspominając OIOM + Tekst combo który przechodzi dachu)

Czy istnieje możliwość, że nie zostały jeszcze przetestowane, które uczyniłoby mnie szczęśliwszym?

EDIT:

• Text.Regex.PCRE (wersja 0.94.4) z 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 

budowania i uruchamiania:

$ 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 

Lepsze, ale nadal z czynnikiem ~ 7-ish ...

Answer 1

Po przejrzeniu innych bibliotek na chwilę skończyłem próbować PCRE.Ligth (wersja 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 [] 

Oto co mi wydostać się z tego:

$ 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 

myślę, że jest na tyle przyzwoity dla moich celów. Mogę spróbować zobaczyć, co dzieje się z innymi bibliotekami, kiedy ręcznie robię podział linii, tak jak tutaj, chociaż wątpię, że to zrobi dużą różnicę.