Improving std.regex(p)

[sybrandy]

> I think only backtracking engines (not DFAs) have the exponential run
> time problem. Regular expression grammar is itself context free (so it's
> parsable efficiently), the NFA and NFA->DFA algorithms are polynomial,
> and the generated DFA makes one transition per input character.
>
>
> Andrei

I don't know how practical it is, but I had a thought to allow some of 
these nasty regexes to run better: use threads.  In theory, and I have 
not done any work to test/prove this so it's very theoretical, you can 
have multiple threads running in parallel each testing a potential path. 
  Granted, there's always the issue of spawning/managing threads and 
potentially overloading the system by spawning too many, however it may 
be a viable alternative if you really HAVE to execute a particularly 
nasty regex.

Anyway, it's just a thought.  I'd hate to lose the benefits of a NFA if 
we're afraid of the potential performance hit if a user writes a bad regex.

Casey