Reduce number of vector buffer reallocs in Regions::unite .

Source/platform/geometry/Region.cpp

Index: Source/platform/geometry/Region.cpp
diff --git a/Source/platform/geometry/Region.cpp b/Source/platform/geometry/Region.cpp
index e755a8b11680dd3f5ecb5ff72de35b373958d9a2..addc038b0a806db8e518573d682ebb5e72f399f4 100644
--- a/Source/platform/geometry/Region.cpp
+++ b/Source/platform/geometry/Region.cpp
@@ -233,6 +233,28 @@ Region::Shape::Shape(const IntRect& rect)
     appendSpan(rect.maxY());
 }
 
+Region::Shape::Shape(size_t segmentsCapacity, size_t spansCapacity)
+{
+    if (segmentsCapacity > m_segments.capacity()) {
+        segmentsCapacity = (segmentsCapacity + segmentsMask) & ~segmentsMask;
+        m_segments.reserveCapacity(segmentsCapacity);
+    }
+
+    if (spansCapacity > m_spans.capacity()) {
+        spansCapacity = (spansCapacity + spansMask) & ~spansMask;
+        m_spans.reserveCapacity(spansCapacity);
+    }
+}
+
+void Region::Shape::trimCapacities()

[danakj, 2014/04/09 18:39:51]

Methods in the same order as their declarations in the .h

[ostap, 2014/04/09 22:45:43]

It seems that all other methods are not in the same order in Regions.cpp , but I
moved trimCapacities() after compareShapes() as it in .h .

+{
+    if (m_segments.size() > segmentsDefaultCapacity && m_segments.capacity() > m_segments.size() * 2)
+        m_segments.shrinkToFit();

[danakj, 2014/04/09 18:39:51]

I feel like this is kinda unfortunate, in that you make it very likely that the
next operation on the region is going to require a realloc/memcpy. Also the *2
seems like it's leaking out of the Vector implementation here.

It'd be really nice if something like Vector::shrinkCapacity() was public, or
maybe a shrinkToReasonableCapacity() or something that would take the *2 into
account. Is there a Vector owner who can approve/disapprove of such an idea?

[ostap, 2014/04/09 22:45:43]

Region always allocate new buffers for operation. They never do it in place. I
just want to limit number of reallocs if unused buffer tail is reasonably small.
Also, *2 is taken from vector, but it used only if there is also other ratio
1.25 (Vector::expandCapacity). Don't know what is better here - do less reallocs
or save a bit more RAM.
Yes, shrinkToReasonableCapacity() would be great!

[danakj, 2014/04/15 20:15:43]

Wanna add that to the CL and we'll see what OWNERs have to say?

+
+    if (m_spans.size() > spansDefaultCapacity && m_spans.capacity() > m_spans.size() * 2)
+        m_spans.shrinkToFit();
+}
+
 void Region::Shape::appendSpan(int y)
 {
     m_spans.append(Span(y, m_segments.size()));
@@ -393,7 +415,9 @@ Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh
     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
 
-    Shape result;
+    size_t segmentsCapacity = shape1.segmentsSize() + shape2.segmentsSize();
+    size_t spansCapacity = shape1.spansSize() + shape2.spansSize();
+    Shape result(segmentsCapacity, spansCapacity);
     if (Operation::trySimpleOperation(shape1, shape2, result))
         return result;
 
@@ -409,6 +433,8 @@ Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh
     SegmentIterator segments2 = 0;
     SegmentIterator segments2End = 0;
 
+    Vector<int, segmentsDefaultCapacity> segments;

[danakj, 2014/04/09 18:39:51]

would it improve anything further in your benchmark to use the
max(shape1.segmentsSize(), shape2.segmentsSize()) here?

[ostap, 2014/04/09 22:45:43]

No, no change at all.
But this benchmark is very special case that emulates what happens on
http://people.mozilla.org/~jorendorff/es6-draft.html with sticky enabled. It
just adds non-intersecting rects to the existing shape and this "segments"
vector never grows above default capacity.
I think it could help for the case when complex shapes get joined. Since it
doesn't make things slower in my benchmark, I just added it because it looks
reasonable.

+
     // Iterate over all spans.
     while (spans1 != spans1End && spans2 != spans2End) {
         int y = 0;
@@ -432,11 +458,12 @@ Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh
         int flag = 0;
         int oldFlag = 0;
 
+        // clear vector without dropping capacity

[danakj, 2014/04/09 18:39:51]

nit: proper sentence (capitalized, with period at the end)

[ostap, 2014/04/09 22:45:43]

Done.

+        segments.resize(0);

[danakj, 2014/04/09 18:39:51]

keep this in the same position? (below s1,s2 assignments)

[ostap, 2014/04/09 22:45:43]

Done.

+
         SegmentIterator s1 = segments1;
         SegmentIterator s2 = segments2;
 
-        Vector<int, 32> segments;
-
         // Now iterate over the segments in each span and construct a new vector of segments.
         while (s1 != segments1End && s2 != segments2End) {
             int test = *s1 - *s2;
@@ -476,6 +503,9 @@ Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh
     else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
         result.appendSpans(shape2, spans2, spans2End);
 
+    // Trim excess capacities if necessary.

[danakj, 2014/04/09 18:39:51]

Prefer not to add comments that just repeat the name of the method more or less
:) If you feel any part of this comment is adding value beyond the method name,
can you just add it to the trimCapacities() method name?

[ostap, 2014/04/09 22:45:43]

Done.

+    result.trimCapacities();
+
     return result;
 }