[Webkit-unassigned] [Bug 98800] RoboHornetPro spends ~25% of total test time in WebCore::Region::Shape methods

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=98800





--- Comment #4 from Eric Seidel <eric at webkit.org>  2012-10-11 13:25:48 PST ---
I believe Region::union is simply N^2.

The union operation is effectively just:

union(Region a, Region b) = { return a + b; }
Region r = reduce(union, regions);

Each region has a vector of spans, and each union operation results in a completely new Region object, which we copy the contents of a and b into.  Each time, we're individually copying over each span into the new region.

If I'm doing my math right, that means we're doing at least N * (N-1)/2 span copies! (the second to last spans are copied once, the 3rd twice, etc. to N-1)  Additionally, we're performing N * ln(N) mallocs from resizing the span vectors.

Bad news bears.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.