regex - Atomic groups clarity

Question

Consider this regex.

a*b

This will fail in case of aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

This takes 67 steps in debugger to fail.

Now consider this regex.

(?>a*)b

This will fail in case of aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

This takes 133 steps in debugger to fail.

And lastly this regex:

a*+b  (a variant of atomic group)

This will fail in case of aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac

This takes 67 steps in debugger to fail.

When I check the benchmark atomic group (?>a*)b performs 179% faster.

Now atomic groups disable backtracking. So performance in match is good.

1. But why are the number of steps more? Can somebody explain on this?

2. Why is there a diff. in steps between two atomic groups (?>a*)b and a*+b.

Do they work differently?

Answer 1

Author note:

? ? This answer targets question 1 as delivered by the bounty text "I am looking forward to the exact reason why more steps are being needed by the debugger.I dont need answers explaining how atomic groups work.";
? ? Jerry's answer addresses the other concerns very well, while my other answer takes a ride through the mentioned constructs, how they work, and why they are important. For full knowledge, simply reading this post is not enough!

Every group in a regular expression takes a step to step into and out of the group.

? ? WHAT?!
Yeah, I'm serious, read on...

Firstly, I would like to present you with quantified non-capturing groups, over without the group:

Pattern 1: (?:c)at
Pattern 2: cat

So what exactly happens here? We'll match the patterns with the test string "concat" on a regex engine with optimizations disabled:

While we're at it, I present you some more groups:

? ? Oh no! I'm going to avoid using groups!

But wait! Please note that the number of steps taken to match has no correlation with the performance of the match. pcre engines optimizes away most of the "unnecessary steps" as I've mentioned. Atomic groups are still the most efficient, despite more steps taken on an engine with optimizations disabled.

Perhaps relevant:

• Why is a character class faster than alternation?