[Webkit-unassigned] [Bug 100814] New: Region::union on a list of does N^2 copies of Shape vectors
bugzilla-daemon at webkit.org
bugzilla-daemon at webkit.org
Tue Oct 30 22:18:08 PDT 2012
https://bugs.webkit.org/show_bug.cgi?id=100814
Summary: Region::union on a list of does N^2 copies of Shape
vectors
Product: WebKit
Version: 528+ (Nightly build)
Platform: Unspecified
OS/Version: Unspecified
Status: NEW
Severity: Normal
Priority: P2
Component: Layout and Rendering
AssignedTo: webkit-unassigned at lists.webkit.org
ReportedBy: eric at webkit.org
CC: andersca at apple.com
Blocks: 98800
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.
--
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.
More information about the webkit-unassigned
mailing list