Quadratic behavior in link reference lookup

mity / md4c

C Markdown parser. Fast. SAX-like interface. Compliant to CommonMark specification.

MIT License

756 stars 138 forks source link

Quadratic behavior in link reference lookup #172

Closed mity closed 2 years ago

mity commented 2 years ago

$ time python -c 'N=10000; print("[x]: /foo\n\n" + "[" * N + "]" * N)' | /md2html > /dev/null
real    0m2.374s
user    0m0.000s
sys     0m0.030s

$ time python -c 'N=20000; print("[x]: /foo\n\n" + "[" * N + "]" * N)' | md2html > /dev/null
real    0m9.440s
user    0m0.015s
sys     0m0.000s

mity commented 2 years ago

This is caused by the fact we do not rule out the stuff with nested [...] as a potential link label soon enough, so we compute hashes and do all the link ref. def. lookup unnecessarily.