[core] Consider symbol bucket leader id in cross-tile symbol indexing

Only buckets with the same leader id participate in `TileLayerIndex::findMatches()`
in order to improve its performace.

`TileLayerIndex` constness is fixed.

2 files changed, 38 insertions, 21 deletions

diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp
index 55ab2cc3c5..d8bd0292ec 100644
--- a/src/mbgl/text/cross_tile_symbol_index.cpp
+++ b/src/mbgl/text/cross_tile_symbol_index.cpp
@@ -6,15 +6,19 @@
 
 namespace mbgl {
 
-
-TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, std::vector<SymbolInstance>& symbolInstances, uint32_t bucketInstanceId_)
-    : coord(coord_), bucketInstanceId(bucketInstanceId_) {
-        for (SymbolInstance& symbolInstance : symbolInstances) {
-            indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, getScaledCoordinates(symbolInstance, coord));
-        }
+TileLayerIndex::TileLayerIndex(OverscaledTileID coord_,
+                               std::vector<SymbolInstance>& symbolInstances,
+                               uint32_t bucketInstanceId_,
+                               std::string bucketLeaderId_)
+    : coord(coord_), bucketInstanceId(bucketInstanceId_), bucketLeaderId(std::move(bucketLeaderId_)) {
+    for (SymbolInstance& symbolInstance : symbolInstances) {
+        indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID,
+                                                                getScaledCoordinates(symbolInstance, coord));
     }
+}
 
-Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, const OverscaledTileID& childTileCoord) {
+Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance,
+                                                    const OverscaledTileID& childTileCoord) const {
     // Round anchor positions to roughly 4 pixel grid
     const double roundingFactor = 512.0 / util::EXTENT / 2.0;
     const double scale = roundingFactor / std::pow(2, childTileCoord.canonical.z - coord.canonical.z);
@@ -24,9 +28,14 @@ Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstan
     };
 }
 
-void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, const OverscaledTileID& newCoord, std::set<uint32_t>& zoomCrossTileIDs) {
+void TileLayerIndex::findMatches(SymbolBucket& bucket,
+                                 const OverscaledTileID& newCoord,
+                                 std::set<uint32_t>& zoomCrossTileIDs) const {
+    auto& symbolInstances = bucket.symbolInstances;
     float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z);
 
+    if (bucket.bucketLeaderID != bucketLeaderId) return;
+
     for (auto& symbolInstance : symbolInstances) {
         if (symbolInstance.crossTileID) {
             // already has a match, skip
@@ -41,7 +50,7 @@ void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, c
 
         auto scaledSymbolCoord = getScaledCoordinates(symbolInstance, newCoord);
 
-        for (IndexedSymbolInstance& thisTileSymbol: it->second) {
+        for (const IndexedSymbolInstance& thisTileSymbol : it->second) {
             // Return any symbol with the same keys whose coordinates are within 1
             // grid unit. (with a 4px grid, this covers a 12px by 12px area)
             if (std::abs(thisTileSymbol.coord.x - scaledSymbolCoord.x) <= tolerance &&
@@ -87,7 +96,7 @@ void CrossTileSymbolLayerIndex::handleWrapJump(float newLng) {
 }
 
 bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, SymbolBucket& bucket, uint32_t& maxCrossTileID) {
-    const auto& thisZoomIndexes = indexes[tileID.overscaledZ];
+    auto& thisZoomIndexes = indexes[tileID.overscaledZ];
     auto previousIndex = thisZoomIndexes.find(tileID);
     if (previousIndex != thisZoomIndexes.end()) {
         if (previousIndex->second.bucketInstanceId == bucket.bucketInstanceId) {
@@ -105,20 +114,22 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol
         symbolInstance.crossTileID = 0;
     }
 
+    auto& thisZoomUsedCrossTileIDs = usedCrossTileIDs[tileID.overscaledZ];
+
     for (auto& it : indexes) {
         auto zoom = it.first;
-        auto zoomIndexes = it.second;
+        const auto& zoomIndexes = it.second;
         if (zoom > tileID.overscaledZ) {
             for (auto& childIndex : zoomIndexes) {
                 if (childIndex.second.coord.isChildOf(tileID)) {
-                    childIndex.second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]);
+                    childIndex.second.findMatches(bucket, tileID, thisZoomUsedCrossTileIDs);
                 }
             }
         } else {
             auto parentTileID = tileID.scaledTo(zoom);
             auto parentIndex = zoomIndexes.find(parentTileID);
             if (parentIndex != zoomIndexes.end()) {
-                parentIndex->second.findMatches(bucket.symbolInstances, tileID, usedCrossTileIDs[tileID.overscaledZ]);
+                parentIndex->second.findMatches(bucket, tileID, thisZoomUsedCrossTileIDs);
             }
         }
     }
@@ -127,13 +138,15 @@ bool CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& tileID, Symbol
         if (!symbolInstance.crossTileID) {
             // symbol did not match any known symbol, assign a new id
             symbolInstance.crossTileID = ++maxCrossTileID;
-            usedCrossTileIDs[tileID.overscaledZ].insert(symbolInstance.crossTileID);
+            thisZoomUsedCrossTileIDs.insert(symbolInstance.crossTileID);
         }
     }
 
-
-    indexes[tileID.overscaledZ].erase(tileID);
-    indexes[tileID.overscaledZ].emplace(tileID, TileLayerIndex(tileID, bucket.symbolInstances, bucket.bucketInstanceId));
+    thisZoomIndexes.erase(tileID);
+    thisZoomIndexes.emplace(
+        std::piecewise_construct,
+        std::forward_as_tuple(tileID),
+        std::forward_as_tuple(tileID, bucket.symbolInstances, bucket.bucketInstanceId, bucket.bucketLeaderID));
     return true;
 }
 
diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp
index 4e32698b3e..ddcdb814c6 100644
--- a/src/mbgl/text/cross_tile_symbol_index.hpp
+++ b/src/mbgl/text/cross_tile_symbol_index.hpp
@@ -31,13 +31,17 @@ public:
 
 class TileLayerIndex {
 public:
-    TileLayerIndex(OverscaledTileID coord, std::vector<SymbolInstance>&, uint32_t bucketInstanceId);
+    TileLayerIndex(OverscaledTileID coord,
+                   std::vector<SymbolInstance>&,
+                   uint32_t bucketInstanceId,
+                   std::string bucketLeaderId);
+
+    Point<int64_t> getScaledCoordinates(SymbolInstance&, const OverscaledTileID&) const;
+    void findMatches(SymbolBucket&, const OverscaledTileID&, std::set<uint32_t>&) const;
 
-    Point<int64_t> getScaledCoordinates(SymbolInstance&, const OverscaledTileID&);
-    void findMatches(std::vector<SymbolInstance>&, const OverscaledTileID&, std::set<uint32_t>&);
-    
     OverscaledTileID coord;
     uint32_t bucketInstanceId;
+    std::string bucketLeaderId;
     std::map<std::u16string,std::vector<IndexedSymbolInstance>> indexedSymbolInstances;
 };