[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

1 files changed, 6 insertions, 5 deletions

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_;
 };