https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78276
Tim Shen <timshen at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |timshen at gcc dot gnu.org --- Comment #1 from Tim Shen <timshen at gcc dot gnu.org> --- (In reply to idrazil from comment #0) > Created attachment 40006 [details] > Example with bug > > I tried match this string "<aaaaaaaaaaaaa>\r\n" with regexp > "(?:[^\r\n]*)*<?(aaaaaaaaaaaaa)>?". GCC 4.9 can solve it almost instantly > but at 6.2 (I've also tried 6.1) it takes on my computer more than 5 seconds. > > I've discovered increasing count of letter "a" also increase (probably > exponentially) solving time of regexp. The problem goes away when I've > alternated regexp to "[^\r\n]*<?(aaaaaaaaaaaaa)>?". (In this case the change > is possible but my original code contains more complex regexp with the same > problem) > > Full example is at the attachment. We could have thrown error_complexity here, but I didn't implement that yet. Alternatively, for this particular case, you can pass in regex_constants::__polynomial. It's not in the standard; it's also slower for normal cases, but it prevents pathological cases like this. FYI, I have a talk about different algorithms and runtime efficiency at CppCon: https://www.youtube.com/watch?v=N_rkHzhXueo