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

[ChrisK]

Justin Bailey wrote:
> On 7/31/07, Donald Bruce Stewart <dons at cse.unsw.edu.au> 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