Page MenuHomePhabricator

Optimization and limits for bracket matching
Closed, ResolvedPublic2 Estimated Story Points

Description

Via T261857: Implement bracket matching in CodeMirror behind a feature flag we already merged all of the customizations we made to the upstream addon, notably this commit. While the quality of this code isn't bad, it was created as proof-of-concept code and never fully finished:

Here are some flame graphs for wikitexts with varying complexity. While the matchbrackets code is not an obvious issue, it's not free either.

Related Objects

Event Timeline

Restricted Application added a subscriber: Aklapper. · View Herald Transcript
awight renamed this task from Finalize matchbrackets addon proof-of-concept customizations to Optimization and limits for bracket matching.Jan 6 2021, 9:42 AM
Lena_WMDE set the point value for this task to 3.

Time-boxed to 3 story points

Just briefly looked into the code and one micro optimization would be using [pos] instead of .charAt( pos ) at several places to get the char from the position in the string. It performs slightly faster and is still compatible to all relevant browsers.

See https://stackoverflow.com/questions/5943726/string-charatx-or-stringx/5943807#5943807

There are also some FIXMEs if there's a better method to find the (next) position of a char in a string than looping through the chars. AFAIK there is not.

[…] one micro optimization would be using [pos] instead of .charAt( pos ) at several places […]

I honestly don't think this is a relevant performance bottleneck. What concerns me the most is that the new code does not respect the existing limits.

Change 655034 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Add documentation for matchbrackets costomizations

https://gerrit.wikimedia.org/r/655034

Change 655035 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Update matchbrackets addon to most recent version

https://gerrit.wikimedia.org/r/655035

Change 655046 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Make bracket matching respect all limits

https://gerrit.wikimedia.org/r/655046

I carefully reviewed as well as profiled the new code we introduced. I could not find a bottleneck. I was a little concerned because we execute CodeMirror.getLine() in a loop, but this is a cheap array index access. charAt() is not an issue either (note the existing code already uses charAt() in many places). The runtime of the new code is 0.16ms of a total runtime of 23ms. That's about 0.5%.

Change 655631 had a related patch set uploaded (by WMDE-Fisch; owner: WMDE-Fisch):
[mediawiki/extensions/CodeMirror@master] Enable bracket matching addon by defining the addons options

https://gerrit.wikimedia.org/r/655631

Change 655631 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Enable bracket matching addon by defining the addons options

https://gerrit.wikimedia.org/r/655631

Change 655034 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Add documentation for matchbrackets costomizations

https://gerrit.wikimedia.org/r/655034

Change 655035 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Update matchbrackets addon to most recent version

https://gerrit.wikimedia.org/r/655035

Change 655046 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Make bracket matching respect all limits

https://gerrit.wikimedia.org/r/655046

Change 655689 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Fix performance bottleneck in mediawiki syntax highlighter

https://gerrit.wikimedia.org/r/655689

These are the relevant flame graphs for the performance fix in gerrit:655689, before and after:

This is when I edit a very long line. The keydown event is triggered when I change the text, and the entire syntax highlighting needs to be redone. It changes from 220ms to 17ms. The flame graph looks much better. You want many sharp spikes (= many small pieces of fast code), but no long plateaus (= slow functions). The bad graph shows an inLink() function, which is part of the mediawiki syntax highlighter. It calls StringStream.match(), a class that's part of CodeMirror. And that's where the flame graph always ends. Why?

Turns out the mediawiki syntax highlighter executes billions of very expensive "find a match anywhere in a long string" regular expressions, but throws every result away that's not at the start of the string. When we limit these regular expressions to look only at the start of the string, they return much, much earlier. The result is the same.

Change 656118 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Fix minor code style issues in matchbrackets addon

https://gerrit.wikimedia.org/r/656118

Change 656118 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Fix minor code style issues in matchbrackets addon

https://gerrit.wikimedia.org/r/656118

Change 655689 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Fix performance bottleneck in mediawiki syntax highlighter

https://gerrit.wikimedia.org/r/655689

Change 657088 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Lower maxHighlightLineLength limit to 5000

https://gerrit.wikimedia.org/r/657088

Change 657096 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Improve matchbrackets performance when moving the cursor

https://gerrit.wikimedia.org/r/657096

Lena_WMDE changed the point value for this task from 3 to 2.Jan 20 2021, 9:29 AM

Change 657088 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Lower maxHighlightLineLength limit to 5000

https://gerrit.wikimedia.org/r/657088

Change 657308 had a related patch set uploaded (by WMDE-Fisch; owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@wmf/1.36.0-wmf.27] Lower maxHighlightLineLength limit to 5000

https://gerrit.wikimedia.org/r/657308

For the record:

I tested CodeMirror and bracket matching with longer complex articles[1] or paragraphs including something like 600x [[link]]. I tested with bracket matching enabled and disabled. I tested with my machine and slower virtual machines on different browsers. Mainly current FF, Chrome, Edge and IE11.

My main insight is, that the bracket matching code itself seems to be totally fine performance wise. I got the worst performance in general with IE11 where typing a few letters hangs for a second until the letter appears. But this is also happening with bracket matching disabled. The same goes for the article[1]. Performance might suffer, even on a good machine, but that's independent of the bracket matching code.

[1] https://en.wikipedia.beta.wmflabs.org/wiki/Barack_Obama

Wonderful, thanks! I can confirm this.

The only additional bottleneck I found is when holding down a cursor key. This can feel laggy. The two brackets are recalculated from scratch every time the cursor moves. While this calculation alone is fast, it changes the DOM and triggers heavy redraws – even if nothing visually changes! https://gerrit.wikimedia.org/r/657096 dramatically improves this in all browsers. Here is the same flame graph before and after the patch:

This is when the cursor is in a 5000 character line with many links, and I hold a cursor key. You can see that the vast majority of heavy redraws is gone. A redraw happens only when the cursor crosses a bracket and something else needs to be highlighted. In other words: The thin spikes (each is ~5ms) contain the entirety of what the matchbrackets addon does. The addon alone is fast.

Such an improvement can't be made in edit mode because this requires redraws anyway.

The effect of the previous 10,000 → 5,000 patch is harder to explain. It does not make any difference when editing. Editing such long lines is painfully slow no matter what, with or without bracket matching. But it makes a difference when using the cursor keys. When I hold a cursor key in a line with 10,000 characters, the fat keydown events in the flame graphs above are ~60ms. This piles up and the browser stops doing redraws, i.e. I can't even see what's happening. In a line with only 5,000 characters they are ~30ms. Still laggy, but better. The main effect of the change is that navigating lines with >5000 characters becomes blazing fast, no matter if the additional patch https://gerrit.wikimedia.org/r/657096 is in place or not.

Both patches together should make the thing usable in pretty much all situations.

Change 657308 abandoned by Awight:
[mediawiki/extensions/CodeMirror@wmf/1.36.0-wmf.27] Lower maxHighlightLineLength limit to 5000

Reason:
1 backporting no longer necessary, the master patch will be included in this week's train.

https://gerrit.wikimedia.org/r/657308

Change 658814 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@wmf/1.36.0-wmf.27] Improve matchbrackets performance when moving the cursor

https://gerrit.wikimedia.org/r/658814

Change 658815 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@wmf/1.36.0-wmf.28] Improve matchbrackets performance when moving the cursor

https://gerrit.wikimedia.org/r/658815

Change 657096 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Improve matchbrackets performance when moving the cursor

https://gerrit.wikimedia.org/r/657096

Change 658814 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@wmf/1.36.0-wmf.27] Improve matchbrackets performance when moving the cursor

https://gerrit.wikimedia.org/r/658814

Change 658815 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@wmf/1.36.0-wmf.28] Improve matchbrackets performance when moving the cursor

https://gerrit.wikimedia.org/r/658815

Mentioned in SAL (#wikimedia-operations) [2021-01-27T12:19:11Z] <awight@deploy1001> Synchronized php-1.36.0-wmf.28/extensions/CodeMirror: Backport: [[gerrit:658815|Improve matchbrackets performance when moving the cursor (T270317)]] (duration: 01m 14s)

Mentioned in SAL (#wikimedia-operations) [2021-01-27T12:20:42Z] <awight@deploy1001> Synchronized php-1.36.0-wmf.27/extensions/CodeMirror: Backport: [[gerrit:658814|Improve matchbrackets performance when moving the cursor (T270317)]] (duration: 01m 06s)

Lena_WMDE moved this task from Demo to Done on the WMDE-TechWish (Sprint-2021-01-20) board.

Change 661948 had a related patch set uploaded (by Thiemo Kreuz (WMDE); owner: Thiemo Kreuz (WMDE)):
[mediawiki/extensions/CodeMirror@master] Fix remaining bottleneck in wikitext syntax highlighter

https://gerrit.wikimedia.org/r/661948

These flame graphs demonstrate the effect of patch https://gerrit.wikimedia.org/r/661948:

I highlighted the relevant piece. 15ms before, 4ms after. That's a lot when you consider this happens every time you press a key.

Change 661948 merged by jenkins-bot:
[mediawiki/extensions/CodeMirror@master] Fix remaining bottleneck in wikitext syntax highlighter

https://gerrit.wikimedia.org/r/661948