OK I have had a closer look and was interested in reading about “worst case quadratic time complexity”. I ran the initial example he gave using VitRegex:
? st.trace('---- recursion test 1 from https://iev.ee/blog/the-quadratic-problem-nobody-fixed/')
st.setValue('bbbbbbbbbb')
startTime = clock()
matches = regex.matchAllRegex(st,'.*a|b')
timeTaken = clock() - startTime
if matches = 10
? st.trace('10 matches found')
passCount += 1
else
errCount += 1
LogIt('recursion test 1 Failed: matches=' & matches & ' but expected 10' )
end
but the time was barely measurable. Then I remembered he said
a 50-character input can take longer than the heat death of the universe . it’s exponential.
a quick search found that this heat death of the universe was
estimated to occur in roughly 10 ^ 100 years (a 1 followed by 100 zeros).
that sounded like a challenge. TBH I didn’t have that many years to wait around so hoped it was faster.
I remembered those old cartoons with a skeleton sitting in front of a VDU (remember those?) due to the sluggish response time.
I used the debug/tracing version of VitRegex (latest version 1.09) in order to see the backtracking and there were 2120 lines of tracing taking a total of just under 0.116 seconds.
vitRegex test tracing.txt (222.4 KB)
Hey the universe didn’t end!
What’s more, I am very clear in the manual to only use the debug/trace version when you are actually debugging some issue, because it is so slow (relatively speaking) - most of the time is spent outputting tracing information rather than getting on with the job at hand.
Anyway I re-did the 50 char torture test without the tracing:
1 0.000000 14400 TestRegex.exe [st][1] ---- recursion test 2 from https://iev.ee/blog/the-quadratic-problem-nobody-fixed/
2 0.001495 14400 TestRegex.exe [st][1] 50 matches found
and this time it took just under 0.0015 secs. Roughly 77 times faster. And that includes putting all 50 matches into the StringTheory results queue.
Anyway I was pretty (well, very) happy with that and it seems to indicate that all the time spent on coding optimisations in VitRegex is paying off (at least in this case - although the log did indicate it had fallen back to “Using standard exhaustive search” so that indicates even the basic exhaustive search without skips and jumps is fast).
Finally, I did notice that he mentions that RE# does not do either capture groups or lazy quantifiers. You can read the article to understand why they are not possible but suffice to say that VitRegex does both 
