MarshallOfSound

#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 test passes

Release Notes

Notes: Fixed the app becoming unresponsive when a page has a very large number of app-region draggable elements.

Backports

43-x-y
In-flight
PR Number
#
Waiting to be merged
44-x-y
Merged
PR Number
#53597
Merged At
Sep 5, 2026, 4:56:58 PM
Released In
Not yet
Release Date
Not yet
45-x-y
Merged
PR Number
#53596
Merged At
Sep 5, 2026, 5:00:43 PM
Released In
Not yet
Release Date
Not yet

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