[boost] anfa-regex performance

From: Vladimir Pozdyayev (pvv_at_[hidden])
Date: 2005-01-12 02:28:23

Some time ago Eric Niebler wrote:

>You commented on the algorithmic complexity, but have you
>benchmarked against Boost.regex? I'd be very curious to see how your
>back-end stacks up performance-wise.

I have done some benchmarking of ANFA-regex versus Boost.Regex, and
it revealed the following (quite expected) trends.

    For very simple match problems ANFA-regex is by about an order of
    magnitude slower. Moreover, the slowdown noticeably increases
    with the number of capturing parentheses.

    For real-world-like match problems, like finding paragraphs of
    "libs/libraries.htm" by matching it against ".*?(<p>.*?</p>)",
    the slowdown drops to about 1.5x--2x. However, in this case the
    "regex_search" function of Boost.Regex performs much faster than
    "regex_match" (thanks to Knuth-Morris-Pratt algorithm, AFAICS).

    For complex / pathological problems ANFA-regex performs much
    faster (any number of orders of magnitude, depending on the
    problem) than Boost.Regex---the linear complexity pays off.

Both Boost.Regex and ANFA-regex have linear complexity for simple
regexes. Highly optimized nature of Boost.Regex allows its complexity
to have much lower time constant than that of ANFA-regex, resulting
in much better performance. However, for more involved regexes
Boost.Regex gets nonlinear complexity, with respective consequences.

The most obvious way of speeding up is to optimize the actual code
(or help the compiler to optimize it). The problem is, the ANFA
simulation algorithm is quite simple and straightforward, so there's
not much room for improvement. On the other hand, there's a whole new
story in optimizing the algorithm itself.

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.

These optimizations are subject to additional research.

And, of course, there are additional speed reserves in KMP for search
problems.

(A side note. An ANFA version used for benchmarking is not the version
I uploaded into yahoo groups recently---I actually managed to double
its speed, or something like that.)

-- 
Best regards,
Vladimir Pozdyayev.