Make Courgette as much as 5x faster.

Changes the Courgette vector implementation to slightly
over-reserve the size of the vector, which makes many future
reserve operations no-ops (as they're quite expensive otherwise,
since they copy the full contents of the previous buffer).

When applying the patch from 35.0.1916.114 to 37.0.2062.120,
before and after this change, the runtime goes from 1m10s to 21s
on my z620.

Slightly higher multipliers produce even better results (e.g. 19s),
but this seemed like a reasonable value to chose so that it doesn't
result in significant additional memory use by Courgette.

BUG=167622
TEST=Build courgette target in Release mode and run it as
courgette.exe -apply chrome.7z chrome_patch.diff out.7z
(where chrome.7z was from un7zipping a 37.0.2062.94 chrome
installer and chrome_patch.diff was from un7zipping a
37.0.2062.94 -> 37.0.2062.120_37 chrome_updater_3stage.exe).
With the patch, the operation should run ~5x faster.

Review URL: https://codereview.chromium.org/565753002

Cr-Commit-Position: refs/heads/master@{#294592}

1 files changed, 6 insertions, 0 deletions

diff --git a/courgette/memory_allocator.h b/courgette/memory_allocator.h
index 5386dad..ada7f40 100644
--- a/courgette/memory_allocator.h
+++ b/courgette/memory_allocator.h
@@ -333,6 +333,12 @@ class NoThrowBuffer {
     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;
     T* new_buffer = alloc_.allocate(size);
     if (!new_buffer) {
       clear();