Footnotes with strong-emphasis take forever to highlight

[uranusjr]

The following literally takes seconds of near-100% CPU to highlight in the Cocoa demo:

First.[^1] Second.[^2] Third.[^3] Fourth.[^4] Fifth.[^5]

[^1]: A ***B***
[^2]: ***C***
[^3]: ***D***
[^4]: ***E***
[^5]: ***F***

And it gets worse with every *** blocks you have. I observed some curious behaviours:

• Only *** markups matter. If you change any of the above ***s into **, for example, the highlighting feels instant.
• If you take out the A in the first footnote, things will be fine.
• The magnitude of slowdown seems to be related with how many *** blocks there are after the A. Say if you put the A before ***C*** things will improve a bit. But if you then add another footnote like [^6]: ***G*** things will go bad again.

[ali-rantakari]

Does the same issue occur with the peg-markdown compiler?

On 27.6.2014, at 19.03, Tzu-ping Chung notifications@github.com wrote:

This following literally takes seconds of near-100% CPU to highlight in the Cocoa demo:

First.¹ Second.² Third.³ Fourth.⁴ Fifth.⁵

Only *** markups matter. If you change any of the above **s into *, for example, the highlighting feels instant.
If you take out the A in the first footnote, things will be fine.
The magnitude of slowdown seems to be related with how many *** blocks there are after the A. Say if you put the A before *C* things will improve a bit. But if you then add another footnote like [^6]: _G_ things will go bad again.
—
Reply to this email directly or view it on GitHub.

Footnotes

1. A _B_ ↩

2. _C_ ↩

3. _D_ ↩

4. _E_ ↩

5. _F_
   And it gets worse with every *** blocks you have. I also observed some curious behaviours: ↩

[uranusjr]

Just tested the HEAD version of peg-markdown. The text I posted above is processed instantly, but the result is not what I expected. To get footnotes to render correctly I need to put each of them in a separate paragraph (i.e. add an empty line between them). If I use the same corrected input with peg-markdown-highlight the highlighting is also instant. But I would at least expect it not to slow down so much even if the input is not well-formatted.

[ali-rantakari]

I was not able to reproduce this, either via the command-line test program (tester) or via the Cocoa example project — on my (Mavericks) machine, the highlighting is fast:

$ time ./tester testfiles/footnotes-slow.md 
First.[^1] Second.[^2] Third.[^3] Fourth.[^4] Fifth.[^5]

[^1]: A ***B***
[^2]: ***C***
[^3]: ***D***
[^4]: ***E***
[^5]: ***F***


real    0m0.072s
user    0m0.059s
sys 0m0.007s

[ali-rantakari]

I suggest using Time Profiler in Instruments to check where the CPU time is used.

[uranusjr]

Hmm, that slows down pretty quickly on mine (Mavericks, MacBook Air 1.7 GHz i7). The above took 0.1s, and if I add a couple more (7 in total) it takes more than 3 seconds.

Doing a time profiling reveals no particular function causing significant amount of processing, but rather a ton of repeated calls of Inline -> StrongStar -> TwoStarClose -> Inline -> EmphStar -> OneStarClose -> Inline -> StrongStar -> (goes on repeating), resulting a very deep call stack.

I tried a simpler input: ***foo*** ***foo*** ***foo*** ***foo*** ***foo*** ***foo*** ***foo*** and the result is similar. So the problem isn’t really about footnotes, but strong-emphasis causing a very deep call stack and drag the performance down.

Here are traces of the first and second examples. Hope they are useful.

cc -v:

Apple LLVM version 5.1 (clang-503.0.40) (based on LLVM 3.4svn)
Target: x86_64-apple-darwin13.3.0
Thread model: posix

[ali-rantakari]

I took some time to look into this and was able to fix this issue by updating the grammar to match the current state of peg-markdown:

$ time ./old_tester testfiles/footnotes-slow.md >/dev/null

real    0m4.462s
user    0m4.407s
sys 0m0.031s
$
$ time ./tester testfiles/footnotes-slow.md >/dev/null

real    0m0.046s
user    0m0.015s
sys 0m0.011s

Thanks for the excellent bug report. Hopefully “better late than never” applies here.

[uranusjr]

Thank you!! This is still a huge problem in MacDown, and based on the download count, the fix will help probably hundreds of users. 😄