From 9dfc2d924d440560adb2db13c758b2c5b3b7dd47 Mon Sep 17 00:00:00 2001 From: John Firebaugh Date: Wed, 31 May 2017 13:53:48 -0700 Subject: [core] Collection-level immutability Introduce a second level of immutability, over each of the collections held by a style: sources, images, and layers. Tracking immutability at this level allows us to short-circuit significant portions of the RenderStyle update logic via a simple equality check, greatly improving performance. --- cmake/core-files.cmake | 1 + include/mbgl/style/image.hpp | 2 +- include/mbgl/util/immutable.hpp | 15 ++++ src/mbgl/renderer/render_style.cpp | 15 ++-- src/mbgl/renderer/render_style.hpp | 6 +- src/mbgl/renderer/style_diff.cpp | 36 ++++---- src/mbgl/renderer/style_diff.hpp | 12 +-- src/mbgl/renderer/update_parameters.hpp | 6 +- src/mbgl/style/collection.hpp | 141 ++++++++++++++++++++++++++++++++ src/mbgl/style/image.cpp | 10 +-- src/mbgl/style/style.cpp | 130 +++++++++-------------------- src/mbgl/style/style.hpp | 15 ++-- test/sprite/sprite_atlas.test.cpp | 4 +- 13 files changed, 254 insertions(+), 139 deletions(-) create mode 100644 src/mbgl/style/collection.hpp diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake index 47a5d16a1b..44e4f40f19 100644 --- a/cmake/core-files.cmake +++ b/cmake/core-files.cmake @@ -331,6 +331,7 @@ set(MBGL_CORE_FILES include/mbgl/style/transition_options.hpp include/mbgl/style/types.hpp include/mbgl/style/undefined.hpp + src/mbgl/style/collection.hpp src/mbgl/style/image.cpp src/mbgl/style/image_impl.cpp src/mbgl/style/image_impl.hpp diff --git a/include/mbgl/style/image.hpp b/include/mbgl/style/image.hpp index 55760ca503..ff3bfedf46 100644 --- a/include/mbgl/style/image.hpp +++ b/include/mbgl/style/image.hpp @@ -24,7 +24,7 @@ public: bool isSdf() const; class Impl; - Immutable impl; + Immutable baseImpl; }; } // namespace style diff --git a/include/mbgl/util/immutable.hpp b/include/mbgl/util/immutable.hpp index 2cdce8772d..eb26c0d282 100644 --- a/include/mbgl/util/immutable.hpp +++ b/include/mbgl/util/immutable.hpp @@ -115,4 +115,19 @@ Immutable staticImmutableCast(const Immutable& u) { return Immutable(std::static_pointer_cast(u.ptr)); } +/** + * Constrained mutation of an immutable reference. Makes a temporarily-mutable copy of the + * input Immutable using the inner type's copy constructor, runs the given callable on the + * mutable copy, and then freezes the copy and reassigns it to the input reference. + * + * Note that other Immutables referring to the same inner instance are not affected; they + * continue to referencing the original immutable instance. + */ +template +void mutate(Immutable& immutable, Fn&& fn) { + Mutable mut = makeMutable(*immutable); + std::forward(fn)(*mut); + immutable = std::move(mut); +} + } // namespace mbgl diff --git a/src/mbgl/renderer/render_style.cpp b/src/mbgl/renderer/render_style.cpp index a3a7d57527..dc49a20646 100644 --- a/src/mbgl/renderer/render_style.cpp +++ b/src/mbgl/renderer/render_style.cpp @@ -41,6 +41,9 @@ RenderStyle::RenderStyle(Scheduler& scheduler_, FileSource& fileSource_) glyphAtlas(std::make_unique(Size{ 2048, 2048 }, fileSource)), spriteAtlas(std::make_unique()), lineAtlas(std::make_unique(Size{ 256, 512 })), + imageImpls(makeMutable>>()), + sourceImpls(makeMutable>>()), + layerImpls(makeMutable>>()), renderLight(makeMutable()), observer(&nullObserver) { glyphAtlas->setObserver(this); @@ -55,7 +58,7 @@ void RenderStyle::setObserver(RenderStyleObserver* observer_) { std::vector RenderStyle::getRenderLayers() const { std::vector result; result.reserve(renderLayers.size()); - for (const auto& layer : layerImpls) { + for (const auto& layer : *layerImpls) { result.push_back(getRenderLayer(layer->id)); } return result; @@ -189,12 +192,12 @@ void RenderStyle::update(const UpdateParameters& parameters) { } // Update all sources. - for (const auto& source : sourceImpls) { + for (const auto& source : *sourceImpls) { std::vector> filteredLayers; bool needsRendering = false; bool needsRelayout = false; - for (const auto& layer : layerImpls) { + for (const auto& layer : *layerImpls) { if (layer->type == LayerType::Background || layer->type == LayerType::Custom || layer->source != source->id) { @@ -262,7 +265,7 @@ RenderData RenderStyle::getRenderData(MapDebugOptions debugOptions, float angle) } } - for (auto& layerImpl : layerImpls) { + for (auto& layerImpl : *layerImpls) { RenderLayer* layer = getRenderLayer(layerImpl->id); assert(layer); @@ -277,7 +280,7 @@ RenderData RenderStyle::getRenderData(MapDebugOptions debugOptions, float angle) continue; } const BackgroundPaintProperties::PossiblyEvaluated& paint = background->evaluated; - if (layerImpl.get() == layerImpls[0].get() && paint.get().from.empty()) { + if (layerImpl.get() == layerImpls->at(0).get() && paint.get().from.empty()) { // This is a solid background. We can use glClear(). result.backgroundColor = paint.get() * paint.get(); } else { @@ -392,7 +395,7 @@ std::vector RenderStyle::queryRenderedFeatures(const ScreenLineString& } // Combine all results based on the style layer order. - for (const auto& layerImpl : layerImpls) { + for (const auto& layerImpl : *layerImpls) { const RenderLayer* layer = getRenderLayer(layerImpl->id); if (!layer->needsRendering(zoomHistory.lastZoom)) { continue; diff --git a/src/mbgl/renderer/render_style.hpp b/src/mbgl/renderer/render_style.hpp index ff03b48fdf..ff222f2569 100644 --- a/src/mbgl/renderer/render_style.hpp +++ b/src/mbgl/renderer/render_style.hpp @@ -71,9 +71,9 @@ public: std::unique_ptr lineAtlas; private: - std::vector> imageImpls; - std::vector> sourceImpls; - std::vector> layerImpls; + Immutable>> imageImpls; + Immutable>> sourceImpls; + Immutable>> layerImpls; std::unordered_map> renderSources; std::unordered_map> renderLayers; diff --git a/src/mbgl/renderer/style_diff.cpp b/src/mbgl/renderer/style_diff.cpp index e250dfa8d5..cd547f2a0b 100644 --- a/src/mbgl/renderer/style_diff.cpp +++ b/src/mbgl/renderer/style_diff.cpp @@ -7,22 +7,28 @@ namespace mbgl { template -StyleDifference diff(const std::vector& a, const std::vector& b, const Eq& eq) { +StyleDifference diff(const Immutable>& a, + const Immutable>& b, + const Eq& eq) { + StyleDifference result; + + if (a == b) { + return result; + } + std::vector lcs; - longest_common_subsequence(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(lcs), eq); + longest_common_subsequence(a->begin(), a->end(), b->begin(), b->end(), std::back_inserter(lcs), eq); - auto aIt = a.begin(); - auto bIt = b.begin(); + auto aIt = a->begin(); + auto bIt = b->begin(); auto lIt = lcs.begin(); - StyleDifference result; - - while (aIt != a.end() || bIt != b.end()) { - if (aIt != a.end() && (lIt == lcs.end() || !eq(*lIt, *aIt))) { + while (aIt != a->end() || bIt != b->end()) { + if (aIt != a->end() && (lIt == lcs.end() || !eq(*lIt, *aIt))) { result.removed.emplace((*aIt)->id, *aIt); aIt++; - } else if (bIt != b.end() && (lIt == lcs.end() || !eq(*lIt, *bIt))) { + } else if (bIt != b->end() && (lIt == lcs.end() || !eq(*lIt, *bIt))) { result.added.emplace((*bIt)->id, *bIt); bIt++; } else { @@ -38,23 +44,23 @@ StyleDifference diff(const std::vector& a, const std::vector& b, const return result; } -ImageDifference diffImages(const std::vector& a, - const std::vector& b) { +ImageDifference diffImages(const Immutable>& a, + const Immutable>& b) { return diff(a, b, [] (const ImmutableImage& lhs, const ImmutableImage& rhs) { return lhs->id == rhs->id; }); } -SourceDifference diffSources(const std::vector& a, - const std::vector& b) { +SourceDifference diffSources(const Immutable>& a, + const Immutable>& b) { return diff(a, b, [] (const ImmutableSource& lhs, const ImmutableSource& rhs) { return std::tie(lhs->id, lhs->type) == std::tie(rhs->id, rhs->type); }); } -LayerDifference diffLayers(const std::vector& a, - const std::vector& b) { +LayerDifference diffLayers(const Immutable>& a, + const Immutable>& b) { return diff(a, b, [] (const ImmutableLayer& lhs, const ImmutableLayer& rhs) { return std::tie(lhs->id, lhs->type) == std::tie(rhs->id, rhs->type); diff --git a/src/mbgl/renderer/style_diff.hpp b/src/mbgl/renderer/style_diff.hpp index 285d1e12ed..ef788c380c 100644 --- a/src/mbgl/renderer/style_diff.hpp +++ b/src/mbgl/renderer/style_diff.hpp @@ -21,20 +21,20 @@ public: using ImmutableImage = Immutable; using ImageDifference = StyleDifference; -ImageDifference diffImages(const std::vector&, - const std::vector&); +ImageDifference diffImages(const Immutable>&, + const Immutable>&); using ImmutableSource = Immutable; using SourceDifference = StyleDifference; -SourceDifference diffSources(const std::vector&, - const std::vector&); +SourceDifference diffSources(const Immutable>&, + const Immutable>&); using ImmutableLayer = Immutable; using LayerDifference = StyleDifference; -LayerDifference diffLayers(const std::vector&, - const std::vector&); +LayerDifference diffLayers(const Immutable>&, + const Immutable>&); bool hasLayoutDifference(const LayerDifference&, const std::string& layerID); diff --git a/src/mbgl/renderer/update_parameters.hpp b/src/mbgl/renderer/update_parameters.hpp index e35ee80a10..7c44064b0b 100644 --- a/src/mbgl/renderer/update_parameters.hpp +++ b/src/mbgl/renderer/update_parameters.hpp @@ -22,9 +22,9 @@ public: const bool spriteLoaded; const style::TransitionOptions transitionOptions; const Immutable light; - const std::vector> images; - const std::vector> sources; - const std::vector> layers; + const Immutable>> images; + const Immutable>> sources; + const Immutable>> layers; Scheduler& scheduler; FileSource& fileSource; diff --git a/src/mbgl/style/collection.hpp b/src/mbgl/style/collection.hpp new file mode 100644 index 0000000000..0deb1411b6 --- /dev/null +++ b/src/mbgl/style/collection.hpp @@ -0,0 +1,141 @@ +#pragma once + +#include +#include + +#include +#include + +namespace mbgl { +namespace style { + +/* + Manages an ordered collection of elements and their `Immutable`s. The latter is + itself stored in an Immutable container. Using immutability at the collection level + allows us to short-circuit significant portions of the RenderStyle update logic via + a simple pointer equality check, greatly improving performance. + + Element types are required to have: + + * An `Impl` inner class type + * An `Immutable baseImpl` member + * A `std::string getID() const` method +*/ +template +class Collection { +public: + using Impl = typename T::Impl; + using WrapperVector = std::vector>; + using ImmutableVector = Immutable>>; + + Collection(); + + std::size_t size() const; + T* get(const std::string&) const; + + std::vector getWrappers() const; + ImmutableVector getImpls() const { return impls; } + + auto begin() const { return wrappers.begin(); } + auto end() const { return wrappers.end(); } + + void clear(); + + T* add(std::unique_ptr, const optional& = {}); + std::unique_ptr remove(const std::string&); + + // Must be called whenever an element of the collection is internally mutated. + // Typically, each element permits registration of an observer, and the observer + // should call this method. + void update(const T&); + +private: + std::size_t index(const std::string&) const; + + WrapperVector wrappers; + ImmutableVector impls; +}; + +template +Collection::Collection() + : impls(makeMutable>>()) { +} + +template +std::size_t Collection::size() const { + return wrappers.size(); +} + +template +std::size_t Collection::index(const std::string& id) const { + return std::find_if(wrappers.begin(), wrappers.end(), [&](const auto& e) { + return e->getID() == id; + }) - wrappers.begin(); +} + +template +T* Collection::get(const std::string& id) const { + std::size_t i = index(id); + return i < size() ? wrappers[i].get() : nullptr; +} + +template +std::vector Collection::getWrappers() const { + std::vector result; + result.reserve(wrappers.size()); + + for (auto& wrapper : wrappers) { + result.push_back(wrapper.get()); + } + + return result; +} + +template +void Collection::clear() { + mutate(impls, [&] (auto& impls_) { + impls_.clear(); + }); + + wrappers.clear(); +} + +template +T* Collection::add(std::unique_ptr wrapper, const optional& before) { + std::size_t i = before ? index(*before) : size(); + + mutate(impls, [&] (auto& impls_) { + impls_.emplace(impls_.begin() + i, wrapper->baseImpl); + }); + + return wrappers.emplace(wrappers.begin() + i, std::move(wrapper))->get(); +} + +template +std::unique_ptr Collection::remove(const std::string& id) { + std::size_t i = index(id); + + if (i >= size()) { + return nullptr; + } + + auto source = std::move(wrappers[i]); + + mutate(impls, [&] (auto& impls_) { + impls_.erase(impls_.begin() + i); + }); + + wrappers.erase(wrappers.begin() + i); + + return source; +} + +template +void Collection::update(const T& wrapper) { + mutate(impls, [&] (auto& impls_) { + impls_.at(this->index(wrapper.getID())) = wrapper.baseImpl; + }); +} + +} // namespace style +} // namespace mbgl diff --git a/src/mbgl/style/image.cpp b/src/mbgl/style/image.cpp index 6039c0458c..1747de5fcc 100644 --- a/src/mbgl/style/image.cpp +++ b/src/mbgl/style/image.cpp @@ -9,25 +9,25 @@ Image::Image(std::string id, PremultipliedImage &&image, const float pixelRatio, bool sdf) - : impl(makeMutable(std::move(id), std::move(image), pixelRatio, sdf)) { + : baseImpl(makeMutable(std::move(id), std::move(image), pixelRatio, sdf)) { } std::string Image::getID() const { - return impl->id; + return baseImpl->id; } Image::Image(const Image&) = default; const PremultipliedImage& Image::getImage() const { - return impl->image; + return baseImpl->image; } bool Image::isSdf() const { - return impl->sdf; + return baseImpl->sdf; } float Image::getPixelRatio() const { - return impl->pixelRatio; + return baseImpl->pixelRatio; } } // namespace style diff --git a/src/mbgl/style/style.cpp b/src/mbgl/style/style.cpp index 34e1cdeb6f..69a6d401ed 100644 --- a/src/mbgl/style/style.cpp +++ b/src/mbgl/style/style.cpp @@ -54,6 +54,8 @@ TransitionOptions Style::getTransitionOptions() const { void Style::setJSON(const std::string& json) { sources.clear(); layers.clear(); + images.clear(); + transitionOptions = {}; Parser parser; @@ -91,12 +93,7 @@ void Style::setJSON(const std::string& json) { } void Style::addSource(std::unique_ptr source) { - // Guard against duplicate source ids - auto it = std::find_if(sources.begin(), sources.end(), [&](const auto& existing) { - return existing->getID() == source->getID(); - }); - - if (it != sources.end()) { + if (sources.get(source->getID())) { std::string msg = "Source " + source->getID() + " already exists"; throw std::runtime_error(msg.c_str()); } @@ -104,7 +101,7 @@ void Style::addSource(std::unique_ptr source) { source->setObserver(this); source->loadDescription(fileSource); - sources.emplace_back(std::move(source)); + sources.add(std::move(source)); } struct SourceIdUsageEvaluator { @@ -131,50 +128,27 @@ std::unique_ptr Style::removeSource(const std::string& id) { return nullptr; } - auto it = std::find_if(sources.begin(), sources.end(), [&](const auto& source) { - return source->getID() == id; - }); + std::unique_ptr source = sources.remove(id); - if (it == sources.end()) { - return nullptr; + if (source) { + source->setObserver(nullptr); } - auto source = std::move(*it); - source->setObserver(nullptr); - sources.erase(it); - return source; } std::vector Style::getLayers() { - std::vector result; - result.reserve(layers.size()); - for (auto& layer : layers) { - result.push_back(layer.get()); - } - return result; -} - -std::vector>::const_iterator Style::findLayer(const std::string& id) const { - return std::find_if(layers.begin(), layers.end(), [&](const auto& layer) { - return layer->baseImpl->id == id; - }); + return layers.getWrappers(); } Layer* Style::getLayer(const std::string& id) const { - auto it = findLayer(id); - return it != layers.end() ? it->get() : nullptr; + return layers.get(id); } Layer* Style::addLayer(std::unique_ptr layer, optional before) { // TODO: verify source - // Guard against duplicate layer ids - auto it = std::find_if(layers.begin(), layers.end(), [&](const auto& existing) { - return existing->getID() == layer->getID(); - }); - - if (it != layers.end()) { + if (layers.get(layer->getID())) { throw std::runtime_error(std::string{"Layer "} + layer->getID() + " already exists"); } @@ -184,25 +158,20 @@ Layer* Style::addLayer(std::unique_ptr layer, optional befor layer->setObserver(this); - return layers.emplace(before ? findLayer(*before) : layers.end(), std::move(layer))->get(); + return layers.add(std::move(layer), before); } std::unique_ptr Style::removeLayer(const std::string& id) { - auto it = std::find_if(layers.begin(), layers.end(), [&](const auto& layer) { - return layer->baseImpl->id == id; - }); - - if (it == layers.end()) - return nullptr; + std::unique_ptr layer = layers.remove(id); - auto layer = std::move(*it); + if (layer) { + layer->setObserver(nullptr); - if (auto* customLayer = layer->as()) { - customLayer->impl().deinitialize(); + if (auto* customLayer = layer->as()) { + customLayer->impl().deinitialize(); + } } - layer->setObserver(nullptr); - layers.erase(it); return layer; } @@ -237,20 +206,11 @@ double Style::getDefaultPitch() const { } std::vector Style::getSources() { - std::vector result; - result.reserve(sources.size()); - for (auto& source : sources) { - result.push_back(source.get()); - } - return result; + return sources.getWrappers(); } Source* Style::getSource(const std::string& id) const { - const auto it = std::find_if(sources.begin(), sources.end(), [&](const auto& source) { - return source->getID() == id; - }); - - return it != sources.end() ? it->get() : nullptr; + return sources.get(id); } bool Style::isLoaded() const { @@ -272,22 +232,23 @@ bool Style::isLoaded() const { } void Style::addImage(std::unique_ptr image) { - std::string id = image->getID(); - auto it = images.find(id); - if (it != images.end() && it->second->getImage().size != image->getImage().size) { - Log::Warning(Event::Sprite, "Can't change sprite dimensions for '%s'", id.c_str()); - return; + if (style::Image* existing = images.get(image->getID())) { + if (existing->getImage().size != image->getImage().size) { + Log::Warning(Event::Sprite, "Can't change sprite dimensions for '%s'", image->getID().c_str()); + return; + } + images.remove(image->getID()); } - images[id] = std::move(image); + + images.add(std::move(image)); } void Style::removeImage(const std::string& id) { - images.erase(id); + images.remove(id); } const style::Image* Style::getImage(const std::string& id) const { - auto it = images.find(id); - return it == images.end() ? nullptr : it->second.get(); + return images.get(id); } void Style::setObserver(style::Observer* observer_) { @@ -295,11 +256,13 @@ void Style::setObserver(style::Observer* observer_) { } void Style::onSourceLoaded(Source& source) { + sources.update(source); observer->onSourceLoaded(source); observer->onUpdate(Update::Repaint); } void Style::onSourceChanged(Source& source) { + sources.update(source); observer->onSourceChanged(source); } @@ -312,6 +275,7 @@ void Style::onSourceError(Source& source, std::exception_ptr error) { } void Style::onSourceDescriptionChanged(Source& source) { + sources.update(source); observer->onSourceDescriptionChanged(source); if (!source.loaded) { source.loadDescription(fileSource); @@ -332,7 +296,8 @@ void Style::onSpriteError(std::exception_ptr error) { observer->onResourceError(error); } -void Style::onLayerChanged(Layer&) { +void Style::onLayerChanged(Layer& layer) { + layers.update(layer); observer->onUpdate(Update::Repaint); } @@ -350,31 +315,16 @@ const std::string& Style::getGlyphURL() const { return glyphURL; } -std::vector> Style::getImageImpls() const { - std::vector> result; - result.reserve(images.size()); - for (const auto& image : images) { - result.push_back(image.second->impl); - } - return result; +Immutable>> Style::getImageImpls() const { + return images.getImpls(); } -std::vector> Style::getSourceImpls() const { - std::vector> result; - result.reserve(sources.size()); - for (const auto& source : sources) { - result.push_back(source->baseImpl); - } - return result; +Immutable>> Style::getSourceImpls() const { + return sources.getImpls(); } -std::vector> Style::getLayerImpls() const { - std::vector> result; - result.reserve(layers.size()); - for (const auto& layer : layers) { - result.push_back(layer->baseImpl); - } - return result; +Immutable>> Style::getLayerImpls() const { + return layers.getImpls(); } } // namespace style diff --git a/src/mbgl/style/style.hpp b/src/mbgl/style/style.hpp index a60fee9264..7e8f6f640b 100644 --- a/src/mbgl/style/style.hpp +++ b/src/mbgl/style/style.hpp @@ -9,6 +9,7 @@ #include #include #include +#include #include #include @@ -75,9 +76,9 @@ public: const std::string& getGlyphURL() const; - std::vector> getImageImpls() const; - std::vector> getSourceImpls() const; - std::vector> getLayerImpls() const; + Immutable>> getImageImpls() const; + Immutable>> getSourceImpls() const; + Immutable>> getLayerImpls() const; void dumpDebugLogs() const; @@ -90,9 +91,9 @@ private: std::unique_ptr spriteLoader; std::string glyphURL; - std::unordered_map> images; - std::vector> sources; - std::vector> layers; + Collection images; + Collection sources; + Collection layers; TransitionOptions transitionOptions; std::unique_ptr light; @@ -103,8 +104,6 @@ private: double defaultBearing = 0; double defaultPitch = 0; - std::vector>::const_iterator findLayer(const std::string& layerID) const; - // SpriteLoaderObserver implementation. void onSpriteLoaded(std::vector>&&) override; void onSpriteError(std::exception_ptr) override; diff --git a/test/sprite/sprite_atlas.test.cpp b/test/sprite/sprite_atlas.test.cpp index 3226f19c1b..78a5862475 100644 --- a/test/sprite/sprite_atlas.test.cpp +++ b/test/sprite/sprite_atlas.test.cpp @@ -23,7 +23,7 @@ TEST(SpriteAtlas, Basic) { auto images = parseSprite(util::read_file("test/fixtures/annotations/emerald.png"), util::read_file("test/fixtures/annotations/emerald.json")); for (auto& image : images) { - atlas.addImage(image->impl); + atlas.addImage(image->baseImpl); } auto metro = *atlas.getIcon("metro"); @@ -63,7 +63,7 @@ TEST(SpriteAtlas, Size) { auto images = parseSprite(util::read_file("test/fixtures/annotations/emerald.png"), util::read_file("test/fixtures/annotations/emerald.json")); for (auto& image : images) { - atlas.addImage(image->impl); + atlas.addImage(image->baseImpl); } auto metro = *atlas.getIcon("metro"); -- cgit v1.2.1