Make Courgette as much as 5x faster.

courgette/memory_allocator.h

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef COURGETTE_MEMORY_ALLOCATOR_H_
 #define COURGETTE_MEMORY_ALLOCATOR_H_
 
 #include <memory>
 
 #include "base/basictypes.h"
@@ skipping 315 matching lines @@
   CheckBool reserve(size_t size) WARN_UNUSED_RESULT {
     if (failed())
       return false;
 
     if (size <= alloc_size_)
       return true;
 
     if (size < kStartSize)
       size = kStartSize;
 
+    // Use a size 1% higher than requested. In practice, this makes Courgette as
+    // much as 5x faster on typical Chrome update payloads as a lot of future
+    // reserve() calls will become no-ops instead of costly resizes that copy
+    // all the data. Note that doing this here instead of outside the function
+    // is more efficient, since it's after the no-op early return checks above.
+    size *= 1.01;

[gab, 2014/09/12 04:12:19]

This will have no impact on reserves below 100, should we also increment |size|
by a fixed amount before applying the multiplier?

Or how about we round |size| up to the nearest multiple of 2? This would most
likely provide nice memory alignment properties while also guaranteeing an
amortized linear time buffer size increase if reserve is called with sequential
indices (which is terrible usage of reserve() and should be fixed in itself).

[gab, 2014/09/12 04:16:06]

Oops s/multiple of 2/power of 2/ of course.

     T* new_buffer = alloc_.allocate(size);
     if (!new_buffer) {
       clear();
       alloc_size_ = kAllocationFailure;
     } else {
       if (buffer_) {
         memcpy(new_buffer, buffer_, size_ * sizeof(T));
         alloc_.deallocate(buffer_, alloc_size_);
       }
       buffer_ = new_buffer;
@@ skipping 111 matching lines @@
  protected:
   T* buffer_;
   size_t size_;  // how much of the buffer we're using.
   size_t alloc_size_;  // how much space we have allocated.
   Allocator alloc_;
 };
 
 }  // namespace courgette
 
 #endif  // COURGETTE_MEMORY_ALLOCATOR_H_