diff options
author | Etienne Pierre-doray <etiennep@chromium.org> | 2021-09-14 17:31:51 +0000 |
---|---|---|
committer | Copybara-Service <copybara-worker@google.com> | 2021-09-14 10:48:48 -0700 |
commit | aff408603b3db5b7974c522db2ad8c5ce2a0f3c1 (patch) | |
tree | 4366ce54a82c7aa38617942292f0a30b08a775cd | |
parent | 9ff43f558d334f100a92bf93d764f32293f9c5aa (diff) | |
download | zucchini-aff408603b3db5b7974c522db2ad8c5ce2a0f3c1.tar.gz |
[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
-rw-r--r-- | algorithm.h | 3 | ||||
-rw-r--r-- | equivalence_map.cc | 2 | ||||
-rw-r--r-- | equivalence_map.h | 2 | ||||
-rw-r--r-- | equivalence_map_unittest.cc | 28 | ||||
-rw-r--r-- | target_pool.cc | 2 | ||||
-rw-r--r-- | target_pool.h | 9 | ||||
-rw-r--r-- | target_pool_unittest.cc | 20 | ||||
-rw-r--r-- | targets_affinity.cc | 4 | ||||
-rw-r--r-- | targets_affinity.h | 5 | ||||
-rw-r--r-- | targets_affinity_unittest.cc | 8 | ||||
-rw-r--r-- | zucchini_gen_unittest.cc | 5 |
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. |