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

Source/platform/geometry/Region.cpp

 /*
  * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 189 matching lines @@
     }
 
     if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutsideB(result))
         return result;
     if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutsideA(result))
         return result;
 
     return result;
 }
 
+void Region::Shape::trimCapacities()
+{
+    m_segments.shrinkToReasonableCapacity();
+    m_spans.shrinkToReasonableCapacity();
+}
+
 struct Region::Shape::CompareContainsOperation {
     const static bool defaultResult = true;
     inline static bool aOutsideB(bool& /* result */) { return false; }
     inline static bool bOutsideA(bool& result) { result = false; return true; }
     inline static bool aOverlapsB(bool& /* result */) { return false; }
 };
 
 struct Region::Shape::CompareIntersectsOperation {
     const static bool defaultResult = false;
     inline static bool aOutsideB(bool& /* result */) { return false; }
     inline static bool bOutsideA(bool& /* result */) { return false; }
     inline static bool aOverlapsB(bool& result) { result = true; return true; }
 };
 
 Region::Shape::Shape()
 {
 }
 
 Region::Shape::Shape(const IntRect& rect)
 {
     appendSpan(rect.y());
     appendSegment(rect.x());
     appendSegment(rect.maxX());
     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::appendSpan(int y)
 {
     m_spans.append(Span(y, m_segments.size()));
 }
 
 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
 {
     if (m_spans.isEmpty())
         return false;
 
@@ skipping 140 matching lines @@
     Shape1,
     Shape2,
 };
 
 template<typename Operation>
 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
 {
     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;
 
     SpanIterator spans1 = shape1.spansBegin();
     SpanIterator spans1End = shape1.spansEnd();
 
     SpanIterator spans2 = shape2.spansBegin();
     SpanIterator spans2End = shape2.spansEnd();
 
     SegmentIterator segments1 = 0;
     SegmentIterator segments1End = 0;
 
     SegmentIterator segments2 = 0;
     SegmentIterator segments2End = 0;
 
+    Vector<int, segmentsDefaultCapacity> segments;
+    segments.reserveCapacity(std::max(shape1.segmentsSize(), shape2.segmentsSize()));
+
     // Iterate over all spans.
     while (spans1 != spans1End && spans2 != spans2End) {
         int y = 0;
         int test = spans1->y - spans2->y;
 
         if (test <= 0) {
             y = spans1->y;
 
             segments1 = shape1.segmentsBegin(spans1);
             segments1End = shape1.segmentsEnd(spans1);
             ++spans1;
         }
         if (test >= 0) {
             y = spans2->y;
 
             segments2 = shape2.segmentsBegin(spans2);
             segments2End = shape2.segmentsEnd(spans2);
             ++spans2;
         }
 
         int flag = 0;
         int oldFlag = 0;
 
         SegmentIterator s1 = segments1;
         SegmentIterator s2 = segments2;
 
-        Vector<int, 32> segments;
+        // Clear vector without dropping capacity.
+        segments.resize(0);

[danakj, 2014/05/12 22:57:09]

Can you assert the capacity after this verify it keeps doing what you intend?

[ostap, 2014/05/13 19:05:21]

Assert that capacity didn't grow and there was now reallocs?
I think this assert is not right and there could be reallocs in some cases like
joining single line of non-intersecting rects with another single line of rects
at the same height. But those cases are extremely rare I don't think it should
be taken into account.

[danakj, 2014/05/13 19:09:03]

I meant assert that the capacity was not shrunken to 0 as the comment claims it
will not be.

[ostap, 2014/05/13 20:07:48]

Done.

 
         // Now iterate over the segments in each span and construct a new vector of segments.
         while (s1 != segments1End && s2 != segments2End) {
             int test = *s1 - *s2;
             int x;
 
             if (test <= 0) {
                 x = *s1;
                 flag = flag ^ 1;
                 ++s1;
@@ skipping 20 matching lines @@
         if (!segments.isEmpty() || !result.isEmpty())
             result.appendSpan(y, segments.data(), segments.data() + segments.size());
     }
 
     // Add any remaining spans.
     if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
         result.appendSpans(shape1, spans1, spans1End);
     else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
         result.appendSpans(shape2, spans2, spans2End);
 
+    result.trimCapacities();
+
     return result;
 }
 
 struct Region::Shape::UnionOperation {
     static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
     {
         if (shape1.isEmpty()) {
             result = shape2;
             return true;
         }
@@ skipping 112 matching lines @@
     m_bounds = m_shape.bounds();
 }
 
 void Region::translate(const IntSize& offset)
 {
     m_bounds.move(offset);
     m_shape.translate(offset);
 }
 
 } // namespace WebCore