Unusually poor performance in current release version

[austrin]

The Oct 21 release version of problemtools seems to have severe performance degradation from the April 22 release, on slow-running scripts.

Concrete examples include the ascendingphoto problem from NWERC 2017 (e.g. case 07-big.in went from 4.7 to 6.0 seconds) even though b281d3f, added between the two versions, claims to improve performance on that specific set.

As an extreme example, I found one script that took ~5 minutes to run on the April 22 release, and more than 3 hours (after which I decided to stop waiting) to run on the Oct 21 release.

[eldering]

@austrin can you provide the specific script and test data that went from ~5 minutes to > 3 hours? That would be helpful in debugging.

[austrin]

OK, here it is: https://gist.github.com/austrin/981690606d9f695d9efb591617b634ac

[eldering]

Ok, I've fixed one issue causing performance degradation since 2018-04-22, but I don't see performance degradation for ascendingphoto. Here's my runtimes for the whole data sets of these problems from NWERC 2018: https://gist.github.com/eldering/5dd61a4f46abc451292dc97725f3ce40
Note the checktestdata without suffix is the current versoin and that I don't have the last two since checktestdata crashes on the large test cases of jugglingtroupe, but that's not a regression.
I'm running this on an Intel CPU G3258 @ 3.20GHz, compiled with gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516.

[TPolzer]

Sidenote: That crash is a nice reminder why RE2 is a good regex implementation.