https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #22 from Hans Åberg <haberg-1 at telia dot com> --- (In reply to Tim Shen from comment #16) > ...I meant to observe whether the example triggers a O(k^2) behavior. It > should be less than quadratic. ... > Here is the updated example, to re-arrange the expression to a tree, not a > chain of "|" operators. The matching itself that I do is linear O(k): I used a version of your example for my program, timing the part in question for various values, dividing with N and N^2, where N is the difference of the input numbers, making it easy to see if it is O(k) or O(k^2). However, in your example, the DFA lexing is quadratic, probably because I use unordered_set objects that here gets size proportional to N. Thus this ought to be optimized. So you might check if that might be an issue in the C++ library.
