partially do Placement asyncupstream/start-collision-async

19 files changed, 422 insertions, 225 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index 4e35e12ee8..ea3cb0d553 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -495,6 +495,8 @@ set(MBGL_CORE_FILES
     src/mbgl/text/glyph_range.hpp
     src/mbgl/text/placement.cpp
     src/mbgl/text/placement.hpp
+    src/mbgl/text/placement_worker.cpp
+    src/mbgl/text/placement_worker.hpp
     src/mbgl/text/quads.cpp
     src/mbgl/text/quads.hpp
     src/mbgl/text/shaping.cpp
diff --git a/src/mbgl/layout/symbol_instance.hpp b/src/mbgl/layout/symbol_instance.hpp
index 827a5dbbdb..a4dd837559 100644
--- a/src/mbgl/layout/symbol_instance.hpp
+++ b/src/mbgl/layout/symbol_instance.hpp
@@ -52,7 +52,6 @@ public:
     optional<size_t> placedTextIndex;
     optional<size_t> placedVerticalTextIndex;
     optional<size_t> placedIconIndex;
-    uint32_t crossTileID = 0;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index 09d8883544..0946f606b5 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -423,7 +423,11 @@ std::unique_ptr<SymbolBucket> SymbolLayout::place(const bool showCollisionBoxes)
     
     auto bucket = std::make_unique<SymbolBucket>(layout, layerPaintProperties, textSize, iconSize, zoom, sdfIcons, iconsNeedLinear, mayOverlap, std::move(symbolInstances));
 
-    for (SymbolInstance &symbolInstance : bucket->symbolInstances) {
+    auto& core = *bucket->mutableCore;
+    auto& placedTextSymbols = core.placedTextSymbols;
+    auto& placedIconSymbols = core.placedIconSymbols;
+
+    for (SymbolInstance &symbolInstance : bucket->mutableCore->symbolInstances) {
 
         const bool hasText = symbolInstance.hasText;
         const bool hasIcon = symbolInstance.hasIcon;
@@ -433,11 +437,11 @@ std::unique_ptr<SymbolBucket> SymbolLayout::place(const bool showCollisionBoxes)
         // Insert final placement into collision tree and add glyphs/icons to buffers
 
         if (hasText) {
-            const Range<float> sizeData = bucket->textSizeBinder->getVertexSizeData(feature);
-            bucket->text.placedSymbols.emplace_back(symbolInstance.anchor.point, symbolInstance.anchor.segment, sizeData.min, sizeData.max,
+            const Range<float> sizeData = core.textSizeBinder->getVertexSizeData(feature);
+            placedTextSymbols.emplace_back(symbolInstance.anchor.point, symbolInstance.anchor.segment, sizeData.min, sizeData.max,
                     symbolInstance.textOffset, symbolInstance.writingModes, symbolInstance.line, CalculateTileDistances(symbolInstance.line, symbolInstance.anchor));
-            symbolInstance.placedTextIndex = bucket->text.placedSymbols.size() - 1;
-            PlacedSymbol& horizontalSymbol = bucket->text.placedSymbols.back();
+            symbolInstance.placedTextIndex = placedTextSymbols.size() - 1;
+            PlacedSymbol& horizontalSymbol = placedTextSymbols.back();
 
             bool firstHorizontal = true;
             for (const auto& symbol : symbolInstance.horizontalGlyphQuads) {
@@ -451,11 +455,10 @@ std::unique_ptr<SymbolBucket> SymbolLayout::place(const bool showCollisionBoxes)
             }
             
             if (symbolInstance.writingModes & WritingModeType::Vertical) {
-                bucket->text.placedSymbols.emplace_back(symbolInstance.anchor.point, symbolInstance.anchor.segment, sizeData.min, sizeData.max,
+                placedTextSymbols.emplace_back(symbolInstance.anchor.point, symbolInstance.anchor.segment, sizeData.min, sizeData.max,
                         symbolInstance.textOffset, WritingModeType::Vertical, symbolInstance.line, CalculateTileDistances(symbolInstance.line, symbolInstance.anchor));
-                symbolInstance.placedVerticalTextIndex = bucket->text.placedSymbols.size() - 1;
-                
-                PlacedSymbol& verticalSymbol = bucket->text.placedSymbols.back();
+                symbolInstance.placedVerticalTextIndex = placedTextSymbols.size() - 1;
+                PlacedSymbol& verticalSymbol = placedTextSymbols.back();
                 bool firstVertical = true;
                 
                 for (const auto& symbol : symbolInstance.verticalGlyphQuads) {
@@ -473,11 +476,11 @@ std::unique_ptr<SymbolBucket> SymbolLayout::place(const bool showCollisionBoxes)
 
         if (hasIcon) {
             if (symbolInstance.iconQuad) {
-                const Range<float> sizeData = bucket->iconSizeBinder->getVertexSizeData(feature);
-                bucket->icon.placedSymbols.emplace_back(symbolInstance.anchor.point, symbolInstance.anchor.segment, sizeData.min, sizeData.max,
+                const Range<float> sizeData = core.iconSizeBinder->getVertexSizeData(feature);
+                placedIconSymbols.emplace_back(symbolInstance.anchor.point, symbolInstance.anchor.segment, sizeData.min, sizeData.max,
                         symbolInstance.iconOffset, WritingModeType::None, symbolInstance.line, std::vector<float>());
-                symbolInstance.placedIconIndex = bucket->icon.placedSymbols.size() - 1;
-                PlacedSymbol& iconSymbol = bucket->icon.placedSymbols.back();
+                symbolInstance.placedIconIndex = placedIconSymbols.size() - 1;
+                PlacedSymbol& iconSymbol = placedIconSymbols.back();
                 iconSymbol.vertexStartIndex = addSymbol(
                                                         bucket->icon, sizeData, *symbolInstance.iconQuad,
                                                         symbolInstance.anchor, iconSymbol);
@@ -490,10 +493,15 @@ std::unique_ptr<SymbolBucket> SymbolLayout::place(const bool showCollisionBoxes)
         }
     }
 
+    core.hasTextData = bucket->hasTextData();
+    core.hasIconData = bucket->hasIconData();
+
     if (showCollisionBoxes) {
         addToDebugBuffers(*bucket);
     }
 
+    bucket->core = std::make_unique<Immutable<SymbolBucket::Core>>(std::move(bucket->mutableCore));
+
     return bucket;
 }
 
@@ -555,11 +563,7 @@ size_t SymbolLayout::addSymbol(Buffer& buffer,
 
 void SymbolLayout::addToDebugBuffers(SymbolBucket& bucket) {
 
-    if (!hasSymbolInstances()) {
-        return;
-    }
-
-    for (const SymbolInstance &symbolInstance : symbolInstances) {
+    for (const SymbolInstance &symbolInstance : bucket.mutableCore->symbolInstances) {
         auto populateCollisionBox = [&](const auto& feature) {
             SymbolBucket::CollisionBuffer& collisionBuffer = feature.alongLine ?
                 static_cast<SymbolBucket::CollisionBuffer&>(bucket.collisionCircle) :
diff --git a/src/mbgl/layout/symbol_projection.cpp b/src/mbgl/layout/symbol_projection.cpp
index fa88ffdf22..393ae1f808 100644
--- a/src/mbgl/layout/symbol_projection.cpp
+++ b/src/mbgl/layout/symbol_projection.cpp
@@ -353,7 +353,8 @@ namespace mbgl {
     }
 
 
-    void reprojectLineLabels(gl::VertexVector<SymbolDynamicLayoutAttributes::Vertex>& dynamicVertexArray, const std::vector<PlacedSymbol>& placedSymbols,
+    void reprojectLineLabels(gl::VertexVector<SymbolDynamicLayoutAttributes::Vertex>& dynamicVertexArray,
+            const std::vector<PlacedSymbol>& placedSymbols, const std::vector<bool>& placedSymbolVisibility,
 			const mat4& posMatrix, const style::SymbolPropertyValues& values,
             const RenderTile& tile, const SymbolSizeBinder& sizeBinder, const TransformState& state) {
 
@@ -374,11 +375,17 @@ namespace mbgl {
         
         bool useVertical = false;
 
-        for (auto& placedSymbol : placedSymbols) {
+        assert(placedSymbols.size() == placedSymbolVisibility.size());
+        auto visibilityIt = placedSymbolVisibility.begin();
+        for (auto it = placedSymbols.begin(); it != placedSymbols.end(); it++, visibilityIt++) {
+
+            const PlacedSymbol& placedSymbol = *it;
+            const bool hidden = *visibilityIt;
+
             // Don't do calculations for vertical glyphs unless the previous symbol was horizontal
             // and we determined that vertical glyphs were necessary.
             // Also don't do calculations for symbols that are collided and fully faded out
-            if (placedSymbol.hidden || (placedSymbol.writingModes == WritingModeType::Vertical && !useVertical)) {
+            if (hidden || (placedSymbol.writingModes == WritingModeType::Vertical && !useVertical)) {
                 hideGlyphs(placedSymbol.glyphOffsets.size(), dynamicVertexArray);
                 continue;
             }
diff --git a/src/mbgl/layout/symbol_projection.hpp b/src/mbgl/layout/symbol_projection.hpp
index 8535014f22..19fa6517ae 100644
--- a/src/mbgl/layout/symbol_projection.hpp
+++ b/src/mbgl/layout/symbol_projection.hpp
@@ -38,7 +38,8 @@ namespace mbgl {
     using PointAndCameraDistance = std::pair<Point<float>,float>;
     PointAndCameraDistance project(const Point<float>& point, const mat4& matrix);
 
-    void reprojectLineLabels(gl::VertexVector<SymbolDynamicLayoutAttributes::Vertex>&, const std::vector<PlacedSymbol>&,
+    void reprojectLineLabels(gl::VertexVector<SymbolDynamicLayoutAttributes::Vertex>&,
+            const std::vector<PlacedSymbol>&, const std::vector<bool>&,
             const mat4& posMatrix, const style::SymbolPropertyValues&,
             const RenderTile&, const SymbolSizeBinder& sizeBinder, const TransformState&);
     
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp
index ebcf93f2b1..fbed45c25e 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.cpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp
@@ -8,6 +8,17 @@ namespace mbgl {
 
 using namespace style;
 
+SymbolBucket::Core::Core(
+        std::vector<SymbolInstance>&& symbolInstances_,
+        style::SymbolLayoutProperties::PossiblyEvaluated layout_,
+        std::unique_ptr<SymbolSizeBinder> textSizeBinder_,
+        std::unique_ptr<SymbolSizeBinder> iconSizeBinder_) :
+    symbolInstances(std::move(symbolInstances_)),
+    layout(std::move(layout_)),
+    textSizeBinder(std::move(textSizeBinder_)),
+    iconSizeBinder(std::move(iconSizeBinder_))
+    {}
+
 SymbolBucket::SymbolBucket(style::SymbolLayoutProperties::PossiblyEvaluated layout_,
                            const std::map<std::string, std::pair<
                                style::IconPaintProperties::PossiblyEvaluated,
@@ -18,14 +29,16 @@ SymbolBucket::SymbolBucket(style::SymbolLayoutProperties::PossiblyEvaluated layo
                            bool sdfIcons_,
                            bool iconsNeedLinear_,
                            bool sortFeaturesByY_,
-                           const std::vector<SymbolInstance>&& symbolInstances_)
-    : layout(std::move(layout_)),
-      sdfIcons(sdfIcons_),
+                           std::vector<SymbolInstance>&& symbolInstances_)
+    : sdfIcons(sdfIcons_),
       iconsNeedLinear(iconsNeedLinear_ || iconSize.isDataDriven() || !iconSize.isZoomConstant()),
       sortFeaturesByY(sortFeaturesByY_),
-      symbolInstances(std::move(symbolInstances_)),
-      textSizeBinder(SymbolSizeBinder::create(zoom, textSize, TextSize::defaultValue())),
-      iconSizeBinder(SymbolSizeBinder::create(zoom, iconSize, IconSize::defaultValue())) {
+      mutableCore(makeMutable<Core>(
+                  std::move(symbolInstances_),
+                  std::move(layout_),
+                  SymbolSizeBinder::create(zoom, textSize, TextSize::defaultValue()),
+                  SymbolSizeBinder::create(zoom, iconSize, IconSize::defaultValue())
+                  )) {
     
     for (const auto& pair : layerPaintProperties) {
         paintPropertyBinders.emplace(
@@ -177,6 +190,10 @@ void SymbolBucket::sortFeatures(const float angle) {
     // The index array buffer is rewritten to reference the (unchanged) vertices in the
     // sorted order.
 
+    auto& symbolInstances = (*core)->symbolInstances;
+    auto& placedTextSymbols = (*core)->placedTextSymbols;
+    auto& placedIconSymbols = (*core)->placedIconSymbols;
+
     // To avoid sorting the actual symbolInstance array we sort an array of indexes.
     std::vector<size_t> symbolInstanceIndexes;
     for (size_t i = 0; i < symbolInstances.size(); i++) {
@@ -186,9 +203,9 @@ void SymbolBucket::sortFeatures(const float angle) {
     const float sin = std::sin(angle);
     const float cos = std::cos(angle);
 
-    std::sort(symbolInstanceIndexes.begin(), symbolInstanceIndexes.end(), [sin, cos, this](size_t &aIndex, size_t &bIndex) {
-        const SymbolInstance& a = symbolInstances[aIndex];
-        const SymbolInstance& b = symbolInstances[bIndex];
+    std::sort(symbolInstanceIndexes.begin(), symbolInstanceIndexes.end(), [sin, cos, symbolInstances](size_t &aIndex, size_t &bIndex) {
+        const SymbolInstance& a = symbolInstances.at(aIndex);
+        const SymbolInstance& b = symbolInstances.at(bIndex);
         const int32_t aRotated = sin * a.anchor.point.x + cos * a.anchor.point.y;
         const int32_t bRotated = sin * b.anchor.point.x + cos * b.anchor.point.y;
         return aRotated != bRotated ?
@@ -200,16 +217,16 @@ void SymbolBucket::sortFeatures(const float angle) {
     icon.triangles.clear();
 
     for (auto i : symbolInstanceIndexes) {
-        const SymbolInstance& symbolInstance = symbolInstances[i];
+        const SymbolInstance& symbolInstance = symbolInstances.at(i);
 
         if (symbolInstance.placedTextIndex) {
-            addPlacedSymbol(text.triangles, text.placedSymbols[*symbolInstance.placedTextIndex]);
+            addPlacedSymbol(text.triangles, placedTextSymbols[*symbolInstance.placedTextIndex]);
         }
         if (symbolInstance.placedVerticalTextIndex) {
-            addPlacedSymbol(text.triangles, text.placedSymbols[*symbolInstance.placedVerticalTextIndex]);
+            addPlacedSymbol(text.triangles, placedTextSymbols[*symbolInstance.placedVerticalTextIndex]);
         }
         if (symbolInstance.placedIconIndex) {
-            addPlacedSymbol(icon.triangles, icon.placedSymbols[*symbolInstance.placedIconIndex]);
+            addPlacedSymbol(icon.triangles, placedIconSymbols[*symbolInstance.placedIconIndex]);
         }
     }
 }
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.hpp b/src/mbgl/renderer/buckets/symbol_bucket.hpp
index 4abea90508..f2f3f6197c 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.hpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp
@@ -21,7 +21,7 @@ public:
     PlacedSymbol(Point<float> anchorPoint_, uint16_t segment_, float lowerSize_, float upperSize_,
             std::array<float, 2> lineOffset_, WritingModeType writingModes_, GeometryCoordinates line_, std::vector<float> tileDistances_) :
         anchorPoint(anchorPoint_), segment(segment_), lowerSize(lowerSize_), upperSize(upperSize_),
-        lineOffset(lineOffset_), writingModes(writingModes_), line(std::move(line_)), tileDistances(std::move(tileDistances_)), hidden(false), vertexStartIndex(0)
+        lineOffset(lineOffset_), writingModes(writingModes_), line(std::move(line_)), tileDistances(std::move(tileDistances_)), vertexStartIndex(0)
     {
     }
     Point<float> anchorPoint;
@@ -33,7 +33,6 @@ public:
     GeometryCoordinates line;
     std::vector<float> tileDistances;
     std::vector<float> glyphOffsets;
-    bool hidden;
     size_t vertexStartIndex;
 };
 
@@ -47,7 +46,7 @@ public:
                  bool sdfIcons,
                  bool iconsNeedLinear,
                  bool sortFeaturesByY,
-                 const std::vector<SymbolInstance>&&);
+                 std::vector<SymbolInstance>&&);
 
     void upload(gl::Context&) override;
     bool hasData() const override;
@@ -59,7 +58,6 @@ public:
     void updateOpacity();
     void sortFeatures(const float angle);
 
-    const style::SymbolLayoutProperties::PossiblyEvaluated layout;
     const bool sdfIcons;
     const bool iconsNeedLinear;
     const bool sortFeaturesByY;
@@ -71,21 +69,35 @@ public:
     bool dynamicUploaded = false;
     bool sortUploaded = false;
 
-    std::vector<SymbolInstance> symbolInstances;
+    std::unique_ptr<Immutable<std::vector<uint32_t>>> symbolCrossTileIDs;
+
+    class Core {
+        public:
+        Core(std::vector<SymbolInstance>&&, style::SymbolLayoutProperties::PossiblyEvaluated, std::unique_ptr<SymbolSizeBinder>, std::unique_ptr<SymbolSizeBinder>);
+        std::vector<SymbolInstance> symbolInstances;
+        const style::SymbolLayoutProperties::PossiblyEvaluated layout;
+        const std::unique_ptr<SymbolSizeBinder> textSizeBinder;
+        const std::unique_ptr<SymbolSizeBinder> iconSizeBinder;
+        std::vector<PlacedSymbol> placedTextSymbols;
+        std::vector<PlacedSymbol> placedIconSymbols;
+        bool hasTextData;
+        bool hasIconData;
+    };
+
+    Mutable<Core> mutableCore;
+    std::unique_ptr<Immutable<Core>> core;
 
     std::map<std::string, std::pair<
         SymbolIconProgram::PaintPropertyBinders,
         SymbolSDFTextProgram::PaintPropertyBinders>> paintPropertyBinders;
     
-    std::unique_ptr<SymbolSizeBinder> textSizeBinder;
-
     struct TextBuffer {
         gl::VertexVector<SymbolLayoutVertex> vertices;
         gl::VertexVector<SymbolDynamicLayoutAttributes::Vertex> dynamicVertices;
         gl::VertexVector<SymbolOpacityAttributes::Vertex> opacityVertices;
         gl::IndexVector<gl::Triangles> triangles;
         SegmentVector<SymbolTextAttributes> segments;
-        std::vector<PlacedSymbol> placedSymbols;
+        std::vector<bool> placedSymbolVisibility;
 
         optional<gl::VertexBuffer<SymbolLayoutVertex>> vertexBuffer;
         optional<gl::VertexBuffer<SymbolDynamicLayoutAttributes::Vertex>> dynamicVertexBuffer;
@@ -93,15 +105,13 @@ public:
         optional<gl::IndexBuffer<gl::Triangles>> indexBuffer;
     } text;
     
-    std::unique_ptr<SymbolSizeBinder> iconSizeBinder;
-    
     struct IconBuffer {
         gl::VertexVector<SymbolLayoutVertex> vertices;
         gl::VertexVector<SymbolDynamicLayoutAttributes::Vertex> dynamicVertices;
         gl::VertexVector<SymbolOpacityAttributes::Vertex> opacityVertices;
         gl::IndexVector<gl::Triangles> triangles;
         SegmentVector<SymbolIconAttributes> segments;
-        std::vector<PlacedSymbol> placedSymbols;
+        std::vector<bool> placedSymbolVisibility;
         PremultipliedImage atlasImage;
 
         optional<gl::VertexBuffer<SymbolLayoutVertex>> vertexBuffer;
diff --git a/src/mbgl/renderer/layers/render_symbol_layer.cpp b/src/mbgl/renderer/layers/render_symbol_layer.cpp
index e194c9c857..9a3aceed77 100644
--- a/src/mbgl/renderer/layers/render_symbol_layer.cpp
+++ b/src/mbgl/renderer/layers/render_symbol_layer.cpp
@@ -78,7 +78,8 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
         assert(dynamic_cast<SymbolBucket*>(tile.tile.getBucket(*baseImpl)));
         SymbolBucket& bucket = *reinterpret_cast<SymbolBucket*>(tile.tile.getBucket(*baseImpl));
 
-        const auto& layout = bucket.layout;
+        const auto& core = **bucket.core;
+        const auto& layout = core.layout;
 
         auto draw = [&] (auto& program,
                          auto&& uniformValues,
@@ -127,11 +128,12 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
 
             if (alongLine) {
                 reprojectLineLabels(bucket.icon.dynamicVertices,
-                                    bucket.icon.placedSymbols,
+                                    core.placedIconSymbols,
+                                    bucket.icon.placedSymbolVisibility,
                                     tile.matrix,
                                     values,
                                     tile,
-                                    *bucket.iconSizeBinder,
+                                    *core.iconSizeBinder,
                                     parameters.state);
 
                 parameters.context.updateVertexBuffer(*bucket.icon.dynamicVertexBuffer, std::move(bucket.icon.dynamicVertices));
@@ -151,7 +153,7 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
                     draw(parameters.programs.symbolIconSDF,
                          SymbolSDFIconProgram::uniformValues(false, values, texsize, parameters.pixelsToGLUnits, alongLine, tile, parameters.state, parameters.symbolFadeChange, SymbolSDFPart::Halo),
                          bucket.icon,
-                         bucket.iconSizeBinder,
+                         core.iconSizeBinder,
                          values,
                          bucket.paintPropertyBinders.at(getID()).first,
                          paintPropertyValues);
@@ -161,7 +163,7 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
                     draw(parameters.programs.symbolIconSDF,
                          SymbolSDFIconProgram::uniformValues(false, values, texsize, parameters.pixelsToGLUnits, alongLine, tile, parameters.state, parameters.symbolFadeChange, SymbolSDFPart::Fill),
                          bucket.icon,
-                         bucket.iconSizeBinder,
+                         core.iconSizeBinder,
                          values,
                          bucket.paintPropertyBinders.at(getID()).first,
                          paintPropertyValues);
@@ -170,7 +172,7 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
                 draw(parameters.programs.symbolIcon,
                      SymbolIconProgram::uniformValues(false, values, texsize, parameters.pixelsToGLUnits, alongLine, tile, parameters.state, parameters.symbolFadeChange),
                      bucket.icon,
-                     bucket.iconSizeBinder,
+                     core.iconSizeBinder,
                      values,
                      bucket.paintPropertyBinders.at(getID()).first,
                      paintPropertyValues);
@@ -188,11 +190,12 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
 
             if (alongLine) {
                 reprojectLineLabels(bucket.text.dynamicVertices,
-                                    bucket.text.placedSymbols,
+                                    core.placedTextSymbols,
+                                    bucket.text.placedSymbolVisibility,
                                     tile.matrix,
                                     values,
                                     tile,
-                                    *bucket.textSizeBinder,
+                                    *core.textSizeBinder,
                                     parameters.state);
 
                 parameters.context.updateVertexBuffer(*bucket.text.dynamicVertexBuffer, std::move(bucket.text.dynamicVertices));
@@ -204,7 +207,7 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
                 draw(parameters.programs.symbolGlyph,
                      SymbolSDFTextProgram::uniformValues(true, values, texsize, parameters.pixelsToGLUnits, alongLine, tile, parameters.state, parameters.symbolFadeChange, SymbolSDFPart::Halo),
                      bucket.text,
-                     bucket.textSizeBinder,
+                     core.textSizeBinder,
                      values,
                      bucket.paintPropertyBinders.at(getID()).second,
                      paintPropertyValues);
@@ -214,7 +217,7 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
                 draw(parameters.programs.symbolGlyph,
                      SymbolSDFTextProgram::uniformValues(true, values, texsize, parameters.pixelsToGLUnits, alongLine, tile, parameters.state, parameters.symbolFadeChange, SymbolSDFPart::Fill),
                      bucket.text,
-                     bucket.textSizeBinder,
+                     core.textSizeBinder,
                      values,
                      bucket.paintPropertyBinders.at(getID()).second,
                      paintPropertyValues);
diff --git a/src/mbgl/renderer/renderer_impl.cpp b/src/mbgl/renderer/renderer_impl.cpp
index af0c491e15..ddd5718601 100644
--- a/src/mbgl/renderer/renderer_impl.cpp
+++ b/src/mbgl/renderer/renderer_impl.cpp
@@ -59,7 +59,7 @@ Renderer::Impl::Impl(RendererBackend& backend_,
     , layerImpls(makeMutable<std::vector<Immutable<style::Layer::Impl>>>())
     , renderLight(makeMutable<Light::Impl>())
     , crossTileSymbolIndex(std::make_unique<CrossTileSymbolIndex>())
-    , placement(std::make_unique<Placement>(TransformState{}, MapMode::Still)) {
+    , placement(std::make_unique<Placement>(TransformState{}, MapMode::Still, mat4(), false, scheduler_)) {
     glyphManager->setObserver(this);
 }
 
@@ -376,21 +376,30 @@ void Renderer::Impl::render(const UpdateParameters& updateParameters) {
         }
     }
 
-    bool placementChanged = false;
     if (!placement->stillRecent(parameters.timePoint)) {
-        auto newPlacement = std::make_unique<Placement>(parameters.state, parameters.mapMode);
-        for (auto it = order.rbegin(); it != order.rend(); ++it) {
-            if (it->layer.is<RenderSymbolLayer>()) {
-                newPlacement->placeLayer(*it->layer.as<RenderSymbolLayer>(), parameters.projMatrix, parameters.debugOptions & MapDebugOptions::Collision);
+        if (!placementInProgress) {
+            placementInProgress = std::make_unique<Placement>(parameters.state, parameters.mapMode, parameters.projMatrix, parameters.debugOptions & MapDebugOptions::Collision, scheduler);
+            for (auto it = order.rbegin(); it != order.rend(); ++it) {
+                if (it->layer.is<RenderSymbolLayer>()) {
+                    placementInProgress->addLayer(*it->layer.as<RenderSymbolLayer>());
+                }
             }
+            placementInProgress->place();
         }
+    }
 
-        placementChanged = newPlacement->commit(*placement, parameters.timePoint);
-        if (placementChanged || symbolBucketsChanged) {
-            placement = std::move(newPlacement);
+    bool placementChanged = false;
+    if (placementInProgress) {
+        if (placementInProgress->isReady()) {
+            placementChanged = placementInProgress->commit(*placement, parameters.timePoint);
+            if (placementChanged || symbolBucketsChanged) {
+                placement = std::move(placementInProgress);
+                placement->setStale();
+            } else {
+                placement->setRecent(parameters.timePoint);
+                placementInProgress.reset();
+            }
         }
-
-        placement->setRecent(parameters.timePoint);
     } else {
         placement->setStale();
     }
@@ -654,7 +663,7 @@ std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin
     std::unordered_map<std::string, std::vector<Feature>> resultsByLayer;
     for (const auto& sourceID : sourceIDs) {
         if (RenderSource* renderSource = getRenderSource(sourceID)) {
-            auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options, placement->collisionIndex);
+            auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options, placement->result->collisionIndex);
             std::move(sourceResults.begin(), sourceResults.end(), std::inserter(resultsByLayer, resultsByLayer.begin()));
         }
     }
@@ -730,7 +739,7 @@ bool Renderer::Impl::hasTransitions(TimePoint timePoint) const {
         }
     }
 
-    if (placement->hasTransitions(timePoint)) {
+    if (placement->hasTransitions(timePoint) || placementInProgress) {
         return true;
     }
 
diff --git a/src/mbgl/renderer/renderer_impl.hpp b/src/mbgl/renderer/renderer_impl.hpp
index dc19e84995..8e98c63497 100644
--- a/src/mbgl/renderer/renderer_impl.hpp
+++ b/src/mbgl/renderer/renderer_impl.hpp
@@ -107,6 +107,7 @@ private:
 
     std::unique_ptr<CrossTileSymbolIndex> crossTileSymbolIndex;
     std::unique_ptr<Placement> placement;
+    std::unique_ptr<Placement> placementInProgress;
 
     bool contextLost = false;
 };
diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
index 05a0450465..08910fa619 100644
--- a/src/mbgl/text/collision_index.cpp
+++ b/src/mbgl/text/collision_index.cpp
@@ -56,7 +56,7 @@ bool CollisionIndex::placeFeature(CollisionFeature& feature,
                                       const mat4& posMatrix,
                                       const mat4& labelPlaneMatrix,
                                       const float textPixelRatio,
-                                      PlacedSymbol& symbol,
+                                      const PlacedSymbol& symbol,
                                       const float scale,
                                       const float fontSize,
                                       const bool allowOverlap,
@@ -87,7 +87,7 @@ bool CollisionIndex::placeLineFeature(CollisionFeature& feature,
                                       const mat4& posMatrix,
                                       const mat4& labelPlaneMatrix,
                                       const float textPixelRatio,
-                                      PlacedSymbol& symbol,
+                                      const PlacedSymbol& symbol,
                                       const float scale,
                                       const float fontSize,
                                       const bool allowOverlap,
@@ -201,7 +201,7 @@ bool CollisionIndex::placeLineFeature(CollisionFeature& feature,
 }
 
 
-void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement) {
+void CollisionIndex::insertFeature(const CollisionFeature& feature, bool ignorePlacement) {
     if (feature.alongLine) {
         for (auto& circle : feature.boxes) {
             if (!circle.used) {
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index 6f78d8aeda..7eab7b5c28 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -21,14 +21,14 @@ public:
                                       const mat4& posMatrix,
                                       const mat4& labelPlaneMatrix,
                                       const float textPixelRatio,
-                                      PlacedSymbol& symbol,
+                                      const PlacedSymbol& symbol,
                                       const float scale,
                                       const float fontSize,
                                       const bool allowOverlap,
                                       const bool pitchWithMap,
                                       const bool collisionDebug);
 
-    void insertFeature(CollisionFeature& feature, bool ignorePlacement);
+    void insertFeature(const CollisionFeature& feature, bool ignorePlacement);
 
     std::vector<IndexedSubfeature> queryRenderedSymbols(const GeometryCoordinates&, const UnwrappedTileID& tileID, const std::string& sourceID) const;
 
@@ -38,7 +38,7 @@ private:
                                   const mat4& posMatrix,
                                   const mat4& labelPlaneMatrix,
                                   const float textPixelRatio,
-                                  PlacedSymbol& symbol,
+                                  const PlacedSymbol& symbol,
                                   const float scale,
                                   const float fontSize,
                                   const bool allowOverlap,
diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp
index 779bec283c..f701b47694 100644
--- a/src/mbgl/text/cross_tile_symbol_index.cpp
+++ b/src/mbgl/text/cross_tile_symbol_index.cpp
@@ -7,14 +7,18 @@
 namespace mbgl {
 
 
-TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, std::vector<SymbolInstance>& symbolInstances, uint32_t bucketInstanceId_)
+TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, const std::vector<SymbolInstance>& symbolInstances, std::vector<uint32_t>& symbolCrossTileIDs, uint32_t bucketInstanceId_)
     : coord(coord_), bucketInstanceId(bucketInstanceId_) {
-        for (SymbolInstance& symbolInstance : symbolInstances) {
-            indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, getScaledCoordinates(symbolInstance, coord));
+        assert(symbolInstances.size() == symbolCrossTileIDs.size());
+        auto idIt = symbolCrossTileIDs.begin();
+        for (auto it = symbolInstances.begin(); it != symbolInstances.end(); it++, idIt++) {
+            auto& symbolInstance = *it;
+            auto crossTileID = *idIt;
+            indexedSymbolInstances[symbolInstance.key].emplace_back(crossTileID, getScaledCoordinates(symbolInstance, coord));
         }
     }
 
-Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, const OverscaledTileID& childTileCoord) {
+Point<int64_t> TileLayerIndex::getScaledCoordinates(const 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,30 +28,34 @@ Point<int64_t> TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstan
     };
 }
 
-void TileLayerIndex::findMatches(std::vector<SymbolInstance>& symbolInstances, const OverscaledTileID& newCoord) {
+void TileLayerIndex::findMatches(const std::vector<SymbolInstance>& symbolInstances, std::vector<uint32_t>& symbolCrossTileIDs, const OverscaledTileID& newCoord) {
     float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z);
 
-    for (auto& symbolInstance : symbolInstances) {
-        if (symbolInstance.crossTileID) {
+    assert(symbolInstances.size() == symbolCrossTileIDs.size());
+    auto idIt = symbolCrossTileIDs.begin();
+    for (auto it = symbolInstances.begin(); it != symbolInstances.end(); it++, idIt++) {
+        auto& symbolInstance = *it;
+        auto& crossTileID = *idIt;
+        if (crossTileID) {
             // already has a match, skip
             continue;
         }
 
-        auto it = indexedSymbolInstances.find(symbolInstance.key);
-        if (it == indexedSymbolInstances.end()) {
+        auto indexedSymbolInstance = indexedSymbolInstances.find(symbolInstance.key);
+        if (indexedSymbolInstance == indexedSymbolInstances.end()) {
             // No symbol with this key in this bucket
             continue;
         }
 
         auto scaledSymbolCoord = getScaledCoordinates(symbolInstance, newCoord);
 
-        for (IndexedSymbolInstance& thisTileSymbol: it->second) {
+        for (IndexedSymbolInstance& thisTileSymbol: indexedSymbolInstance->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 &&
                 std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance) {
 
-                symbolInstance.crossTileID = thisTileSymbol.crossTileID;
+                crossTileID = thisTileSymbol.crossTileID;
                 break;
             }
         }
@@ -63,6 +71,10 @@ void CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& coord, SymbolB
     if (bucket.bucketInstanceId) return;
     bucket.bucketInstanceId = ++maxBucketInstanceId;
 
+    auto& symbolInstances = (*bucket.core)->symbolInstances;
+
+    Mutable<std::vector<uint32_t>> symbolCrossTileIDs = makeMutable<std::vector<uint32_t>>(symbolInstances.size(), 0);
+
     uint8_t minZoom = 25;
     uint8_t maxZoom = 0;
     for (auto& it : indexes) {
@@ -80,7 +92,7 @@ void CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& coord, SymbolB
                 if (!childIndex.second.coord.isChildOf(coord)) {
                     continue;
                 }
-                childIndex.second.findMatches(bucket.symbolInstances, coord);
+                childIndex.second.findMatches(symbolInstances, *symbolCrossTileIDs, coord);
             }
         }
         if (z == 0) {
@@ -95,7 +107,7 @@ void CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& coord, SymbolB
         if (zoomIndexes != indexes.end()) {
             auto parentIndex = zoomIndexes->second.find(parentCoord);
             if (parentIndex != zoomIndexes->second.end()) {
-                parentIndex->second.findMatches(bucket.symbolInstances, coord);
+                parentIndex->second.findMatches(symbolInstances, *symbolCrossTileIDs, coord);
             }
         }
         if (z == 0) {
@@ -103,14 +115,16 @@ void CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& coord, SymbolB
         }
     }
     
-    for (auto& symbolInstance : bucket.symbolInstances) {
-        if (!symbolInstance.crossTileID) {
+    for (auto& crossTileID : *symbolCrossTileIDs) {
+        if (!crossTileID) {
             // symbol did not match any known symbol, assign a new id
-            symbolInstance.crossTileID = ++maxCrossTileID;
+            crossTileID = ++maxCrossTileID;
         }
     }
 
-    indexes[coord.overscaledZ].emplace(coord, TileLayerIndex(coord, bucket.symbolInstances, bucket.bucketInstanceId));
+    indexes[coord.overscaledZ].emplace(coord, TileLayerIndex(coord, symbolInstances, *symbolCrossTileIDs, bucket.bucketInstanceId));
+
+    bucket.symbolCrossTileIDs = std::make_unique<Immutable<std::vector<uint32_t>>>(std::move(symbolCrossTileIDs));
 }
 
 bool CrossTileSymbolLayerIndex::removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs) {
diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp
index 0b8c5c4780..ec0a5677de 100644
--- a/src/mbgl/text/cross_tile_symbol_index.hpp
+++ b/src/mbgl/text/cross_tile_symbol_index.hpp
@@ -32,10 +32,10 @@ class IndexedSymbolInstance {
 
 class TileLayerIndex {
     public:
-        TileLayerIndex(OverscaledTileID coord, std::vector<SymbolInstance>&, uint32_t bucketInstanceId);
+        TileLayerIndex(OverscaledTileID coord, const std::vector<SymbolInstance>&, std::vector<uint32_t>& symbolCrossTileIDs, uint32_t bucketInstanceId);
 
-        Point<int64_t> getScaledCoordinates(SymbolInstance&, const OverscaledTileID&);
-        void findMatches(std::vector<SymbolInstance>&, const OverscaledTileID&);
+        Point<int64_t> getScaledCoordinates(const SymbolInstance&, const OverscaledTileID&) const;
+        void findMatches(const std::vector<SymbolInstance>&, std::vector<uint32_t>& symbolCrossTileIDs, const OverscaledTileID&);
         
         OverscaledTileID coord;
         uint32_t bucketInstanceId;
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index 2a24a803a7..546635c51d 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -30,16 +30,21 @@ bool JointOpacityState::isHidden() const {
     return icon.isHidden() && text.isHidden();
 }
 
-Placement::Placement(const TransformState& state_, MapMode mapMode_)
-    : collisionIndex(state_)
+Placement::Placement(const TransformState& state_, MapMode mapMode_, const mat4& projMatrix_, const bool showCollisionBoxes_, Scheduler& scheduler)
+    : result(makeMutable<PlacementResult>(state_))
     , state(state_)
     , mapMode(mapMode_)
+    , showCollisionBoxes(showCollisionBoxes_)
+    , projMatrix(projMatrix_)
+    , worker(scheduler, state_, projMatrix_, showCollisionBoxes_)
+    , placementBucketLayers(makeMutable<std::vector<std::vector<PlacementBucket>>>())
     , recentUntil(TimePoint::min())
 {}
 
-void Placement::placeLayer(RenderSymbolLayer& symbolLayer, const mat4& projMatrix, bool showCollisionBoxes) {
+void Placement::addLayer(RenderSymbolLayer& symbolLayer) {
 
-    std::unordered_set<uint32_t> seenCrossTileIDs;
+    placementBucketLayers->emplace_back();
+    auto& placementBuckets = placementBucketLayers->back();
 
     for (RenderTile& renderTile : symbolLayer.renderTiles) {
 
@@ -51,111 +56,47 @@ void Placement::placeLayer(RenderSymbolLayer& symbolLayer, const mat4& projMatri
         assert(dynamic_cast<SymbolBucket*>(bucket));
         SymbolBucket& symbolBucket = *reinterpret_cast<SymbolBucket*>(bucket);
 
-        auto& layout = symbolBucket.layout;
-
-        const float pixelsToTileUnits = renderTile.id.pixelsToTileUnits(1, state.getZoom());
-
-        const float scale = std::pow(2, state.getZoom() - renderTile.tile.id.overscaledZ);
-        const float textPixelRatio = util::EXTENT / (util::tileSize * renderTile.tile.id.overscaleFactor());
-
-        mat4 posMatrix;
-        state.matrixFor(posMatrix, renderTile.id);
-        matrix::multiply(posMatrix, projMatrix, posMatrix);
-
-        mat4 textLabelPlaneMatrix = getLabelPlaneMatrix(renderTile.matrix,
-                layout.get<TextPitchAlignment>() == style::AlignmentType::Map,
-                layout.get<TextRotationAlignment>() == style::AlignmentType::Map,
-                state,
-                pixelsToTileUnits);
-
-        mat4 iconLabelPlaneMatrix = getLabelPlaneMatrix(renderTile.matrix,
-                layout.get<IconPitchAlignment>() == style::AlignmentType::Map,
-                layout.get<IconRotationAlignment>() == style::AlignmentType::Map,
-                state,
-                pixelsToTileUnits);
-
-        placeLayerBucket(symbolBucket, posMatrix, textLabelPlaneMatrix, iconLabelPlaneMatrix, scale, textPixelRatio, showCollisionBoxes, seenCrossTileIDs);
+        assert(symbolBucket.core);
+        placementBuckets.emplace_back(*symbolBucket.core, *symbolBucket.symbolCrossTileIDs, renderTile.id, renderTile.tile.id);
     }
 }
 
-void Placement::placeLayerBucket(
-        SymbolBucket& bucket,
-        const mat4& posMatrix,
-        const mat4& textLabelPlaneMatrix,
-        const mat4& iconLabelPlaneMatrix,
-        const float scale,
-        const float textPixelRatio,
-        const bool showCollisionBoxes,
-        std::unordered_set<uint32_t>& seenCrossTileIDs) {
-
-    auto partiallyEvaluatedTextSize = bucket.textSizeBinder->evaluateForZoom(state.getZoom());
-    auto partiallyEvaluatedIconSize = bucket.iconSizeBinder->evaluateForZoom(state.getZoom());
-
-    const bool iconWithoutText = !bucket.hasTextData() || bucket.layout.get<TextOptional>();
-    const bool textWithoutIcon = !bucket.hasIconData() || bucket.layout.get<IconOptional>();
-
-    for (auto& symbolInstance : bucket.symbolInstances) {
-
-        if (seenCrossTileIDs.count(symbolInstance.crossTileID) == 0) {
-            bool placeText = false;
-            bool placeIcon = false;
-
-            if (symbolInstance.placedTextIndex) {
-                PlacedSymbol& placedSymbol = bucket.text.placedSymbols.at(*symbolInstance.placedTextIndex);
-                const float fontSize = evaluateSizeForFeature(partiallyEvaluatedTextSize, placedSymbol);
-
-                placeText = collisionIndex.placeFeature(symbolInstance.textCollisionFeature,
-                        posMatrix, textLabelPlaneMatrix, textPixelRatio,
-                        placedSymbol, scale, fontSize,
-                        bucket.layout.get<TextAllowOverlap>(),
-                        bucket.layout.get<TextPitchAlignment>() == style::AlignmentType::Map,
-                        showCollisionBoxes);
-            }
-
-            if (symbolInstance.placedIconIndex) {
-                PlacedSymbol& placedSymbol = bucket.icon.placedSymbols.at(*symbolInstance.placedIconIndex);
-                const float fontSize = evaluateSizeForFeature(partiallyEvaluatedIconSize, placedSymbol);
-
-                placeIcon = collisionIndex.placeFeature(symbolInstance.iconCollisionFeature,
-                        posMatrix, iconLabelPlaneMatrix, textPixelRatio,
-                        placedSymbol, scale, fontSize,
-                        bucket.layout.get<IconAllowOverlap>(),
-                        bucket.layout.get<IconPitchAlignment>() == style::AlignmentType::Map,
-                        showCollisionBoxes);
-            }
-
-            // combine placements for icon and text
-            if (!iconWithoutText && !textWithoutIcon) {
-                placeText = placeIcon = placeText && placeIcon;
-            } else if (!textWithoutIcon) {
-                placeText = placeText && placeIcon;
-            } else if (!iconWithoutText) {
-                placeIcon = placeText && placeIcon;
-            }
-
-            if (placeText) {
-                collisionIndex.insertFeature(symbolInstance.textCollisionFeature, bucket.layout.get<TextIgnorePlacement>());
-            }
-
-            if (placeIcon) {
-                collisionIndex.insertFeature(symbolInstance.iconCollisionFeature, bucket.layout.get<IconIgnorePlacement>());
-            }
-
-            assert(symbolInstance.crossTileID != 0);
+void Placement::place() {
+    if (mapMode == MapMode::Still) {
+        // synchronous
+        PlacementWorker placement(state, projMatrix, showCollisionBoxes);
+        result = placement.place(std::move(placementBucketLayers));
+    } else {
+        // asynchronous
+        future = worker.ask(&PlacementWorker::place, std::move(placementBucketLayers));
+    }
+}
 
-            placements.emplace(symbolInstance.crossTileID, PlacementPair(placeText, placeIcon));
-            seenCrossTileIDs.insert(symbolInstance.crossTileID);
-        }
-    } 
+bool Placement::isReady() {
+    if (mapMode == MapMode::Still) {
+        // synchronous
+        return true;
+    } else {
+        // asynchronous
+        return future.wait_for(Duration(0)) == std::future_status::ready;
+    }
 }
 
 bool Placement::commit(const Placement& prevPlacement, TimePoint now) {
+
+    if (mapMode != MapMode::Still) {
+        // asynchronous result
+        result = future.get();
+    }
+
     commitTime = now;
 
     bool placementChanged = false;
 
     float increment = mapMode == MapMode::Still ? 1.0 : std::chrono::duration<float>(commitTime - prevPlacement.commitTime) / Duration(std::chrono::milliseconds(300));
 
+    auto& placements = result->placements;
+
     if (increment) {}
     // add the opacities from the current placement, and copy their current values from the previous placement
     for (auto& placementPair : placements) {
@@ -200,17 +141,29 @@ void Placement::updateLayerOpacities(RenderSymbolLayer& symbolLayer) {
 }
 
 void Placement::updateBucketOpacities(SymbolBucket& bucket, std::unordered_set<uint32_t>& seenCrossTileIDs) {
-    if (bucket.hasTextData()) bucket.text.opacityVertices.clear();
-    if (bucket.hasIconData()) bucket.icon.opacityVertices.clear();
+    if (bucket.hasTextData()) {
+        bucket.text.opacityVertices.clear();
+        bucket.text.placedSymbolVisibility.clear();
+    }
+    if (bucket.hasIconData()) {
+        bucket.icon.opacityVertices.clear();
+        bucket.icon.placedSymbolVisibility.clear();
+    }
     if (bucket.hasCollisionBoxData()) bucket.collisionBox.dynamicVertices.clear();
     if (bucket.hasCollisionCircleData()) bucket.collisionCircle.dynamicVertices.clear();
 
-    for (SymbolInstance& symbolInstance : bucket.symbolInstances) {
-        auto opacityState = seenCrossTileIDs.count(symbolInstance.crossTileID) == 0 ?
-            getOpacity(symbolInstance.crossTileID) :
+    auto& symbolInstances = (*bucket.core)->symbolInstances;
+
+    auto idIt = (*bucket.symbolCrossTileIDs)->begin();
+    for (auto it = symbolInstances.begin(); it != symbolInstances.end(); it++, idIt++) {
+        auto& symbolInstance = *it;
+        auto crossTileID = *idIt;
+
+        auto opacityState = seenCrossTileIDs.count(crossTileID) == 0 ?
+            getOpacity(crossTileID) :
             JointOpacityState(false, false);
 
-        seenCrossTileIDs.insert(symbolInstance.crossTileID);
+        seenCrossTileIDs.insert(crossTileID);
 
         if (symbolInstance.hasText) {
             auto opacityVertex = SymbolOpacityAttributes::vertex(opacityState.text.placed, opacityState.text.opacity);
@@ -221,10 +174,10 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, std::unordered_set<u
                 bucket.text.opacityVertices.emplace_back(opacityVertex);
             }
             if (symbolInstance.placedTextIndex) {
-                bucket.text.placedSymbols[*symbolInstance.placedTextIndex].hidden = opacityState.isHidden();
+                bucket.text.placedSymbolVisibility.push_back(opacityState.isHidden());
             }
             if (symbolInstance.placedVerticalTextIndex) {
-                bucket.text.placedSymbols[*symbolInstance.placedVerticalTextIndex].hidden = opacityState.isHidden();
+                bucket.text.placedSymbolVisibility.push_back(opacityState.isHidden());
             }
         }
         if (symbolInstance.hasIcon) {
@@ -236,7 +189,7 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, std::unordered_set<u
                 bucket.icon.opacityVertices.emplace_back(opacityVertex);
             }
             if (symbolInstance.placedIconIndex) {
-                bucket.icon.placedSymbols[*symbolInstance.placedIconIndex].hidden = opacityState.isHidden();
+                bucket.icon.placedSymbolVisibility.push_back(opacityState.isHidden());
             }
         }
         
diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp
index fd36ad25e9..ab8f4e1e5a 100644
--- a/src/mbgl/text/placement.hpp
+++ b/src/mbgl/text/placement.hpp
@@ -2,15 +2,16 @@
 
 #include <string>
 #include <unordered_map>
+#include <mbgl/actor/actor.hpp>
 #include <mbgl/util/chrono.hpp>
-#include <mbgl/text/collision_index.hpp>
+#include <mbgl/text/placement_worker.hpp>
 #include <mbgl/layout/symbol_projection.hpp>
+#include <mbgl/renderer/buckets/symbol_bucket.hpp>
 #include <unordered_set>
 
 namespace mbgl {
 
     class RenderSymbolLayer;
-    class SymbolBucket;
 
     class OpacityState {
         public:
@@ -30,17 +31,12 @@ namespace mbgl {
             OpacityState text;
     };
 
-    class PlacementPair {
-        public:
-            PlacementPair(bool text_, bool icon_) : text(text_), icon(icon_) {}
-            bool text;
-            bool icon;
-    };
-
     class Placement {
         public:
-            Placement(const TransformState&, MapMode mapMode);
-            void placeLayer(RenderSymbolLayer&, const mat4&, bool showCollisionBoxes);
+            Placement(const TransformState&, MapMode mapMode, const mat4& projMatrix, const bool showCollisionBoxes, Scheduler&);
+            void addLayer(RenderSymbolLayer&);
+            void place();
+            bool isReady();
             bool commit(const Placement& prevPlacement, TimePoint);
             void updateLayerOpacities(RenderSymbolLayer&);
             JointOpacityState getOpacity(uint32_t crossTileSymbolID) const;
@@ -48,7 +44,7 @@ namespace mbgl {
             bool hasTransitions(TimePoint now) const;
 
             // TODO: public for queryRenderedFeatures
-            CollisionIndex collisionIndex;
+            Immutable<PlacementResult> result;
         
             bool stillRecent(TimePoint now) const;
             void setRecent(TimePoint now);
@@ -56,22 +52,25 @@ namespace mbgl {
         private:
 
             void placeLayerBucket(
-                    SymbolBucket&,
-                    const mat4& posMatrix,
-                    const mat4& textLabelPlaneMatrix,
-                    const mat4& iconLabelPlaneMatrix,
-                    const float scale,
-                    const float pixelRatio,
-                    const bool showCollisionBoxes,
+                    const SymbolBucket::Core&,
+                    const std::vector<uint32_t>& symbolCrossTileIDs,
+                    const UnwrappedTileID&,
+                    const OverscaledTileID&,
                     std::unordered_set<uint32_t>& seenCrossTileIDs);
 
             void updateBucketOpacities(SymbolBucket&, std::unordered_set<uint32_t>&);
 
             TransformState state;
-            MapMode mapMode;
+            const MapMode mapMode;
             TimePoint commitTime;
+            const bool showCollisionBoxes;
+            const mat4 projMatrix;
+
+            Actor<PlacementWorker> worker;
+            std::future<Immutable<PlacementResult>> future;
+
+            Mutable<std::vector<std::vector<PlacementBucket>>> placementBucketLayers;
 
-            std::unordered_map<uint32_t,PlacementPair> placements;
             std::unordered_map<uint32_t,JointOpacityState> opacities;
         
             TimePoint recentUntil;
diff --git a/src/mbgl/text/placement_worker.cpp b/src/mbgl/text/placement_worker.cpp
new file mode 100644
index 0000000000..041f48e805
--- /dev/null
+++ b/src/mbgl/text/placement_worker.cpp
@@ -0,0 +1,128 @@
+#include <mbgl/text/placement_worker.hpp>
+#include <mbgl/layout/symbol_projection.hpp>
+
+namespace mbgl {
+
+PlacementBucket::PlacementBucket(Immutable<SymbolBucket::Core>& core, Immutable<std::vector<uint32_t>>& ids, const UnwrappedTileID& unwrapped, const OverscaledTileID& overscaled) :
+    symbolBucketCore(core), symbolCrossTileIDs(ids), unwrappedTileID(unwrapped), overscaledTileID(overscaled) {}
+
+PlacementWorker::PlacementWorker(const TransformState& state_, const mat4& projMatrix_, const bool showCollisionBoxes_) :
+    state(state_),
+    projMatrix(projMatrix_),
+    showCollisionBoxes(showCollisionBoxes_)
+    {}
+
+Immutable<PlacementResult> PlacementWorker::place(Immutable<std::vector<std::vector<PlacementBucket>>> placementBucketLayers) {
+    Mutable<PlacementResult> result = makeMutable<PlacementResult>(state);
+
+    for (auto& placementBuckets : *placementBucketLayers) {
+        std::unordered_set<uint32_t> seenCrossTileIDs;
+        for (auto& placementBucket: placementBuckets) {
+            placeLayerBucket(result->placements, result->collisionIndex, *placementBucket.symbolBucketCore, *placementBucket.symbolCrossTileIDs, placementBucket.unwrappedTileID, placementBucket.overscaledTileID, seenCrossTileIDs);
+        }
+    }
+
+    return std::move(result);
+}
+
+void PlacementWorker::placeLayerBucket(
+        std::unordered_map<uint32_t,PlacementPair>& placements,
+        CollisionIndex& collisionIndex,
+        const SymbolBucket::Core& bucketCore,
+        const std::vector<uint32_t>& symbolCrossTileIDs,
+        const UnwrappedTileID& unwrappedTileID,
+        const OverscaledTileID& overscaledTileID,
+        std::unordered_set<uint32_t>& seenCrossTileIDs) {
+
+    const float scale = std::pow(2, state.getZoom() - overscaledTileID.overscaledZ);
+    const float textPixelRatio = util::EXTENT / (util::tileSize * overscaledTileID.overscaleFactor());
+
+    const float pixelsToTileUnits = unwrappedTileID.pixelsToTileUnits(1, state.getZoom());
+
+    mat4 posMatrix;
+    state.matrixFor(posMatrix, unwrappedTileID);
+    matrix::multiply(posMatrix, projMatrix, posMatrix);
+
+    mat4 textLabelPlaneMatrix = getLabelPlaneMatrix(posMatrix,
+            bucketCore.layout.get<style::TextPitchAlignment>() == style::AlignmentType::Map,
+            bucketCore.layout.get<style::TextRotationAlignment>() == style::AlignmentType::Map,
+            state,
+            pixelsToTileUnits);
+
+    mat4 iconLabelPlaneMatrix = getLabelPlaneMatrix(posMatrix,
+            bucketCore.layout.get<style::IconPitchAlignment>() == style::AlignmentType::Map,
+            bucketCore.layout.get<style::IconRotationAlignment>() == style::AlignmentType::Map,
+            state,
+            pixelsToTileUnits);
+
+    auto partiallyEvaluatedTextSize = bucketCore.textSizeBinder->evaluateForZoom(state.getZoom());
+    auto partiallyEvaluatedIconSize = bucketCore.iconSizeBinder->evaluateForZoom(state.getZoom());
+
+    const bool iconWithoutText = !bucketCore.hasTextData || bucketCore.layout.get<style::TextOptional>();
+    const bool textWithoutIcon = !bucketCore.hasIconData || bucketCore.layout.get<style::IconOptional>();
+
+    assert(bucketCore.symbolInstances.size() == symbolCrossTileIDs.size());
+
+    auto idIt = symbolCrossTileIDs.begin();
+    for (auto it = bucketCore.symbolInstances.begin(); it != bucketCore.symbolInstances.end(); it++, idIt++) {
+        auto& symbolInstance = *it;
+        const uint32_t crossTileID = *idIt;
+
+        if (seenCrossTileIDs.count(crossTileID) == 0) {
+            bool placeText = false;
+            bool placeIcon = false;
+
+            // TODO eliminate this copy
+            CollisionFeature textCollisionFeature = symbolInstance.textCollisionFeature;
+            if (symbolInstance.placedTextIndex) {
+                const PlacedSymbol& placedSymbol = bucketCore.placedTextSymbols.at(*symbolInstance.placedTextIndex);
+                const float fontSize = evaluateSizeForFeature(partiallyEvaluatedTextSize, placedSymbol);
+
+                placeText = collisionIndex.placeFeature(textCollisionFeature,
+                        posMatrix, textLabelPlaneMatrix, textPixelRatio,
+                        placedSymbol, scale, fontSize,
+                        bucketCore.layout.get<style::TextAllowOverlap>(),
+                        bucketCore.layout.get<style::TextPitchAlignment>() == style::AlignmentType::Map,
+                        showCollisionBoxes);
+            }
+
+            // TODO eliminate this copy
+            CollisionFeature iconCollisionFeature = symbolInstance.iconCollisionFeature;
+            if (symbolInstance.placedIconIndex) {
+                const PlacedSymbol& placedSymbol = bucketCore.placedIconSymbols.at(*symbolInstance.placedIconIndex);
+                const float fontSize = evaluateSizeForFeature(partiallyEvaluatedIconSize, placedSymbol);
+
+                placeIcon = collisionIndex.placeFeature(iconCollisionFeature,
+                        posMatrix, iconLabelPlaneMatrix, textPixelRatio,
+                        placedSymbol, scale, fontSize,
+                        bucketCore.layout.get<style::IconAllowOverlap>(),
+                        bucketCore.layout.get<style::IconPitchAlignment>() == style::AlignmentType::Map,
+                        showCollisionBoxes);
+            }
+
+            // combine placements for icon and text
+            if (!iconWithoutText && !textWithoutIcon) {
+                placeText = placeIcon = placeText && placeIcon;
+            } else if (!textWithoutIcon) {
+                placeText = placeText && placeIcon;
+            } else if (!iconWithoutText) {
+                placeIcon = placeText && placeIcon;
+            }
+
+            if (placeText) {
+                collisionIndex.insertFeature(textCollisionFeature, bucketCore.layout.get<style::TextIgnorePlacement>());
+            }
+
+            if (placeIcon) {
+                collisionIndex.insertFeature(iconCollisionFeature, bucketCore.layout.get<style::IconIgnorePlacement>());
+            }
+
+            assert(crossTileID != 0);
+
+            placements.emplace(crossTileID, PlacementPair(placeText, placeIcon));
+            seenCrossTileIDs.insert(crossTileID);
+        }
+    }
+}
+
+} // namespace mbgl
diff --git a/src/mbgl/text/placement_worker.hpp b/src/mbgl/text/placement_worker.hpp
new file mode 100644
index 0000000000..86bc16088e
--- /dev/null
+++ b/src/mbgl/text/placement_worker.hpp
@@ -0,0 +1,53 @@
+#pragma once
+
+#include <unordered_map>
+#include <mbgl/util/immutable.hpp>
+#include <mbgl/renderer/buckets/symbol_bucket.hpp>
+#include <mbgl/text/collision_index.hpp>
+
+namespace mbgl {
+
+class PlacementBucket {
+    public:
+        PlacementBucket(Immutable<SymbolBucket::Core>&, Immutable<std::vector<uint32_t>>& ids, const UnwrappedTileID&, const OverscaledTileID&);
+        Immutable<SymbolBucket::Core> symbolBucketCore;
+        Immutable<std::vector<uint32_t>> symbolCrossTileIDs;
+        UnwrappedTileID unwrappedTileID;
+        OverscaledTileID overscaledTileID;
+};
+
+class PlacementPair {
+    public:
+        PlacementPair(bool text_, bool icon_) : text(text_), icon(icon_) {}
+        bool text;
+        bool icon;
+};
+
+class PlacementResult {
+    public:
+        PlacementResult(const TransformState& state) : collisionIndex(state) {}
+        CollisionIndex collisionIndex;
+        std::unordered_map<uint32_t,PlacementPair> placements;
+};
+
+class PlacementWorker {
+    public:
+        PlacementWorker(const TransformState&, const mat4& projMatrix, const bool showCollisionBoxes);
+        Immutable<PlacementResult> place(Immutable<std::vector<std::vector<PlacementBucket>>> placementBucketLayers);
+
+    private:
+        TransformState state;
+        const mat4 projMatrix;
+        const bool showCollisionBoxes;
+
+        void placeLayerBucket(
+                std::unordered_map<uint32_t,PlacementPair>& placements,
+                CollisionIndex& collisionIndex,
+                const SymbolBucket::Core&,
+                const std::vector<uint32_t>& symbolCrossTileIDs,
+                const UnwrappedTileID&,
+                const OverscaledTileID&,
+                std::unordered_set<uint32_t>& seenCrossTileIDs);
+};
+
+} // namespace mbgl
diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
index 576c23b682..c73cdfddd9 100644
--- a/src/mbgl/tile/geometry_tile.cpp
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -287,9 +287,6 @@ void GeometryTile::resetCrossTileIDs() {
         auto symbolBucket = dynamic_cast<SymbolBucket*>(bucket.second.get());
         if (symbolBucket && symbolBucket->bucketInstanceId) {
             symbolBucket->bucketInstanceId = 0;
-            for (auto& symbolInstance : symbolBucket->symbolInstances) {
-                symbolInstance.crossTileID = 0;
-            }
         }
     }
 }