[Bug libstdc++/78276] New: regex_search is slow

["idrazil at fit dot vutbr.cz" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78276

            Bug ID: 78276
           Summary: regex_search is slow
           Product: gcc
           Version: 6.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: idrazil at fit dot vutbr.cz
  Target Milestone: ---

Created attachment 40006
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=40006&action=edit
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.