[Haskell-cafe] Re: Knuth Morris Pratt for Lazy Bytestrings implementation

Justin Bailey wrote:

On 7/31/07, Donald Bruce Stewart wrote:

...

jgbailey: Also, be sure to compare against a naive search, optimised for strict and lazy bytestrings,

http://hpaste.org/1803

If its not faster than those 2, then you're doing something wrong :)

-- Don

Yes, I was really hoping someone (dons :)) would look at my code and give any suggestions. Did the attachment come through?

Justin

I will make measurements. I already see that

{-# OPTIONS_GHC -fbang-patterns #-} module KMPSeq (kmpMatch)

kmpMatch' :: B.ByteString -> Int64 -> Int -> Int64 kmpMatch' !str !currIdx !patShift

let matchLength' !pat !str !cnt | B.null pat = {-# SCC "kmpMatch_nullPatStr" #-} cnt matchLength' !pat !str !cnt | B.null str = {-# SCC "kmpMatch_nullStr" #-} 0 matchLength' !pat !str !cnt | (B.head pat == B.head str) = {-# SCC "kmpMatch_eqHead" #-}

Is a huge win. It now uses 3 MB instead of 243 MB and runs faster. -- Chris