match execution time grows exponentially on certain regular expressions, when you increase input length

Steps to reproduce: run the attached test script.

Outcome: Execution time doubles in each round.

I expect match to be faster (like gawk's match in this case).

What version of the product are you using? On what operating system?

$ mawk -W version
mawk 1.3.4 20150503
Copyright 2008-2014,2015, Thomas E. Dickey
Copyright 1991-1996,2014, Michael D. Brennan

random-funcs:       srandom/random
regex-funcs:        internal
compiled limits:
sprintf buffer      8192
maximum-integer     2147483647

$ uname -a
Linux jarnos-OptiPlex-745 3.13.0-59-lowlatency #98-Ubuntu SMP PREEMPT Fri Jul 
24 21:43:07 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

Original issue reported on code.google.com by jarno.il...@gmail.com on 29 Jul 2015 at 9:50

Attachments:

test-mawk-match.sh

ThomasDickey / original-mawk

match execution time grows exponentially on certain regular expressions, when you increase input length #34