#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 (adragcard containing ano-dragbutton, 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 testpasses
Release Notes
Notes: none
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