regexps

Stephen Weeks MLton@sourcelight.com
Tue, 12 Jun 2001 00:22:36 -0700


> I'm surprised that you see a big speedup in the NFA simulation.  

? I didn't say this.  I only said that I expect to speedup mlprof.  I anticipate
using the DFA in that case.

> I like the
> NFA because it never gets very bad, but for simple regular expressions it
> should be a bit slower.  Hmm... I guess your original code isn't so different
> from an NFA simulation except that you don't fold duplicates, which is very
> very cheap.

The original code does a lot of allocation per input character.  The NFA
simulation doesn't do any.  The next state computation is also easier.  Thus,
there is a good chance the new NFA code will be faster than the old symbolic
code, but I haven't done any measurements.  The DFA code will be much faster
(than either).

> I'm still playing around with some ideas for what I want in regular expressions,
> but don't let that stop you.

Yeah, I'm probably going to do my old notion of saves for now.  I'm also not
sure how to handle your longest/shortest match star operator, but it's probably
doable.

> Any notion on where the 3x for native code is coming from?

Nope.  I'll leave that to Matthew :-)