[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

1 files changed, 10 insertions, 10 deletions

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);