[Haskell-cafe] Spelling checker exercise

[Daniel Fischer]

Am Montag 25 Januar 2010 05:34:50 schrieb Matthew Phillips:
> On 24/01/2010, at 10:22 PM, Daniel Fischer wrote:
>
> <...>
>
> > I think I know what happened here:
> >
> > $ ghc -fforce-recomp --make matthew -o matthew0
>
> <...>
>
> > I habitually compile all code with -O2, unless I have a specific
> > reason not to. I tend to forget that some compile without
> > optimisations. For some kinds of code that makes hardly any
> > difference, for others it makes a big difference.
>
> I used the flags "-funbox-strict-fields -fvia-C -optc-O2", but *not*
> -O2. Whoops! I could kick myself: I blindly assumed that -optc-O2 would
> turn on optimisation, but of course that's just the flag for GCC.

By the way, compiling via C nowadays hardly ever produces faster code than 
the native code generator (most times I tried since 6.10, if there was a 
difference, native was faster).

>
>   $ time ./spelling becuase
>   becuase -> because
>
>   real	0m4.467s
>   user	0m3.865s
>   sys	0m0.280s
>
>   $ time ./spelling_df becuase
>   becuase -> because
>
>   real	0m2.422s
>   user	0m2.198s
>   sys	0m0.081s
>
> Your previous version is close to twice as fast, and now only 2.5 times
> slower than Python.
>
> <snipped new version of code with toLower removed>
>
> With your suggested changes, your latest version on my machine:
>
>   $ time ./spelling_df becuase
>   becuase -> because
>
>   real	0m1.731s
>   user	0m1.572s
>   sys	0m0.056s
>
> Now, we're getting close: 4.7s -> 2.3s -> 1.7s.
>
> >>> But once you start needing two edits (try korrekt), correct and
> >>> edits1 start to show up. That shows that Norvig's algorithm isn't
> >>> really good. With two edit steps, you create a _lot_ of strings you
> >>> need to look up, far more than there are in the map. That takes
> >>> time. It'll be better to scan the map for entries with an edit
> >>> distance (< 3) if you have a good method to check that
> >
> > Indeed:
> > $ time ./nLDBSWSpelling becuase
> > becuase -> because
> > 2.84user 0.02system 0:02.86elapsed 100%CPU
> > $ time ./nLDBSWSpelling korrekt
> > korrekt -> correct
> > 2.83user 0.05system 0:02.88elapsed 100%CPU
>
> Not sure if I see what you're saying here: do you mean to point out the
> 2.86 vs 2.88 elapsed?

Well, above the code, I had the times for Norvig's algorithm (creating all 
two-step edits and checking which are known):

> > And, without profiling:
> > $ time ./spellingBSW becuase
> > becuase -> because
> > 2.84user 0.03system 0:02.88elapsed 99%CPU
> >
> > Finally, building the set of two-step edits takes longer than the
> > additional lookups:
> >
> > $ time ./spellingBSW becuase
> > becuase -> because
> > 2.84user 0.03system 0:02.88elapsed 99%CPU
> > $ time ./spellingBSW korrekt
> > korrekt -> correct
> > 3.50user 0.02system 0:03.52elapsed 100%CPU
> >
> > vs.
> >
> > $ time ./spellingBSWL becuase
> > becuase -> because
> > 2.79user 0.04system 0:02.83elapsed 100%CPU
> > $ time ./spellingBSWL3 korrekt
> > korrekt -> correct
> > 3.20user 0.02system 0:03.23elapsed 99%CPU

For "becuase", which is a one-step edit, all take the same time (within 
normal fluctuation), 2.8x seconds.
For the two-step edit "korrekt", the version building Sets takes 3.5 
seconds, the version which doesn't build a Set of two-step edits takes 3.2 
seconds, *and the version scanning the Map of known words for entries with 
a Levenshtein distance [modified to account for transpositions] less than 
3, takes 2.8y seconds, practically the same time as for the one-step edit*.

It becomes more obvious, perhaps, if we test a couple of two-steppers:

Lazy Levenshtein:

 time ./nLDBSWSpelling becrase korrekt halmos territoir gutzenperg
becrase -> because
korrekt -> correct
halmos -> holmes
territoir -> territory
gutzenperg -> gutenberg
2.94user 0.03system 0:02.97elapsed 100%CPU

just something like 0.1 - 0.15 seconds more than for "becuase", that makes 
0.02 - 0.04 seconds per two-edit correction.

Sets:

$ time ./spellingBSW becrase korrekt halmos territoir gutzenperg
becrase -> because
korrekt -> correct
halmos -> holmes
territoir -> territory
gutzenperg -> gutenberg
7.48user 0.03system 0:07.55elapsed 99%CPU

Gewalt geschrien! That takes almost a second per two-edit correction.

List:

$ time ./spellingBSWL3 becrase korrekt halmos territoir gutzenperg
becrase -> because
korrekt -> correct
halmos -> holmes
territoir -> territory
gutzenperg -> gutenberg
5.54user 0.04system 0:05.58elapsed 99%CPU

Better, but still bad, roughly half a second per correction.

Python without psyco:

$ time python ./norvig.py becrase korrekt halmos territoir gutzenperg
Trained in  1.46993017197 seconds
because
correct
holmes
territory
gutenberg
3.00user 0.08system 0:03.09elapsed 99%CPU
$ time python ./norvig.py becuase
Trained in  1.49027395248 seconds
because
1.46user 0.08system 0:01.55elapsed 100%CPU

about 0.3 seconds per correction

and with:

$ time python ./norvig.py becrase korrekt halmos territoir gutzenperg
Trained in  1.22417902946 seconds
because
correct
holmes
territory
gutenberg
2.12user 0.09system 0:02.21elapsed 100%CPU
$ time python ./norvig.py becuase
Trained in  1.17486715317 seconds
because
1.14user 0.08system 0:01.23elapsed 99%CPU

about 0.2 seconds per correction.

(Just for the record, I found out what Python did in the half second I 
couldn't account for: it looked for matches for "./norvig.py", I forgot 
that Python passes the name of the script in argv[0] - d'oh)

>
> >>> Another thing is
> >>>
> >>> allWords = keysSet wordCounts
> >>>
> >>> Ouch. For each correction, you construct that set anew. Just use
> >>> member from Data.Map instead of Data.Set.member and look up the
> >>> words in the map.
> >>
> >> Whoops! Just to be clear though: Haskell will memoise the result of
> >> "allWords" for a given invocation of "correct"?
> >
> > Yes. But not across different invocations.
> >
> >> So this would only make a large difference for multiple corrections?
> >
> > Right. But that's the interesting use case, isn't it?
>
> It will be when I get the the rest of it working, yes :)
>
> >>>> I will look at using Bloom Filters or
> >>>> Trie’s instead of Data.Map, but I wonder if readFile should be
> >>>> taking nearly %30 of the run time, even for a 6MB file?
> >>>
> >>> No way. But it doesn't seem to, from my GHC's point of view.
> >>
> >> Just to be sure I wasn't using the SCC incorrectly, I split out the
> >> readFile call into "myReadFile". The prof line comes out as:
> >>
> >>  myReadFile            Main         210           1  35.8    8.6
> >> 35.8    8.6
> >>
> >> i.e. 35.8%  of runtime.
> >
> > Can I see the exact code which gives that profile?
> > Somehow, things which shouldn't must be attributed to readFile.
>
> The version at this link has myReadFile split out.
>
> http://github.com/scramjet/spelling/blob/31071edb2166b2bc4d350358900d975
>228fd43b9/spelling.hs
>
> Doing the same to your version has the same result:
>
>   myReadFile       Main       210           1  45.7    9.6    45.7   
> 9.6
>
> It does seem that the profiler is wrong or misleading somehow.

Strange. Doing that here has no such effect. The only line in the profile 
(ByteString) where myReadFile occurs is

   myReadFile  Main  260   1   0.0  0.9   0.0    0.9   0   6507348

(snipped whitespace), entered once, allocated 6.5 million bytes, took not 
measurable time.

Both, compiled via C and with the native code generator.

With String IO, it costs 4.6% time and 8.1% allocation.

>
> Two other quick questions:
>
> (1) you added parentheses to "candidates":
>
>   candidates = known [word] `or` ((known e1) `or` known_edits2)
>
> The "or"'s should short circuit so that if "known [word]" is non-empty,
> the others shouldn't be evaluated. I read the above as forcing
> evaluation of the second "or" first: am I wrong?

Au contraire, 
"Any operator lacking a fixity declaration is assumed to be infixl 9" 
says the report, so without parentheses, it's parsed as

(known [word] `or` known e1) `or` known_edits2

and both 'or's must be evaluated even if word is known. Since 'or' is lazy 
in its second argument, if we associate it

known [word] `or` (known e1 `or` known_edits2)

, in case of a known word, we needn't look at the parenthesis at all (it 
will probably not make a measurable difference in running time unless you 
check a couple of million known words, but still, it feels lazier). For a 
local definition, I thought an explicit fixity declaration was overkill.

>
> (2) you eliminated the "fold" in "correct" in favour of a tail-recursive
> search in "maxCount": was this for style or performance reasons (or both
> :)?

Performance, kind of. Since the lists we fold over are in fact short, it 
doesn't really matter, but if they were long, there'd be the risk of 
unnecessarily allocating lots of pairs. I'm rather confident that with -O2, 
GHC will eliminate the pairs anyway, but without looking at the core, I'm 
not entirely sure.
However, in fact it was an unthought-through rewrite because I just had 
someone with a stack overflow in spite of foldl' due to the laziness of the 
data constructors[*]. So I made sure that that couldn't happen, without 
looking at the folded function to see if that already prevents it. And in 
fact, it does, so using a foldl' if you use lists instead of Sets is fine, 
with respect to style, even preferable.

[*] classic example: why will

average xs = sum / len
   where
      (sum,len) = foldl' accum (0,0) xs
      accum (sm,ln) x = (sm+x,ln+1)

cause a stack overflow for long lists?

>
> Cheers,
>
> Matthew.