Performance issue when rendering a lot of space

[krasnoukhov]

Here's a pretty comprehensive example:

note = "1"+" "*20000+"2"
Benchmark.measure { Kramdown::Document.new(note) }.real

This takes around 3 seconds on my machine. A DOS vulnerability potentially?

[gettalong]

Thanks for reporting and the test. The culprit is the setext header parser, will have to investigate a bit more why its regexp is slow.

[gettalong]

The problem exists not only for the setext header parser but at least also for the atx header parser, i.e. these two regexp have bad behaviour when used on very long lines:

SETEXT_HEADER_START = /^(#{OPT_SPACE}[^ \t].*?)#{HEADER_ID}[ \t]*?\n(-|=)+\s*?\n/
ATX_HEADER_MATCH = /^(\#{1,6})(.+?(?:\\#)?)\s*?#*#{HEADER_ID}\s*?\n/

I have tried a few things but haven't yet come up with a viable solution.

[krasnoukhov]

I don't have much experience with optimizing the regexes either. Can't put my finger on what's slow

[gettalong]

When removing everything after the first occurence of \n in each regexp, they get fast. So I guess that the regexp has to backtrack much more because of them. However, I haven't come across a solution yet.

[glebm]

Some of the instances of *? are unnecessary, e.g. \s*?\n can be replaced with [ \t\r\f\v]*\n in both regexes (see https://ruby-doc.org/core-2.5.1/Regexp.html#class-Regexp-label-Character+Classes).

IIRC, *? can be expensive. I am not completely sure about this though.

[gettalong]

Thanks but I have already tried that. And also changing lazy to possessive quantifiers or vice versa. Didn't find a combination that was fast and didn't break the tests...

[glebm]

Splitting the parsing into two regexes seems to work: #509 Seemed to work but really just worked around the previous benchmark.

Here are the benchmarks that take the parsing further:

"setext":

ruby -rbenchmark -Ilib -rkramdown -e 'p Benchmark.measure{Kramdown::Document.new("1#{" "*20000}2\n==\n")}'

"atx":

ruby -rbenchmark -Ilib -rkramdown -e 'p Benchmark.measure{Kramdown::Document.new("## 1#{" "*20000}2")}'

Update: Parsing semi-manually seems to work: #513