search

mity / md4c

C Markdown parser. Fast. SAX-like interface. Compliant to CommonMark specification.
MIT License
759 stars 140 forks source link

Parsing <><><><><><>… takes quadratic time #57

Closed andersk closed 5 years ago

andersk commented 5 years ago 
$ python -c 'print("<>" * 10000)' | time md2html > /dev/null
1.41user 0.00system 0:01.45elapsed 96%CPU (0avgtext+0avgdata 1968maxresident)k
0inputs+0outputs (0major+229minor)pagefaults 0swaps
$ python -c 'print("<>" * 20000)' | time md2html > /dev/null
4.80user 0.00system 0:04.84elapsed 99%CPU (0avgtext+0avgdata 2608maxresident)k
0inputs+0outputs (0major+365minor)pagefaults 0swaps
$ python -c 'print("<>" * 40000)' | time md2html > /dev/null
19.52user 0.00system 0:19.65elapsed 99%CPU (0avgtext+0avgdata 3528maxresident)k
0inputs+0outputs (0major+640minor)pagefaults 0swaps
andersk commented 5 years ago

Another quadratic case:

$ python -c 'print("\\``" * 20000)' | time md2html > /dev/null
0.81user 0.00system 0:00.85elapsed 95%CPU (0avgtext+0avgdata 2480maxresident)k
0inputs+0outputs (0major+333minor)pagefaults 0swaps
$ python -c 'print("\\``" * 40000)' | time md2html > /dev/null
3.70user 0.00system 0:03.76elapsed 98%CPU (0avgtext+0avgdata 3240maxresident)k
0inputs+0outputs (0major+551minor)pagefaults 0swaps
$ python -c 'print("\\``" * 80000)' | time md2html > /dev/null
15.23user 0.00system 0:15.35elapsed 99%CPU (0avgtext+0avgdata 5008maxresident)k
0inputs+0outputs (0major+991minor)pagefaults 0swaps
andersk commented 5 years ago

And another:

$ python -c 'print("[ (](" * 20000)' | time md2html > /dev/null
0.75user 0.00system 0:00.76elapsed 97%CPU (0avgtext+0avgdata 3440maxresident)k
0inputs+0outputs (0major+550minor)pagefaults 0swaps
$ python -c 'print("[ (](" * 40000)' | time md2html > /dev/null
2.96user 0.00system 0:03.00elapsed 98%CPU (0avgtext+0avgdata 4956maxresident)k
0inputs+0outputs (0major+989minor)pagefaults 0swaps
$ python -c 'print("[ (](" * 80000)' | time md2html > /dev/null
12.22user 0.00system 0:12.28elapsed 99%CPU (0avgtext+0avgdata 8568maxresident)k
0inputs+0outputs (0major+1867minor)pagefaults 0swaps
mity commented 5 years ago

Ok. Thanks for reporting them.

I'll open new bugs for each of them and close this, as they are likely not caused by a single bug, so we can track them separately.