From b83030aa9bb1a8d9f14ae8160698c1ee4d5a4c72 Mon Sep 17 00:00:00 2001 From: Mikhail Pozdnyakov Date: Fri, 18 Jan 2019 13:12:04 +0200 Subject: [core] Remove tile sorting from the clip and mask algorithms The tile sorting can be now removed from the algorithms, which calculate tile mask and clip ids, because their client code provides tiles being already sorted (in `TilePyramid`). This patch brings significant improvements to the Tile-related performance tests results, for example the `TileMaskGeneration` benchmark test runs 33 times faster with these changes applied. --- src/mbgl/algorithm/generate_clip_ids.hpp | 3 ++- src/mbgl/algorithm/generate_clip_ids_impl.hpp | 7 +++---- src/mbgl/algorithm/update_tile_masks.hpp | 6 ++++-- test/algorithm/generate_clip_ids.test.cpp | 21 +++++++++++++++------ test/algorithm/update_tile_masks.test.cpp | 5 ++++- 5 files changed, 28 insertions(+), 14 deletions(-) diff --git a/src/mbgl/algorithm/generate_clip_ids.hpp b/src/mbgl/algorithm/generate_clip_ids.hpp index adcf87a72a..6950433578 100644 --- a/src/mbgl/algorithm/generate_clip_ids.hpp +++ b/src/mbgl/algorithm/generate_clip_ids.hpp @@ -25,8 +25,9 @@ private: std::multimap pool; public: + // The given vector must be sorted by id. template - void update(std::vector> renderables); + void update(std::vector> sortedRenderables); std::map getClipIDs() const; }; diff --git a/src/mbgl/algorithm/generate_clip_ids_impl.hpp b/src/mbgl/algorithm/generate_clip_ids_impl.hpp index fedab06022..a4af9c8cbb 100644 --- a/src/mbgl/algorithm/generate_clip_ids_impl.hpp +++ b/src/mbgl/algorithm/generate_clip_ids_impl.hpp @@ -10,12 +10,11 @@ namespace algorithm { template void ClipIDGenerator::update(std::vector> renderables) { std::size_t size = 0; - - std::sort(renderables.begin(), renderables.end(), - [](const auto& a, const auto& b) { return a.get().id < b.get().id; }); + assert(std::is_sorted(renderables.begin(), renderables.end(), + [](const Renderable& a, const Renderable& b) { return a.id < b.id; })); const auto end = renderables.end(); - for (auto it = renderables.begin(); it != end; it++) { + for (auto it = renderables.begin(); it != end; ++it) { auto& renderable = it->get(); if (!renderable.used || !renderable.needsClipping) { continue; diff --git a/src/mbgl/algorithm/update_tile_masks.hpp b/src/mbgl/algorithm/update_tile_masks.hpp index a7840cd163..c475473cb6 100644 --- a/src/mbgl/algorithm/update_tile_masks.hpp +++ b/src/mbgl/algorithm/update_tile_masks.hpp @@ -95,10 +95,12 @@ void computeTileMasks( // Only other Renderables that are *children* of the Renderable we are generating the mask for will // be considered. For example, adding a Renderable with TileID 4/8/13 won't affect the TileMask for // 2/1/3, since it is not a descendant of it. +// +// The given |renderables| must be sorted by id. template void updateTileMasks(std::vector> renderables) { - std::sort(renderables.begin(), renderables.end(), - [](const Renderable& a, const Renderable& b) { return a.id < b.id; }); + assert(std::is_sorted(renderables.begin(), renderables.end(), + [](const Renderable& a, const Renderable& b) { return a.id < b.id; })); TileMask mask; const auto end = renderables.end(); diff --git a/test/algorithm/generate_clip_ids.test.cpp b/test/algorithm/generate_clip_ids.test.cpp index f01c2da80a..d918514e51 100644 --- a/test/algorithm/generate_clip_ids.test.cpp +++ b/test/algorithm/generate_clip_ids.test.cpp @@ -24,6 +24,15 @@ struct Renderable { } }; +namespace { +auto makeSorted(std::vector& renderables) { + std::vector> sorted(renderables.begin(), renderables.end()); + std::sort(sorted.begin(), sorted.end(), + [](const Renderable& a, const Renderable& b){ return a.id < b.id; }); + return sorted; +} +} // namespace + ::std::ostream& operator<<(::std::ostream& os, const Renderable& rhs) { return os << "Renderable{ " << rhs.id << ", " << rhs.clip << " }"; } @@ -71,7 +80,7 @@ TEST(GenerateClipIDs, ParentAndFourChildrenNegative) { }; algorithm::ClipIDGenerator generator; - generator.update({ renderables.begin(), renderables.end() }); + generator.update(makeSorted(renderables)); EXPECT_EQ(decltype(renderables)({ Renderable{ UnwrappedTileID{ 1, -2, 0 }, ClipID{ "00000111", "00000010" } }, @@ -102,7 +111,7 @@ TEST(GenerateClipIDs, NegativeParentAndMissingLevel) { }; algorithm::ClipIDGenerator generator; - generator.update({ renderables.begin(), renderables.end() }); + generator.update(makeSorted(renderables)); EXPECT_EQ(decltype(renderables)({ Renderable{ UnwrappedTileID{ 1, -1, 0 }, ClipID{ "00000111", "00000001" } }, @@ -186,7 +195,7 @@ TEST(GenerateClipIDs, MultipleLevels) { }; algorithm::ClipIDGenerator generator; - generator.update({ renderables.begin(), renderables.end() }); + generator.update(makeSorted(renderables)); ASSERT_EQ(decltype(renderables)({ Renderable{ UnwrappedTileID{ 2, 0, 0 }, ClipID{ "00001111", "00000001" } }, Renderable{ UnwrappedTileID{ 3, 0, 0 }, ClipID{ "00001111", "00000011" } }, @@ -237,7 +246,7 @@ TEST(GenerateClipIDs, Bug206) { }; algorithm::ClipIDGenerator generator; - generator.update({ renderables.begin(), renderables.end() }); + generator.update(makeSorted(renderables)); EXPECT_EQ( decltype(renderables)({ Renderable{ UnwrappedTileID{ 10, 162, 395 }, ClipID{ "00001111", "00000001" } }, @@ -350,8 +359,8 @@ TEST(GenerateClipIDs, SomeUnclippedTiles) { }; algorithm::ClipIDGenerator generator; - generator.update({ renderables1.begin(), renderables1.end() }); - generator.update({ renderables2.begin(), renderables2.end() }); + generator.update(makeSorted(renderables1)); + generator.update(makeSorted(renderables2)); EXPECT_EQ(decltype(renderables1)({ Renderable { UnwrappedTileID { 7, 36, 49 }, ClipID {"00000011","00000010"} }, Renderable { UnwrappedTileID { 7, 36, 48 }, ClipID {"00000011","00000001"} }, diff --git a/test/algorithm/update_tile_masks.test.cpp b/test/algorithm/update_tile_masks.test.cpp index 3c698eb0cd..381a6628cf 100644 --- a/test/algorithm/update_tile_masks.test.cpp +++ b/test/algorithm/update_tile_masks.test.cpp @@ -45,7 +45,10 @@ void validate(const std::vector expected) { std::vector actual = expected; std::for_each(actual.begin(), actual.end(), [](auto& renderable) { renderable.mask.clear(); }); - algorithm::updateTileMasks({ actual.begin(), actual.end() }); + std::vector> sorted(actual.begin(), actual.end()); + std::sort(sorted.begin(), sorted.end(), + [](const MaskedRenderable& a, const MaskedRenderable& b){ return a.id < b.id; }); + algorithm::updateTileMasks(std::move(sorted)); EXPECT_EQ(expected, actual); } -- cgit v1.2.1