[Zucchini]: Convert OffsetMapper to deque

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

This has no significant impact on cpu time. On MacBook pro 2017
Before:
Zucchini.TotalTime 9.95879 s
Zucchini.TotalTime 9.11599 s
Zucchini.TotalTime 9.33174 s
After:
Zucchini.TotalTime 10.5557 s
Zucchini.TotalTime 8.78599 s
Zucchini.TotalTime 8.95282 s

Bug: 1262150
Change-Id: I078a671832f2a33d5e1a3d9d971bff66d4179b89
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/3247092
Commit-Queue: Etienne Pierre-Doray <etiennep@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/main@{#936371}
NOKEYCHECK=True
GitOrigin-RevId: 7abe67cf21e8f30c0ff2499410c8d57aae9bf8fc

3 files changed, 23 insertions, 21 deletions

diff --git a/equivalence_map.cc b/equivalence_map.cc
index be9ec0f..b4d5e27 100644
--- a/equivalence_map.cc
+++ b/equivalence_map.cc
@@ -214,7 +214,7 @@ EquivalenceCandidate VisitEquivalenceSeed(
 
 /******** OffsetMapper ********/
 
-OffsetMapper::OffsetMapper(std::vector<Equivalence>&& equivalences,
+OffsetMapper::OffsetMapper(std::deque<Equivalence>&& equivalences,
                            offset_t old_image_size,
                            offset_t new_image_size)
     : equivalences_(std::move(equivalences)),
@@ -310,7 +310,7 @@ void OffsetMapper::ForwardProjectAll(std::deque<offset_t>* offsets) const {
 }
 
 void OffsetMapper::PruneEquivalencesAndSortBySource(
-    std::vector<Equivalence>* equivalences) {
+    std::deque<Equivalence>* equivalences) {
   std::sort(equivalences->begin(), equivalences->end(),
             [](const Equivalence& a, const Equivalence& b) {
               return a.src_offset < b.src_offset;
@@ -368,6 +368,7 @@ void OffsetMapper::PruneEquivalencesAndSortBySource(
   base::EraseIf(*equivalences, [](const Equivalence& equivalence) {
     return equivalence.length == 0;
   });
+  equivalences->shrink_to_fit();
 }
 
 /******** EquivalenceMap ********/
diff --git a/equivalence_map.h b/equivalence_map.h
index 2a8b7de..af99ac4 100644
--- a/equivalence_map.h
+++ b/equivalence_map.h
@@ -7,6 +7,7 @@
 
 #include <stddef.h>
 
+#include <deque>
 #include <limits>
 #include <vector>
 
@@ -82,13 +83,13 @@ EquivalenceCandidate VisitEquivalenceSeed(
 // bytes in |old_image| and |new_image|) one-to-one.
 class OffsetMapper {
  public:
-  using const_iterator = std::vector<Equivalence>::const_iterator;
+  using const_iterator = std::deque<Equivalence>::const_iterator;
 
   // Constructors for various data sources. "Old" and "new" image sizes are
   // needed for bounds checks and to handle dangling targets.
   // - From a list of |equivalences|, already sorted (by |src_offset|) and
   //   pruned, useful for tests.
-  OffsetMapper(std::vector<Equivalence>&& equivalences,
+  OffsetMapper(std::deque<Equivalence>&& equivalences,
                offset_t old_image_size,
                offset_t new_image_size);
   // - From a generator, useful for Zucchini-apply.
@@ -131,7 +132,7 @@ class OffsetMapper {
   void ForwardProjectAll(std::deque<offset_t>* offsets) const;
 
   // Accessor for testing.
-  const std::vector<Equivalence> equivalences() const { return equivalences_; }
+  const std::deque<Equivalence> equivalences() const { return equivalences_; }
 
   // Sorts |equivalences| by |src_offset| and removes all source overlaps; so a
   // source location that was covered by some Equivalence would become covered
@@ -140,12 +141,12 @@ class OffsetMapper {
   // of a tie, the Equivalence with minimal |src_offset|. |equivalences| may
   // change in size since empty Equivalences are removed.
   static void PruneEquivalencesAndSortBySource(
-      std::vector<Equivalence>* equivalences);
+      std::deque<Equivalence>* equivalences);
 
  private:
   // |equivalences_| is pruned, i.e., no "old" blocks overlap (and no "new"
   // block overlaps). Also, it is sorted by "old" offsets.
-  std::vector<Equivalence> equivalences_;
+  std::deque<Equivalence> equivalences_;
   const offset_t old_image_size_;
   const offset_t new_image_size_;
 };
diff --git a/equivalence_map_unittest.cc b/equivalence_map_unittest.cc
index 508bf23..6b826d1 100644
--- a/equivalence_map_unittest.cc
+++ b/equivalence_map_unittest.cc
@@ -252,28 +252,28 @@ TEST(EquivalenceMapTest, ExtendEquivalenceBackward) {
 
 TEST(EquivalenceMapTest, PruneEquivalencesAndSortBySource) {
   auto PruneEquivalencesAndSortBySourceTest =
-      [](std::vector<Equivalence>&& equivalences) {
+      [](std::deque<Equivalence>&& equivalences) {
         OffsetMapper::PruneEquivalencesAndSortBySource(&equivalences);
         return std::move(equivalences);
       };
 
-  EXPECT_EQ(std::vector<Equivalence>(),
+  EXPECT_EQ(std::deque<Equivalence>(),
             PruneEquivalencesAndSortBySourceTest({}));
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, 1}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, 1}}),
             PruneEquivalencesAndSortBySourceTest({{0, 10, 1}}));
-  EXPECT_EQ(std::vector<Equivalence>(),
+  EXPECT_EQ(std::deque<Equivalence>(),
             PruneEquivalencesAndSortBySourceTest({{0, 10, 0}}));
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, 1}, {1, 11, 1}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, 1}, {1, 11, 1}}),
             PruneEquivalencesAndSortBySourceTest({{0, 10, 1}, {1, 11, 1}}));
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, 2}, {2, 13, 1}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, 2}, {2, 13, 1}}),
             PruneEquivalencesAndSortBySourceTest({{0, 10, 2}, {1, 12, 2}}));
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, 2}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, 2}}),
             PruneEquivalencesAndSortBySourceTest({{0, 10, 2}, {1, 12, 1}}));
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, 2}, {2, 14, 1}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, 2}, {2, 14, 1}}),
             PruneEquivalencesAndSortBySourceTest({{0, 10, 2}, {1, 13, 2}}));
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, 1}, {1, 12, 3}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, 1}, {1, 12, 3}}),
             PruneEquivalencesAndSortBySourceTest({{0, 10, 2}, {1, 12, 3}}));
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, 3}, {3, 16, 2}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, 3}, {3, 16, 2}}),
             PruneEquivalencesAndSortBySourceTest(
                 {{0, 10, 3}, {1, 13, 3}, {3, 16, 2}}));  // Pruning is greedy
 
@@ -288,9 +288,9 @@ TEST(EquivalenceMapTest, PruneEquivalencesAndSortBySource) {
   //                 ***************
   // This test case makes sure the function does not stall on a large instance
   // of this pattern.
-  EXPECT_EQ(std::vector<Equivalence>({{0, 10, +300000}, {300000, 30, +300000}}),
+  EXPECT_EQ(std::deque<Equivalence>({{0, 10, +300000}, {300000, 30, +300000}}),
             PruneEquivalencesAndSortBySourceTest([] {
-              std::vector<Equivalence> equivalenses;
+              std::deque<Equivalence> equivalenses;
               equivalenses.push_back({0, 10, +300000});
               for (offset_t i = 0; i < 100000; ++i)
                 equivalenses.push_back({200000 + i, 20, +200000 - 2 * i});
@@ -302,7 +302,7 @@ TEST(EquivalenceMapTest, PruneEquivalencesAndSortBySource) {
 TEST(EquivalenceMapTest, NaiveExtendedForwardProject) {
   constexpr size_t kOldImageSize = 1000U;
   constexpr size_t kNewImageSize = 1000U;
-  OffsetMapper offset_mapper(std::vector<Equivalence>(), kOldImageSize,
+  OffsetMapper offset_mapper(std::deque<Equivalence>(), kOldImageSize,
                              kNewImageSize);
 
   // Convenience function to declutter.
@@ -417,7 +417,7 @@ TEST(EquivalenceMapTest, ExtendedForwardProjectEncoding) {
   // - '.' are "new" offsets that appear as output.
   // - '(' and ')' surround a single "new" location that are repeated as output.
   int case_no = 0;
-  auto run_test = [&case_no](std::vector<Equivalence>&& equivalences,
+  auto run_test = [&case_no](std::deque<Equivalence>&& equivalences,
                              const std::string& old_spec,
                              const std::string& new_spec) {
     const size_t old_size = old_spec.length();