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

Reply via email to