[core] Reserve memory for tileCover container elements

2 files changed, 19 insertions, 12 deletions

diff --git a/benchmark/fixtures/api/cache.db b/benchmark/fixtures/api/cache.db
index a62a3b0f00..611de14077 100644
--- a/benchmark/fixtures/api/cache.db
+++ b/benchmark/fixtures/api/cache.db
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index 5408d84a13..dc39d17297 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -81,21 +81,27 @@ std::vector<UnwrappedTileID> tileCover(const Point<double>& tl,
                                        const Point<double>& bl,
                                        const Point<double>& c,
                                        uint8_t zoom) {
-    const int32_t tiles = 1 << zoom;
+    const int32_t maxTilesPerAxis = 1 << zoom;
 
-    struct ID {
+    struct CoverID {
         int32_t x, y;
         double sqDist;
     };
 
-    std::vector<ID> t;
+    std::vector<CoverID> coverIDs;
+    // Simple bbox for pre-reserving coverIDs elements.
+    const auto maxX = util::max(tl.x, tr.x, br.x, bl.x);
+    const auto minX = util::min(tl.x, tr.x, br.x, bl.x);
+    const auto maxY = util::max(tl.y, tr.x, br.x, bl.x);
+    const auto minY = util::min(tl.y, tr.y, br.y, bl.y);
+    coverIDs.reserve(util::clamp(0lu, size_t((maxX - minX) * (maxY - minY)), std::numeric_limits<size_t>::max()));
 
     auto scanLine = [&](int32_t x0, int32_t x1, int32_t y) {
         int32_t x;
-        if (y >= 0 && y <= tiles) {
+        if (y >= 0 && y <= maxTilesPerAxis) {
             for (x = x0; x < x1; ++x) {
                 const auto dx = x + 0.5 - c.x, dy = y + 0.5 - c.y;
-                t.emplace_back(ID{ x, y, dx * dx + dy * dy });
+                coverIDs.emplace_back(CoverID { x, y, dx * dx + dy * dy });
             }
         }
     };
@@ -104,22 +110,23 @@ std::vector<UnwrappedTileID> tileCover(const Point<double>& tl,
     // \---+
     // | \ |
     // +---\.
-    scanTriangle(tl, tr, br, 0, tiles, scanLine);
-    scanTriangle(br, bl, tl, 0, tiles, scanLine);
+    scanTriangle(tl, tr, br, 0, maxTilesPerAxis, scanLine);
+    scanTriangle(br, bl, tl, 0, maxTilesPerAxis, scanLine);
 
     // Sort first by distance, then by x/y.
-    std::sort(t.begin(), t.end(), [](const ID& a, const ID& b) {
+    std::sort(coverIDs.begin(), coverIDs.end(), [](const CoverID& a, const CoverID& b) {
         return std::tie(a.sqDist, a.x, a.y) < std::tie(b.sqDist, b.x, b.y);
     });
 
     // Erase duplicate tile IDs (they typically occur at the common side of both triangles).
-    t.erase(std::unique(t.begin(), t.end(), [](const ID& a, const ID& b) {
+    coverIDs.erase(std::unique(coverIDs.begin(), coverIDs.end(), [](const CoverID& a, const CoverID& b) {
                 return a.x == b.x && a.y == b.y;
-            }), t.end());
+            }), coverIDs.end());
 
     std::vector<UnwrappedTileID> result;
-    for (const auto& id : t) {
-        result.emplace_back(zoom, id.x, id.y);
+    result.reserve(coverIDs.size());
+    for (const auto& coverID : coverIDs) {
+        result.emplace_back(zoom, coverID.x, coverID.y);
     }
     return result;
 }