Checking individual checkboxes performs fine; it's just the check all that makes it hang.

The problem is the same in "safe mode", so it's not related to a script or gadget I have enabled.

Looks like the problematic line is multiselect.selectItems( isChecked ? multiselect.items : [] );, if isChecked is true.

That calls OO.ui.MultiselectWidget.prototype.selectItemsByData, which calls OO.ui.mixin.GroupElement.prototype.findItemFromData on each item.

Each call of findItemFromData, in turn, iterates through every item in the list again.

So I think the whole thing has O(n^2) complexity (I say this in the hope someone will tell me if I'm wrong, because I don't know that much about software engineering and have never actually tried to use big O notation before 😅).

Lag is noticeable with as low as 200 items.

Change 912402 had a related patch set uploaded (by Neil P. Quinn-WMF; author: Neil P. Quinn-WMF):

[mediawiki/core@master] editwatchlist.js: Use jQuery for performant select-all

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

In T335082#8795040, @nshahquinn-wmf wrote:

Looks like the problematic line is multiselect.selectItems( isChecked ? multiselect.items : [] );, if isChecked is true.

That calls OO.ui.MultiselectWidget.prototype.selectItemsByData, which calls OO.ui.mixin.GroupElement.prototype.findItemFromData on each item.

Each call of findItemFromData, in turn, iterates through every item in the list again.

So I think the whole thing has O(n^2) complexity (I say this in the hope someone will tell me if I'm wrong, because I don't know that much about software engineering and have never actually tried to use big O notation before 😅).

Yep, that's exactly true. But I tried fixing it (fairly easy to do these days by using a Set), and that didn't make the whole operation any faster. It turns out to not be the only problem…

Another thing that happens is: as the code is selecting all of the checkboxes one-by-one, each change causes CheckboxMultiselectInputWidget to update its internal bookkeeping about which values are selected (OO.ui.CheckboxMultiselectInputWidget.prototype.onCheckboxesSelect), and that is also a O(n^2) operation (see code in OO.ui.CheckboxMultiselectInputWidget.prototype.cleanUpValue). So overall, the whole thing is O(n^3)!

[On second thought, it would be quite unusual for a merely quadratic algorithm to start taking forever at 200 items, they tend to fail around 5000, depending on how expensive each operation is. I didn't realize this until I found the issue above.]

I actually wrote all of this code in 2016 in https://gerrit.wikimedia.org/r/c/oojs/ui/+/291708, and definitely cut some corners to get the feature done faster. On the other hand, it took 7 years for anyone to run into an issue, so maybe it wasn't that bad of a tradeoff ;) . At the time we supported browsers where Set is unavailable, so this would have been quite tedious to do properly.

I'll propose a OOUI patch to fix this later this week, but I can't promise when it will be reviewed and released.

Change 912402 merged by jenkins-bot:

[mediawiki/core@master] editwatchlist.js: Use jQuery for performant select-all

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

Change 913969 had a related patch set uploaded (by Bartosz Dziewoński; author: Bartosz Dziewoński):

[oojs/ui@master] CheckboxMultiselectInputWidget: Fix quadratic performance in common methods

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

Change 913970 had a related patch set uploaded (by Bartosz Dziewoński; author: Bartosz Dziewoński):

[oojs/ui@master] CheckboxMultiselectInputWidget: Debounce internal updates to avoid quadratic performance

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

Change 913224 had a related patch set uploaded (by Bartosz Dziewoński; author: Bartosz Dziewoński):

[mediawiki/core@master] Revert "editwatchlist.js: Use jQuery for performant select-all"

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

Test wiki created on Patch demo by Matma Rex using patch(es) linked to this task:
https://patchdemo.wmflabs.org/wikis/5c81a4541f/wiki/Special:EditWatchlist

Also created an OOUI Demos page:
https://patchdemo.wmflabs.org/wikis/5c81a4541f/w/build/ooui/demos

The two patches above fix the problems in OOUI. You can try the demo here: https://patchdemo.wmflabs.org/wikis/5c81a4541f/wiki/Special:EditWatchlist (log in as "Patch Demo" with password "patchdemo1", I set up a watchlist for this user with 5000 entries). It's not exactly pleasant to use, but you can check or uncheck them in less than a second.

(However, you can't actually submit the form if you do – it's hitting some size limit on form submissions, and dropping form fields after the 999th one. Something for another day…)

Change 913969 merged by jenkins-bot:

[oojs/ui@master] CheckboxMultiselectInputWidget: Fix quadratic performance in common methods

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

Change 913970 merged by jenkins-bot:

[oojs/ui@master] CheckboxMultiselectInputWidget: Debounce internal updates to avoid quadratic performance

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

In T335082#8815547, @matmarex wrote:

Yep, that's exactly true. But I tried fixing it (fairly easy to do these days by using a Set), and that didn't make the whole operation any faster. It turns out to not be the only problem…

Another thing that happens is: as the code is selecting all of the checkboxes one-by-one, each change causes CheckboxMultiselectInputWidget to update its internal bookkeeping about which values are selected (OO.ui.CheckboxMultiselectInputWidget.prototype.onCheckboxesSelect), and that is also a O(n^2) operation (see code in OO.ui.CheckboxMultiselectInputWidget.prototype.cleanUpValue). So overall, the whole thing is O(n^3)!

[On second thought, it would be quite unusual for a merely quadratic algorithm to start taking forever at 200 items, they tend to fail around 5000, depending on how expensive each operation is. I didn't realize this until I found the issue above.]

I actually wrote all of this code in 2016 in https://gerrit.wikimedia.org/r/c/oojs/ui/+/291708, and definitely cut some corners to get the feature done faster. On the other hand, it took 7 years for anyone to run into an issue, so maybe it wasn't that bad of a tradeoff ;) . At the time we supported browsers where Set is unavailable, so this would have been quite tedious to do properly.

I'll propose a OOUI patch to fix this later this week, but I can't promise when it will be reviewed and released.

Thank you for explaining all that; it's super interesting!

And thank you for fixing OOUI. I can't +2 the revert of my patch but I'm glad to have it so quickly replaced by a more elegant fix 😊

Change 921070 had a related patch set uploaded (by VolkerE; author: VolkerE):

[mediawiki/core@master] Update OOUI to v0.47.0

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

Change 921070 merged by jenkins-bot:

[mediawiki/core@master] Update OOUI to v0.47.0

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

Test wiki on Patch demo by Matma Rex using patch(es) linked to this task was deleted:

https://patchdemo.wmflabs.org/wikis/5c81a4541f/w/

Change 913224 merged by jenkins-bot:

[mediawiki/core@master] Revert "editwatchlist.js: Use jQuery for performant select-all"

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