extremely poor performance on certain markdown file

[gerner]

This particular markdown takes a long time (21 seconds on my laptop) to parse:
https://github.com/date-fns/date-fns/blob/a9fc0c7b715883349555bfb94daa1059430eda52/src/locale/en-US/snapshot.md

$ time pygmentize -f terminal -l md -o /dev/null /tmp/snapshot.md

real    0m21.318s
user    0m21.306s
sys     0m0.012s

I've seen slow-ish parsing performance on markdown with tables before, however I'm not certain it's tables that's causing the issue.

[gerner]

I do see Error tokens showing up for '\n' on its own line which I think is because the rule here doesn't match a newline:

https://github.com/pygments/pygments/blob/master/pygments/lexers/markup.py#L601

That seems like a separate issue. If I add a rule to match r'\n' (most) of the errors go away, but that doesn't speed up processing any.

[gerner]

I think tables is a red herring. I pulled out the table rules and performance didn't change.

However, this rule looks expensive:

# strikethrough
(r'([^~]*)(~~[^~]+~~)', bygroups(Text, Generic.Deleted)),

I don't know why, but if I comment it out the file is processed in 400ms down from 21s. Note that this file doesn't have the character "~" anywhere in it.

it looks like the leading ([^~]*) group is the culprit here. changing the rule to this gets the same improvement in performance (400ms down from 21s):

# strikethrough
(r'(~~[^~]+~~)', bygroups(Generic.Deleted)),

I don't think we need that since there's already a catch all single character rule that will eat up text characters that don't match.

Also, why the heavy use of bygroups throughout?

[gerner]

Note, if I change the rule as suggested above the output of pygmentize doesn't change and all test cases still pass. It just happens in 400ms instead of 21s.

[gerner]

This is fixed by #1623