Re: [boost] anfa-regex performance

From: John Maddock (john_at_[hidden])
Date: 2005-01-12 05:48:14

Apologies for being way behind with your messages - I haven't had a chance 
to examine your code yet.

> Two main slowdown factors are (1) excessive tag copying and (2)
> nondeterminism. I can name two ways to reduce (1). The factor (2) is
> all about ANFA to ADFA conversion.

Copying, is always a real killer, unless you can elliminate memory 
allocations.   More than anything else these will soak up cycles, especially 
on multi-processor systems where the locking can really kill performance 
(imagine multiple threads all calling new/delete constantly).

> These optimizations are subject to additional research.
>
> And, of course, there are additional speed reserves in KMP for search
> problems.

Actually, I think I may remove that code as a dis-optimisation, a simple 
scan for first character is probably faster in the *average* case, and of 
course if you can do a Boyer-search that's even better.

Like you, more research is needed!

John.