diff options
author | Etienne Pierre-doray <etiennep@chromium.org> | 2021-10-29 14:12:23 +0000 |
---|---|---|
committer | Copybara-Service <copybara-worker@google.com> | 2021-10-29 07:21:52 -0700 |
commit | 8bb965d29e918d0559589a215ff7f4bd0874bc08 (patch) | |
tree | 5f8e62ce428ef559d57789248ed2d237e33791e8 | |
parent | b90a947429fdce96b1d684b9a7af9683cb4a13c1 (diff) | |
download | zucchini-8bb965d29e918d0559589a215ff7f4bd0874bc08.tar.gz |
[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
-rw-r--r-- | equivalence_map.cc | 5 | ||||
-rw-r--r-- | equivalence_map.h | 11 | ||||
-rw-r--r-- | equivalence_map_unittest.cc | 28 |
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(); |