[zucchini]: Convert TargetPool to deque.

shrink_to_fit with vector tends to cause high memory peak.
Changing deque is a simple change that reduces memory peak at the cost of
loss of guarantee (contiguous storage).

Similar to https://chromium-review.googlesource.com/c/chromium/src/+/2830864
which dramatically reduced crach rate
https://crash.corp.google.com/browse?q=product_name%3D%27Chrome%27+AND+EXISTS+%28SELECT+1+FROM+UNNEST%28CrashedStackTrace.StackFrame%29+WHERE+FunctionName%3D%27installer%3A%3AArchivePatchHelper%3A%3AZucchiniEnsemblePatch%27%29+AND+expanded_custom_data.ChromeCrashProto.magic_signature_1.name%3D%27%5BOut+of+Memory%5D+zucchini%3A%3ADisassemblerWin32%3Czucchini%3A%3AWin32X64Traits%3E%3A%3AParseAndStoreRel32%27

An alternative is to look ahead to determine vector size. The is hard to do
with SortAndUniquify, which performs in-place modifications.

Bug: 1247633
Change-Id: I624c360ee1f2bf18bd584d1aafdde0f0c2ffb61e
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/3149810
Commit-Queue: Etienne Pierre-Doray <etiennep@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/main@{#921292}
NOKEYCHECK=True
GitOrigin-RevId: 380557e6b592531eb360513791968dd7ab0ee77d

11 files changed, 46 insertions, 42 deletions

diff --git a/algorithm.h b/algorithm.h
index f5d49e3..4cafe93 100644
--- a/algorithm.h
+++ b/algorithm.h
@@ -8,6 +8,7 @@
 #include <stddef.h>
 
 #include <algorithm>
+#include <deque>
 #include <type_traits>
 #include <vector>
 
@@ -69,7 +70,7 @@ inline int IncrementForAlignCeil4(T pos) {
 
 // Sorts values in |container| and removes duplicates.
 template <class T>
-void SortAndUniquify(std::vector<T>* container) {
+void SortAndUniquify(std::deque<T>* container) {
   std::sort(container->begin(), container->end());
   container->erase(std::unique(container->begin(), container->end()),
                    container->end());
diff --git a/equivalence_map.cc b/equivalence_map.cc
index 26c0764..be9ec0f 100644
--- a/equivalence_map.cc
+++ b/equivalence_map.cc
@@ -291,7 +291,7 @@ offset_t OffsetMapper::ExtendedForwardProject(offset_t offset) const {
                                                 : kOffsetBound - 1;
 }
 
-void OffsetMapper::ForwardProjectAll(std::vector<offset_t>* offsets) const {
+void OffsetMapper::ForwardProjectAll(std::deque<offset_t>* offsets) const {
   DCHECK(std::is_sorted(offsets->begin(), offsets->end()));
   auto current = equivalences_.begin();
   for (auto& src : *offsets) {
diff --git a/equivalence_map.h b/equivalence_map.h
index 8b716a1..2a8b7de 100644
--- a/equivalence_map.h
+++ b/equivalence_map.h
@@ -128,7 +128,7 @@ class OffsetMapper {
   // Given sorted |offsets|, applies a projection in-place of all offsets that
   // are part of a pruned equivalence from |old_image| to |new_image|. Other
   // offsets are removed from |offsets|.
-  void ForwardProjectAll(std::vector<offset_t>* offsets) const;
+  void ForwardProjectAll(std::deque<offset_t>* offsets) const;
 
   // Accessor for testing.
   const std::vector<Equivalence> equivalences() const { return equivalences_; }
diff --git a/equivalence_map_unittest.cc b/equivalence_map_unittest.cc
index b3a4ea4..508bf23 100644
--- a/equivalence_map_unittest.cc
+++ b/equivalence_map_unittest.cc
@@ -22,7 +22,7 @@ namespace zucchini {
 
 namespace {
 
-using OffsetVector = std::vector<offset_t>;
+using OffsetDeque = std::deque<offset_t>;
 
 // Make all references 2 bytes long.
 constexpr offset_t kReferenceSize = 2;
@@ -504,7 +504,7 @@ TEST(EquivalenceMapTest, ExtendedForwardProjectEncoding) {
 TEST(EquivalenceMapTest, ForwardProjectAll) {
   auto ForwardProjectAllTest = [](const OffsetMapper& offset_mapper,
                                   std::initializer_list<offset_t> offsets) {
-    OffsetVector offsets_vec(offsets);
+    std::deque<offset_t> offsets_vec(offsets);
     offset_mapper.ForwardProjectAll(&offsets_vec);
     return offsets_vec;
   };
@@ -512,29 +512,29 @@ TEST(EquivalenceMapTest, ForwardProjectAll) {
   // [0,2) --> [10,12), [2,3) --> [13,14), [4,6) --> [16,18).
   OffsetMapper offset_mapper1({{0, 10, +2}, {2, 13, +1}, {4, 16, +2}}, 100U,
                               100U);
-  EXPECT_EQ(OffsetVector({10}), ForwardProjectAllTest(offset_mapper1, {0}));
-  EXPECT_EQ(OffsetVector({13}), ForwardProjectAllTest(offset_mapper1, {2}));
-  EXPECT_EQ(OffsetVector({}), ForwardProjectAllTest(offset_mapper1, {3}));
-  EXPECT_EQ(OffsetVector({10, 13}),
+  EXPECT_EQ(OffsetDeque({10}), ForwardProjectAllTest(offset_mapper1, {0}));
+  EXPECT_EQ(OffsetDeque({13}), ForwardProjectAllTest(offset_mapper1, {2}));
+  EXPECT_EQ(OffsetDeque({}), ForwardProjectAllTest(offset_mapper1, {3}));
+  EXPECT_EQ(OffsetDeque({10, 13}),
             ForwardProjectAllTest(offset_mapper1, {0, 2}));
-  EXPECT_EQ(OffsetVector({11, 13, 17}),
+  EXPECT_EQ(OffsetDeque({11, 13, 17}),
             ForwardProjectAllTest(offset_mapper1, {1, 2, 5}));
-  EXPECT_EQ(OffsetVector({11, 17}),
+  EXPECT_EQ(OffsetDeque({11, 17}),
             ForwardProjectAllTest(offset_mapper1, {1, 3, 5}));
-  EXPECT_EQ(OffsetVector({10, 11, 13, 16, 17}),
+  EXPECT_EQ(OffsetDeque({10, 11, 13, 16, 17}),
             ForwardProjectAllTest(offset_mapper1, {0, 1, 2, 3, 4, 5, 6}));
 
   // [0,2) --> [10,12), [13,14) --> [2,3), [16,18) --> [4,6).
   OffsetMapper offset_mapper2({{0, 10, +2}, {13, 2, +1}, {16, 4, +2}}, 100U,
                               100U);
-  EXPECT_EQ(OffsetVector({2}), ForwardProjectAllTest(offset_mapper2, {13}));
-  EXPECT_EQ(OffsetVector({10, 2}),
+  EXPECT_EQ(OffsetDeque({2}), ForwardProjectAllTest(offset_mapper2, {13}));
+  EXPECT_EQ(OffsetDeque({10, 2}),
             ForwardProjectAllTest(offset_mapper2, {0, 13}));
-  EXPECT_EQ(OffsetVector({11, 2, 5}),
+  EXPECT_EQ(OffsetDeque({11, 2, 5}),
             ForwardProjectAllTest(offset_mapper2, {1, 13, 17}));
-  EXPECT_EQ(OffsetVector({11, 5}),
+  EXPECT_EQ(OffsetDeque({11, 5}),
             ForwardProjectAllTest(offset_mapper2, {1, 14, 17}));
-  EXPECT_EQ(OffsetVector({10, 11, 2, 4, 5}),
+  EXPECT_EQ(OffsetDeque({10, 11, 2, 4, 5}),
             ForwardProjectAllTest(offset_mapper2, {0, 1, 13, 14, 16, 17, 18}));
 }
 
diff --git a/target_pool.cc b/target_pool.cc
index 23551fd..e15d0b9 100644
--- a/target_pool.cc
+++ b/target_pool.cc
@@ -16,7 +16,7 @@ namespace zucchini {
 
 TargetPool::TargetPool() = default;
 
-TargetPool::TargetPool(std::vector<offset_t>&& targets) {
+TargetPool::TargetPool(std::deque<offset_t>&& targets) {
   DCHECK(targets_.empty());
   DCHECK(std::is_sorted(targets.begin(), targets.end()));
   targets_ = std::move(targets);
diff --git a/target_pool.h b/target_pool.h
index 27884d6..fb462b2 100644
--- a/target_pool.h
+++ b/target_pool.h
@@ -7,6 +7,7 @@
 
 #include <stddef.h>
 
+#include <deque>
 #include <vector>
 
 #include "components/zucchini/image_utils.h"
@@ -21,11 +22,11 @@ class TargetSource;
 // with a list of associated reference types, only used during patch generation.
 class TargetPool {
  public:
-  using const_iterator = std::vector<offset_t>::const_iterator;
+  using const_iterator = std::deque<offset_t>::const_iterator;
 
   TargetPool();
   // Initializes the object with given sorted and unique |targets|.
-  explicit TargetPool(std::vector<offset_t>&& targets);
+  explicit TargetPool(std::deque<offset_t>&& targets);
   TargetPool(TargetPool&&);
   TargetPool(const TargetPool&);
   ~TargetPool();
@@ -62,7 +63,7 @@ class TargetPool {
   void FilterAndProject(const OffsetMapper& offset_mapper);
 
   // Accessors for testing.
-  const std::vector<offset_t>& targets() const { return targets_; }
+  const std::deque<offset_t>& targets() const { return targets_; }
   const std::vector<TypeTag>& types() const { return types_; }
 
   // Returns the number of targets.
@@ -72,7 +73,7 @@ class TargetPool {
 
  private:
   std::vector<TypeTag> types_;     // Enumerates type_tag for this pool.
-  std::vector<offset_t> targets_;  // Targets for pool in ascending order.
+  std::deque<offset_t> targets_;   // Targets for pool in ascending order.
 };
 
 }  // namespace zucchini
diff --git a/target_pool_unittest.cc b/target_pool_unittest.cc
index 4c3efec..9a779b0 100644
--- a/target_pool_unittest.cc
+++ b/target_pool_unittest.cc
@@ -5,9 +5,9 @@
 #include "components/zucchini/target_pool.h"
 
 #include <cmath>
+#include <deque>
 #include <string>
 #include <utility>
-#include <vector>
 
 #include "components/zucchini/image_utils.h"
 #include "testing/gtest/include/gtest/gtest.h"
@@ -16,29 +16,29 @@ namespace zucchini {
 
 namespace {
 
-using OffsetVector = std::vector<offset_t>;
+using OffsetDeque = std::deque<offset_t>;
 
 }  // namespace
 
 TEST(TargetPoolTest, InsertTargetsFromReferences) {
-  auto test_insert = [](std::vector<Reference>&& references) -> OffsetVector {
+  auto test_insert = [](std::vector<Reference>&& references) -> OffsetDeque {
     TargetPool target_pool;
     target_pool.InsertTargets(references);
     // Return copy since |target_pool| goes out of scope.
     return target_pool.targets();
   };
 
-  EXPECT_EQ(OffsetVector(), test_insert({}));
-  EXPECT_EQ(OffsetVector({0, 1}), test_insert({{0, 0}, {10, 1}}));
-  EXPECT_EQ(OffsetVector({0, 1}), test_insert({{0, 1}, {10, 0}}));
-  EXPECT_EQ(OffsetVector({0, 1, 2}), test_insert({{0, 1}, {10, 0}, {20, 2}}));
-  EXPECT_EQ(OffsetVector({0}), test_insert({{0, 0}, {10, 0}}));
-  EXPECT_EQ(OffsetVector({0, 1}), test_insert({{0, 0}, {10, 0}, {20, 1}}));
+  EXPECT_EQ(OffsetDeque(), test_insert({}));
+  EXPECT_EQ(OffsetDeque({0, 1}), test_insert({{0, 0}, {10, 1}}));
+  EXPECT_EQ(OffsetDeque({0, 1}), test_insert({{0, 1}, {10, 0}}));
+  EXPECT_EQ(OffsetDeque({0, 1, 2}), test_insert({{0, 1}, {10, 0}, {20, 2}}));
+  EXPECT_EQ(OffsetDeque({0}), test_insert({{0, 0}, {10, 0}}));
+  EXPECT_EQ(OffsetDeque({0, 1}), test_insert({{0, 0}, {10, 0}, {20, 1}}));
 }
 
 TEST(TargetPoolTest, KeyOffset) {
   auto test_key_offset = [](const std::string& nearest_offsets_key,
-                            OffsetVector&& targets) {
+                            OffsetDeque&& targets) {
     TargetPool target_pool(std::move(targets));
     for (offset_t offset : target_pool.targets()) {
       offset_t key = target_pool.KeyForOffset(offset);
diff --git a/targets_affinity.cc b/targets_affinity.cc
index d083787..b9a4877 100644
--- a/targets_affinity.cc
+++ b/targets_affinity.cc
@@ -21,8 +21,8 @@ TargetsAffinity::~TargetsAffinity() = default;
 
 void TargetsAffinity::InferFromSimilarities(
     const EquivalenceMap& equivalences,
-    const std::vector<offset_t>& old_targets,
-    const std::vector<offset_t>& new_targets) {
+    const std::deque<offset_t>& old_targets,
+    const std::deque<offset_t>& new_targets) {
   forward_association_.assign(old_targets.size(), {});
   backward_association_.assign(new_targets.size(), {});
 
diff --git a/targets_affinity.h b/targets_affinity.h
index dff1741..163b015 100644
--- a/targets_affinity.h
+++ b/targets_affinity.h
@@ -8,6 +8,7 @@
 #include <stddef.h>
 #include <stdint.h>
 
+#include <deque>
 #include <vector>
 
 #include "components/zucchini/image_utils.h"
@@ -30,8 +31,8 @@ class TargetsAffinity {
   // affinity scores. Both |old_targets| and |new_targets| are targets in the
   // same pool and are sorted in ascending order.
   void InferFromSimilarities(const EquivalenceMap& equivalence_map,
-                             const std::vector<offset_t>& old_targets,
-                             const std::vector<offset_t>& new_targets);
+                             const std::deque<offset_t>& old_targets,
+                             const std::deque<offset_t>& new_targets);
 
   // Assigns labels to targets based on associations previously inferred, using
   // |min_affinity| to reject associations with weak |affinity|. Label 0 is
diff --git a/targets_affinity_unittest.cc b/targets_affinity_unittest.cc
index 86182f9..abcbd3f 100644
--- a/targets_affinity_unittest.cc
+++ b/targets_affinity_unittest.cc
@@ -25,8 +25,8 @@ TEST(TargetsAffinityTest, AffinityBetween) {
 
   auto test_affinity = [&targets_affinity](
                            const EquivalenceMap& equivalence_map,
-                           const std::vector<offset_t>& old_targets,
-                           const std::vector<offset_t>& new_targets) {
+                           const std::deque<offset_t>& old_targets,
+                           const std::deque<offset_t>& new_targets) {
     targets_affinity.InferFromSimilarities(equivalence_map, old_targets,
                                            new_targets);
     AffinityVector affinities(old_targets.size());
@@ -81,8 +81,8 @@ TEST(TargetsAffinityTest, AssignLabels) {
 
   auto test_labels_assignment =
       [&targets_affinity](const EquivalenceMap& equivalence_map,
-                          const std::vector<offset_t>& old_targets,
-                          const std::vector<offset_t>& new_targets,
+                          const std::deque<offset_t>& old_targets,
+                          const std::deque<offset_t>& new_targets,
                           double min_affinity,
                           const std::vector<uint32_t>& expected_old_labels,
                           const std::vector<uint32_t>& expected_new_labels) {
diff --git a/zucchini_gen_unittest.cc b/zucchini_gen_unittest.cc
index 3a6d2cb..bc37bf6 100644
--- a/zucchini_gen_unittest.cc
+++ b/zucchini_gen_unittest.cc
@@ -6,6 +6,7 @@
 
 #include <stdint.h>
 
+#include <deque>
 #include <utility>
 #include <vector>
 
@@ -30,8 +31,8 @@ constexpr double kDummySim = 0.0;
 std::vector<int32_t> GenerateReferencesDeltaTest(
     std::vector<Reference>&& old_references,
     std::vector<Reference>&& new_references,
-    std::vector<offset_t>&& exp_old_targets,
-    std::vector<offset_t>&& exp_projected_old_targets,
+    std::deque<offset_t>&& exp_old_targets,
+    std::deque<offset_t>&& exp_projected_old_targets,
     EquivalenceMap&& equivalence_map) {
   // OffsetMapper needs image sizes for forward-projection overflow check. These
   // are tested elsewhere, so just use arbitrary large value.