search

commonmark / cmark

CommonMark parsing and rendering library and program in C
Other
1.62k stars 539 forks source link

Fix quadratic behavior when parsing inlines #378

Closed nwellnhof closed 3 years ago

nwellnhof commented 3 years ago

The inline parsing code would call cmark_node_append_child to append nodes. This public function has a sanity check which is linear in the depth of the tree. Repeated calls could show quadratic behavior in degenerate trees. Use a special function to append nodes without this check.

Fixes #373. Found by OSS-Fuzz.

jgm commented 3 years ago

Sorry it took me a while to look at this. It looks great. I had one question (inline above). Did you measure the effects of these changes on benchmarks? I would imagine it speeds things up.

nwellnhof commented 3 years ago

I didn't measure anything, but the changes should also speed up parsing real-world documents.

jgm commented 3 years ago

Excellent.

jgm commented 3 years ago

I ran the benchmarks and it does look like we get a small speedup (~2-3%).