I have uploaded my test cases for Atomic Grouping / Possessive
Qualifier, which is the common code we seem to have developed, as this
may be of use to you.  I also have documentation, but for now, would you
mind running these tests against your code to see what the test outputs
and also, how did you come up with the 2x result?  Was that running the
test suite?  Usually, the regexp module is benchmarked against its test
suite and there are timings built into that, so it may be useful if you
could run the unmodified Lib/test/test_re.py you got from the trunk
against the original code before modification and your modification, and
do so a few times to get a good average result on multi-tasking systems,
and post the results here so we can get a good statistical feel for how
your new engine improves efficiency.  Certainly, I support any Engine
that works faster, as I myself have tried to make it faster but ended up
with something 8% slower instead, alas.

Also, good thinking on fixing the Negative Look-behind variable-width
issue; I wish I'd thought of that, but I am curious about something: did
you remove the optimization for fixed-width look-behind?  The old code
only allowed fixed with because that test can be done quickly; I noticed
your code adds a lot of new REV opcodes to handle back-tracking and I
assume look-behind logic for variable-width look-behind.  It would be
handy if the compiler and engine would be able to differentiate between
fixed-width look-behind (optimized as was originally) and variable-width
(using your advanced code).

Thanks to AMK for some of these suggestions.  Your changes are quite
radical though so I am still trying to wade through them all and I still
don't have a full-picture of how you've changed things, but there are
some good ideas here, IMHO, especially if you do indeed get 2x speedup.