#53595: perf: build the draggable region in O(n log n) instead of O(n²)
Merged
Created: Sep 5, 2026, 3:08:46 PM
Merged: Sep 5, 2026, 4:05:34 PM
5 comments
Target: main
Description of Change
DraggableRegionsToSkRegion (browser UI thread, run on every DraggableRegionsChanged from the renderer) applied each rect with its own SkRegion::op(). Each op is linear in the region built so far, so N non‑adjacent app-region rects cost O(N²): a page with a few thousand draggable tiles stalls the whole app for 100 ms–seconds every time layout moves them.
- Union each run of consecutive same‑kind rects with
SkRegion::setRects()(divide‑and‑conquer) and fold the runs in document order. Later rects still win over earlier ones, so the result is identical to before; checked against the old loop on 20k randomized inputs (mixed drag/no‑drag order, empty and negative rects) with zero differences. - Release‑Skia timings for one update, disjoint 18×18 tiles / one drag rect with N‑1 no‑drag holes:
| rects | before | after |
|---|---|---|
| 1,000 | 1.1 ms | 0.07 ms |
| 10,000 | 106–114 ms | 0.74 ms |
| 30,000 | 0.94–1.04 s | 2.5 ms |
- End to end (frameless window, 40 layouts that each shift 10k regions): main‑process max stall 2.6 s → no gap over 9 ms. Heavily interleaved drag/no‑drag sequences fall back toward the old cost since order has to be preserved, but never worse than before.
Checklist
- PR description included
-
npm testpasses
Release Notes
Notes: Fixed the app becoming unresponsive when a page has a very large number of app-region draggable elements.
Backports
Semver Impact
Major
Breaking changes
Minor
New features
Patch
Bug fixes
None
Docs, tests, etc.
Semantic Versioning helps users understand the impact of updates:
- Major (X.y.z): Breaking changes that may require code modifications
- Minor (x.Y.z): New features that maintain backward compatibility
- Patch (x.y.Z): Bug fixes that don't change the API
- None: Changes that don't affect using facing parts of Electron