rtc::Buffer: Grow capacity by at least 1.5x to prevent quadratic behavior

webrtc/base/buffer.h

 /*
  *  Copyright 2004 The WebRTC Project Authors. All rights reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
@@ skipping 201 matching lines @@
   }
 
   // The AppendData functions add data to the end of the buffer. They accept
   // the same input types as the constructors.
   template <typename U,
             typename std::enable_if<
                 internal::BufferCompat<T, U>::value>::type* = nullptr>
   void AppendData(const U* data, size_t size) {
     RTC_DCHECK(IsConsistent());
     const size_t new_size = size_ + size;
-    EnsureCapacity(new_size);
+    EnsureCapacityWithHeadroom(new_size, true);
     static_assert(sizeof(T) == sizeof(U), "");
     std::memcpy(data_.get() + size_, data, size * sizeof(U));
     size_ = new_size;
     RTC_DCHECK(IsConsistent());
   }
 
   template <typename U,
             size_t N,
             typename std::enable_if<
                 internal::BufferCompat<T, U>::value>::type* = nullptr>
@@ skipping 32 matching lines @@
     size_ = old_size + written_elements;
     RTC_DCHECK(IsConsistent());
     return written_elements;
   }
 
   // Sets the size of the buffer. If the new size is smaller than the old, the
   // buffer contents will be kept but truncated; if the new size is greater,
   // the existing contents will be kept and the new space will be
   // uninitialized.
   void SetSize(size_t size) {
-    EnsureCapacity(size);
+    EnsureCapacityWithHeadroom(size, true);

[sprang_webrtc, 2016/06/20 09:27:44]

Do we really want with headroom here, as it's an explicit size request?

[kwiberg-webrtc, 2016/06/20 09:51:31]

It's an explicit *size* request, but the caller doesn't necessarily care about
*capacity* (except that it has to grow large enough, obviously). My thinking is
that callers that want the extra control can use EnsureCapacity(); this makes it
harder for callers that don't care to accidentally shoot themselves in the foot.

[sprang_webrtc, 2016/06/20 09:56:28]

Acknowledged.

     size_ = size;
   }
 
   // Ensure that the buffer size can be increased to at least capacity without
   // further reallocation. (Of course, this operation might need to reallocate
   // the buffer.)
   void EnsureCapacity(size_t capacity) {
-    RTC_DCHECK(IsConsistent());
-    if (capacity <= capacity_)
-      return;
-    std::unique_ptr<T[]> new_data(new T[capacity]);
-    std::memcpy(new_data.get(), data_.get(), size_ * sizeof(T));
-    data_ = std::move(new_data);
-    capacity_ = capacity;
-    RTC_DCHECK(IsConsistent());
+    // Don't allocate extra headroom, since the user is asking for a specific
+    // capacity.
+    EnsureCapacityWithHeadroom(capacity, false);
   }
 
   // Resets the buffer to zero size without altering capacity. Works even if the
   // buffer has been moved from.
   void Clear() {
     size_ = 0;
     RTC_DCHECK(IsConsistent());
   }
 
   // Swaps two buffers. Also works for buffers that have been moved from.
   friend void swap(BufferT& a, BufferT& b) {
     using std::swap;
     swap(a.size_, b.size_);
     swap(a.capacity_, b.capacity_);
     swap(a.data_, b.data_);
   }
 
  private:
+  void EnsureCapacityWithHeadroom(size_t capacity, bool extra_headroom) {
+    RTC_DCHECK(IsConsistent());
+    if (capacity <= capacity_)
+      return;
+
+    // If the caller asks for extra headroom, ensure that the new capacity is
+    // >= 1.5 times the old capacity. Any constant > 1 is sufficient to prevent
+    // quadratic behavior; as to why we pick 1.5 in particular, see
+    // https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md and
+    // http://www.gahcep.com/cpp-internals-stl-vector-part-1/.
+    const size_t new_capacity =
+        extra_headroom ? std::max(capacity, capacity_ + capacity_ / 2)
+                       : capacity;

[sprang_webrtc, 2016/06/20 09:27:44]

This seems a little odd. If capacity > 1.5 * capacity_, we expand without the
1.5x margin? 

[kwiberg-webrtc, 2016/06/20 09:51:31]

capacity is the requested capacity. If that's >= 1.5 times current capacity,
there's no need for us to increase the capacity by more than the caller asked
for. Remember, all that's needed to ensure good performance is that we keep the
number of reallocations small, and we do that by always reallocating to a new
buffer that's at least 1.5x the size of the old one. Whether that happens
because we allocate more than the user asked for or because the user happened to
actually ask for a size that's >= 1.5x larger doesn't matter.

[sprang_webrtc, 2016/06/20 09:56:28]

OK, fair enough.

+
+    std::unique_ptr<T[]> new_data(new T[new_capacity]);
+    std::memcpy(new_data.get(), data_.get(), size_ * sizeof(T));
+    data_ = std::move(new_data);
+    capacity_ = new_capacity;
+    RTC_DCHECK(IsConsistent());
+  }
+
   // Precondition for all methods except Clear and the destructor.
   // Postcondition for all methods except move construction and move
   // assignment, which leave the moved-from object in a possibly inconsistent
   // state.
   bool IsConsistent() const {
     return (data_ || capacity_ == 0) && capacity_ >= size_;
   }
 
   // Called when *this has been moved from. Conceptually it's a no-op, but we
   // can mutate the state slightly to help subsequent sanity checks catch bugs.
@@ skipping 14 matching lines @@
   size_t capacity_;
   std::unique_ptr<T[]> data_;
 };
 
 // By far the most common sort of buffer.
 using Buffer = BufferT<uint8_t>;
 
 }  // namespace rtc
 
 #endif  // WEBRTC_BASE_BUFFER_H_