[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.

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<UnwrappedTileID, Leaf> pool;
 
 public:
+    // The given vector must be sorted by id.
     template <typename Renderable>
-    void update(std::vector<std::reference_wrapper<Renderable>> renderables);
+    void update(std::vector<std::reference_wrapper<Renderable>> sortedRenderables);
 
     std::map<UnwrappedTileID, ClipID> 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 <typename Renderable>
 void ClipIDGenerator::update(std::vector<std::reference_wrapper<Renderable>> 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 <typename Renderable>
 void updateTileMasks(std::vector<std::reference_wrapper<Renderable>> 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<Renderable>& renderables) {
+    std::vector<std::reference_wrapper<Renderable>> 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<Renderable>({ renderables.begin(), renderables.end() });
+    generator.update<Renderable>(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<Renderable>({ renderables.begin(), renderables.end() });
+    generator.update<Renderable>(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<Renderable>({ renderables.begin(), renderables.end() });
+    generator.update<Renderable>(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<Renderable>({ renderables.begin(), renderables.end() });
+    generator.update<Renderable>(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<Renderable>({ renderables1.begin(), renderables1.end() });
-    generator.update<Renderable>({ renderables2.begin(), renderables2.end() });
+    generator.update<Renderable>(makeSorted(renderables1));
+    generator.update<Renderable>(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<MaskedRenderable> expected) {
     std::vector<MaskedRenderable> actual = expected;
     std::for_each(actual.begin(), actual.end(),
                   [](auto& renderable) { renderable.mask.clear(); });
-    algorithm::updateTileMasks<MaskedRenderable>({ actual.begin(), actual.end() });
+    std::vector<std::reference_wrapper<MaskedRenderable>> sorted(actual.begin(), actual.end());
+    std::sort(sorted.begin(), sorted.end(),
+                  [](const MaskedRenderable& a, const MaskedRenderable& b){ return a.id < b.id; });
+    algorithm::updateTileMasks<MaskedRenderable>(std::move(sorted));
     EXPECT_EQ(expected, actual);
 }