Page MenuHomePhabricator
Create Task
Maniphest T270317

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

Assigned To
thiemowmde
Authored By
thiemowmde
Dec 16 2020, 5:23 PM
Tags
Referenced Files
F34094112: Screenshot from 2021-02-07 08-22-30.png
Feb 7 2021, 7:31 AM
F34094113: Screenshot from 2021-02-07 08-22-26.png
Feb 7 2021, 7:31 AM
F34011124: Screenshot from 2021-01-21 16-53-05.png
Jan 21 2021, 5:06 PM
F34011125: Screenshot from 2021-01-21 16-53-25.png
Jan 21 2021, 5:06 PM
F33996724: Screenshot from 2021-01-12 14-50-13_with.png
Jan 12 2021, 3:56 PM
F33996725: Screenshot from 2021-01-12 15-10-29.png
Jan 12 2021, 3:56 PM
F33990710: Screenshot from 2021-01-08 13-37-27.png
Jan 8 2021, 12:43 PM
F33947295: Screenshot from 2020-12-16 18-10-59.png
Dec 16 2020, 5:23 PM
View All 9 Files
Subscribers
Aklapper
Lena_WMDE
lilients_WMDE
thiemowmde
WMDE-Fisch

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.

Screenshot from 2020-12-16 18-16-38.png (298×1 px, 43 KB)

Screenshot from 2020-12-16 18-10-59.png (305×868 px, 54 KB)

Details

Show related patches Customize query in gerrit

Related Objects
Search...

Event Timeline

thiemowmde created this task.Dec 16 2020, 5:23 PM
Restricted Application added a project: Community-Tech. · View Herald TranscriptDec 16 2020, 5:23 PM
Restricted Application added a subscriber: Aklapper. · View Herald Transcript
thiemowmde added a subtask: T261857: Implement bracket matching in CodeMirror behind a feature flag.Dec 16 2020, 5:24 PM
thiemowmde updated the task description. (Show Details)Jan 5 2021, 4:24 PM
Lena_WMDE closed subtask T261857: Implement bracket matching in CodeMirror behind a feature flag as Resolved.Jan 6 2021, 9:32 AM
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 moved this task from Backlog to Ready for pickup on the WMDE-Templates-FocusArea board.Jan 6 2021, 9:43 AM
Lena_WMDE added a project: WMDE-QWERTY-Sprint-2021-01-06.Jan 6 2021, 9:46 AM
Lena_WMDE set the point value for this task to 3.

Time-boxed to 3 story points

WMDE-Fisch moved this task from Ready for pickup to In sprint on the WMDE-Templates-FocusArea board.Jan 6 2021, 9:46 AM
WMDE-Fisch added a comment.Jan 7 2021, 10:22 AM

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

WMDE-Fisch added a comment.Jan 7 2021, 10:28 AM

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.

thiemowmde added a comment.Jan 7 2021, 10:49 AM

[…] 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.

thiemowmde claimed this task.Jan 8 2021, 9:56 AM
thiemowmde moved this task from Sprint Backlog to Doing on the WMDE-QWERTY-Sprint-2021-01-06 board.
gerritbot added a comment.Jan 8 2021, 10:41 AM

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

gerritbot added a project: Patch-For-Review.Jan 8 2021, 10:41 AM

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

gerritbot added a comment.Jan 8 2021, 12:30 PM

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

thiemowmde moved this task from Doing to Review on the WMDE-QWERTY-Sprint-2021-01-06 board.Jan 8 2021, 12:43 PM

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%.

Screenshot from 2021-01-08 13-37-27.png (392×1 px, 74 KB)

gerritbot added a comment.Jan 12 2021, 10:54 AM

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

gerritbot added a comment.Jan 12 2021, 11:07 AM

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

gerritbot added a comment.Jan 12 2021, 11:48 AM

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

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

gerritbot added a comment.Jan 12 2021, 11:48 AM

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

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

gerritbot added a comment.Jan 12 2021, 11:55 AM

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

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

ReleaseTaggerBot added a project: MW-1.36-notes (1.36.0-wmf.27; 2021-01-19).Jan 12 2021, 12:00 PM
Maintenance_bot removed a project: Patch-For-Review.Jan 12 2021, 12:10 PM
gerritbot added a comment.Jan 12 2021, 3:12 PM

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

gerritbot added a project: Patch-For-Review.Jan 12 2021, 3:12 PM
thiemowmde added a comment.Jan 12 2021, 3:56 PM

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

Screenshot from 2021-01-12 14-50-13_with.png (385×635 px, 40 KB)
Screenshot from 2021-01-12 15-10-29.png (390×893 px, 41 KB)

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.

thiemowmde mentioned this in T190983: Poor performances of syntax highlighting feature at old WikiEditors in IE11.Jan 12 2021, 4:10 PM
thiemowmde mentioned this in T184857: Problems with editing huge pages.
thiemowmde mentioned this in T197502: Syntax Highlighter consumes insane amounts of CPU on large texts or on mobile phone..
thiemowmde mentioned this in T269096: Upstream or fork bracket matching for CodeMirror.Jan 14 2021, 8:48 AM
gerritbot added a comment.Jan 14 2021, 10:15 AM

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

gerritbot added a comment.Jan 14 2021, 10:50 AM

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

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

gerritbot added a comment.Jan 14 2021, 11:22 AM

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

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

Maintenance_bot removed a project: Patch-For-Review.Jan 14 2021, 12:10 PM
WMDE-Fisch moved this task from Review to Demo on the WMDE-QWERTY-Sprint-2021-01-06 board.Jan 18 2021, 10:42 AM
thiemowmde moved this task from Demo to Doing on the WMDE-QWERTY-Sprint-2021-01-06 board.Jan 19 2021, 9:11 AM
thiemowmde updated the task description. (Show Details)Jan 19 2021, 9:17 AM
gerritbot added a comment.Jan 19 2021, 2:12 PM

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

gerritbot added a project: Patch-For-Review.Jan 19 2021, 2:12 PM
gerritbot added a comment.Jan 19 2021, 2:30 PM

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

thiemowmde updated the task description. (Show Details)Jan 19 2021, 2:30 PM
thiemowmde moved this task from Doing to Review on the WMDE-QWERTY-Sprint-2021-01-06 board.
Lena_WMDE changed the point value for this task from 3 to 2.Jan 20 2021, 9:29 AM
Lena_WMDE edited projects, added WMDE-TechWish (Sprint-2021-01-20); removed WMDE-TechWish.
Tobi_WMDE_SW moved this task from Sprint Backlog to Review on the WMDE-TechWish (Sprint-2021-01-20) board.Jan 20 2021, 9:31 AM
gerritbot added a comment.Jan 20 2021, 10:03 AM

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

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

gerritbot added a comment.Jan 20 2021, 10:06 AM

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

ReleaseTaggerBot edited projects, added MW-1.36-notes (1.36.0-wmf.28; 2021-01-26); removed MW-1.36-notes (1.36.0-wmf.27; 2021-01-19).Jan 20 2021, 11:00 AM
WMDE-Fisch added a comment.Jan 21 2021, 11:12 AM

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

WMDE-Fisch mentioned this in T272454: Manual QA of bracket matching.Jan 21 2021, 11:17 AM
thiemowmde added a comment.Jan 21 2021, 5:06 PM

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:

Screenshot from 2021-01-21 16-53-05.png (272×1 px, 41 KB)
Screenshot from 2021-01-21 16-53-25.png (247×1 px, 32 KB)

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.

gerritbot added a comment.Jan 25 2021, 3:09 PM

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

gerritbot added a comment.Jan 27 2021, 8:53 AM

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

gerritbot added a comment.Jan 27 2021, 8:53 AM

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

gerritbot added a comment.Jan 27 2021, 9:07 AM

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

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

ReleaseTaggerBot edited projects, added MW-1.36-notes (1.36.0-wmf.29; 2021-02-02); removed MW-1.36-notes (1.36.0-wmf.28; 2021-01-26).Jan 27 2021, 10:00 AM
gerritbot added a comment.Jan 27 2021, 12:09 PM

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

gerritbot added a comment.Jan 27 2021, 12:10 PM

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

Stashbot added a comment.Jan 27 2021, 12:19 PM

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)

Stashbot added a comment.Jan 27 2021, 12:20 PM

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)

WMDE-Fisch moved this task from Review to Demo on the WMDE-TechWish (Sprint-2021-01-20) board.Jan 27 2021, 12:45 PM
WMDE-Fisch removed a project: Patch-For-Review.
ReleaseTaggerBot edited projects, added MW-1.36-notes (1.36.0-wmf.28; 2021-01-26); removed MW-1.36-notes (1.36.0-wmf.29; 2021-02-02).Jan 27 2021, 1:00 PM
Lena_WMDE closed this task as Resolved.Feb 2 2021, 9:15 AM
Lena_WMDE moved this task from Demo to Done on the WMDE-TechWish (Sprint-2021-01-20) board.
gerritbot added a comment.Feb 5 2021, 3:20 PM

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

gerritbot added a project: Patch-For-Review.Feb 5 2021, 3:20 PM
thiemowmde added a comment.Feb 7 2021, 7:31 AM

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

Screenshot from 2021-02-07 08-22-26.png (397×1 px, 46 KB)

Screenshot from 2021-02-07 08-22-30.png (400×628 px, 38 KB)

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

gerritbot added a comment.Feb 8 2021, 11:15 AM

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

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

ReleaseTaggerBot edited projects, added MW-1.36-notes (1.36.0-wmf.30; 2021-02-09); removed MW-1.36-notes (1.36.0-wmf.28; 2021-01-26).Feb 8 2021, 12:00 PM
thiemowmde mentioned this in T274369: Check if we can get rid of the 5000 characters limit.Feb 10 2021, 2:32 PM
Izno moved this task from Backlog to Done on the MediaWiki-extensions-CodeMirror board.Aug 19 2021, 7:07 PM
thiemowmde mentioned this in T288161: Enable CodeMirror's Syntax Highlighting on English Wikipedia by default.Aug 26 2021, 10:02 AM
Content licensed under Creative Commons Attribution-ShareAlike (CC BY-SA) 4.0 unless otherwise noted; code licensed under GNU General Public License (GPL) 2.0 or later and other open source licenses. By using this site, you agree to the Terms of Use, Privacy Policy, and Code of Conduct. · Wikimedia Foundation · Privacy Policy · Code of Conduct · Terms of Use · Disclaimer · CC-BY-SA · GPL