Bug 100814 - Region::union on a list of does N^2 copies of Shape vectors
Summary: Region::union on a list of does N^2 copies of Shape vectors
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks: 98800
  Show dependency treegraph
 
Reported: 2012-10-30 22:19 PDT by Eric Seidel (no email)
Modified: 2013-09-04 10:37 PDT (History)
3 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Eric Seidel (no email) 2012-10-30 22:19:26 PDT
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.
Comment 1 Eric Seidel (no email) 2012-10-31 01:23:02 PDT
(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.