MarshallOfSound

#53642: perf: build the draggable region by recursive halving

Merged
Created: Sep 6, 2026, 8:27:00 PM
Merged: Sep 6, 2026, 9:21:07 PM
4 comments
Target: main

Description of Change

Follow-up to #53595, adopting the approach from https://crrev.com/c/8360195 (content::DraggableRegionsToSkRegion).

  • #53595 unions each run of consecutive same-kind rects with setRects() and folds the runs in order. That is O(n log n) only while drag/no-drag rects arrive in long runs; when they interleave (a drag card containing a no-drag button, repeated N times) every run is a single rect and the fold is quadratic again.
  • This splits the list in halves, builds each half recursively, and combines them as first.result − second.covered + second.result (a point covered by any rect in the second half is decided by the second half alone). Later rects still win; the region is identical to the original sequential loop (checked on 20k randomized inputs), and the cost is O(n log n) region ops however the kinds interleave.
  • The helper is a verbatim copy of the one in the CL, with a TODO to replace it with a call to content::DraggableRegionsToSkRegion() once that rolls in.

Release Skia, building the region once from 10k rects:

input sequential (pre‑#53595) runs (#53595) halving (this PR)
disjoint drag tiles / 1 drag + 9,999 no‑drag holes 106–114 ms 0.74 ms ~1 ms
strictly alternating drag/no‑drag tiles 1.4 ms
random overlapping, 80% drag / 20% no‑drag 475 ms 202 ms 26 ms

Checklist

  • PR description included
  • npm test passes

Release Notes

Notes: none

Backports

43-x-y
Pending
Waiting for a manual backport
44-x-y
Merged
PR Number
#53648
Merged At
Sep 7, 2026, 1:10:00 AM
Released In
Not yet
Release Date
Not yet
45-x-y
Merged
PR Number
#53649
Merged At
Sep 7, 2026, 1:09:20 AM
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