Parsing <<<<<<… takes quadratic time

[andersk]

$ time node -e 'require("markdown-it")().render("<".repeat(200000))'
0.36user 0.01system 0:00.36elapsed 103%CPU (0avgtext+0avgdata 55036maxresident)k
0inputs+0outputs (0major+7434minor)pagefaults 0swaps
$ time node -e 'require("markdown-it")().render("<".repeat(400000))'
1.28user 0.02system 0:01.29elapsed 101%CPU (0avgtext+0avgdata 75008maxresident)k
0inputs+0outputs (0major+12473minor)pagefaults 0swaps
$ time node -e 'require("markdown-it")().render("<".repeat(800000))'
5.54user 0.04system 0:05.55elapsed 100%CPU (0avgtext+0avgdata 98892maxresident)k
0inputs+0outputs (0major+19163minor)pagefaults 0swaps
$ time node -e 'require("markdown-it")().render("<".repeat(1600000))'
22.20user 0.06system 0:22.19elapsed 100%CPU (0avgtext+0avgdata 159764maxresident)k
0inputs+0outputs (0major+35116minor)pagefaults 0swaps

[puzrin]

@andersk can i ask you about source of your testing patterns? For example, we ported pathological tests from commonmark, and closed couple of addiional unrepored bugs. But i'd like to plan work somehow, to fix all at once.

PS. Thank you very much for our reports.

[andersk]

All I did was I write a loop over repetitions of strings on a set of interesting characters that finds the slowest inputs. Then I manually verify the asymptotic behavior of good candidates. I’m not sure if I should publish the code, as simple as it is, given that it’s designed to break Markdown libraries and it seems to be annoyingly good at this… 😞 But I’m happy to share it privately.

[puzrin]

@andersk we closed all perf issues. If you have plans for more tests - le me know, i'll postpone publish.