100814 2012-10-30 22:19:26 -0700 Region::union on a list of does N^2 copies of Shape vectors 2013-09-04 10:37:01 -0700 1 1 1 Unclassified WebKit Layout and Rendering 528+ (Nightly build) Unspecified Unspecified NEW P2 Normal --- 98800 1 eric webkit-unassigned andersca leviw tonikitoo oldest_to_newest 754965 0 eric 2012-10-30 22:19:26 -0700 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. 755044 1 eric 2012-10-31 01:23:02 -0700 (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.