Bug 100814
| Summary: | Region::union on a list of does N^2 copies of Shape vectors | ||
|---|---|---|---|
| Product: | WebKit | Reporter: | Eric Seidel (no email) <eric> |
| Component: | Layout and Rendering | Assignee: | Nobody <webkit-unassigned> |
| Status: | NEW | ||
| Severity: | Normal | CC: | andersca, leviw, tonikitoo |
| Priority: | P2 | ||
| Version: | 528+ (Nightly build) | ||
| Hardware: | Unspecified | ||
| OS: | Unspecified | ||
| Bug Depends on: | |||
| Bug Blocks: | 98800 | ||
Eric Seidel (no email)
Region::union on a list of does N^2 copies of Shape vectors
Regions are mutable, but their Shapes are not. Each Shape has 2 vectors which are both copied into a new Shape object when two Shapes are combined.
To union a list of Regions into a single Region amounts to copying the contents of the first region's Shape vectors N times! (The second region's shape vectors N-1, times, etc.)
The sum of a list from 1 to N is N(N-1)/2, which is for our purposes is order N^2. :(
Prior to my mitigation in bug 98800, we performed this O(N^2) algorithm every time we did RenderLayerCompositor::computeCompositingRequirements (which is currently on every style recalc!)
This could be solved by making a mutable union which built up a Shape, instead of copying each pair into a new Shape.
I've split this off from bug 98800 so we can land a mitigation for RoboHornet now, and fix the algorithm complexity of Region/Shape combining later.
| Attachments | ||
|---|---|---|
| Add attachment proposed patch, testcase, etc. |
Eric Seidel (no email)
(In reply to comment #0)
> Prior to my mitigation in bug 98800, we performed this O(N^2) algorithm every time we did RenderLayerCompositor::computeCompositingRequirements (which is currently on every style recalc!)
This every-style-recalc behavior is tracked by bug 84393.