Merge pull request tangrams#443 from tangrams/perf-sort-feature-tags

MVT source speedup
matteblair · Dec 18, 2015 · c1cd749 · c1cd749
2 parents de49162 + ab50e14
commit c1cd749
Show file tree

Hide file tree

Showing 4 changed files with 56 additions and 16 deletions.
diff --git a/core/src/data/properties.cpp b/core/src/data/properties.cpp
@@ -20,20 +20,20 @@ Properties::Properties(std::vector<Item>&& _items) {
 }
 
 Properties& Properties::operator=(Properties&& _other) {
-     props = std::move(_other.props);
-     return *this;
+    props = std::move(_other.props);
+    return *this;
+}
+
+void Properties::setSorted(std::vector<Item>&& _items) {
+    props = std::move(_items);
 }
 
 const Value& Properties::get(const std::string& key) const {
     const static Value NOT_FOUND(none_type{});
 
     const auto it = std::lower_bound(props.begin(), props.end(), key,
                                      [](const auto& item, const auto& key) {
-                                         if (item.key.size() == key.size()) {
-                                             return item.key < key;
-                                         } else {
-                                             return item.key.size() < key.size();
-                                         }
+                                         return keyComparator(item.key, key);
                                      });
 
     if (it == props.end() || it->key != key) {

diff --git a/core/src/data/properties.h b/core/src/data/properties.h
@@ -45,6 +45,8 @@ struct Properties {
     void add(std::string key, std::string value);
     void add(std::string key, double value);
 
+    void setSorted(std::vector<Item>&& _items);
+
     // template <typename... Args> void add(std::string key, Args&&... args) {
     //     props.emplace_back(std::move(key), Value{std::forward<Args>(args)...});
     //     sort();
@@ -54,6 +56,13 @@ struct Properties {
 
     int32_t sourceId;
 
+    static bool keyComparator(const std::string& a, const std::string& b) {
+        if (a.size() == b.size()) {
+            return a < b;
+        } else {
+            return a.size() < b.size();
+        }
+    }
 private:
     std::vector<Item> props;
 };

diff --git a/core/src/util/pbfParser.cpp b/core/src/util/pbfParser.cpp
@@ -1,9 +1,12 @@
 #include "pbfParser.h"
 
+#include "data/propertyItem.h"
 #include "tile/tile.h"
 #include "platform.h"
 #include "util/geom.h"
 
+#include <algorithm>
+
 namespace Tangram {
 
 void PbfParser::extractGeometry(ParserContext& _ctx, protobuf::message& _geomIn) {
@@ -68,10 +71,13 @@ void PbfParser::extractFeature(ParserContext& _ctx, protobuf::message& _featureI
     //Iterate through this feature
     protobuf::message geometry; // By default data_ and end_ are nullptr
 
-    _ctx.properties.clear();
     _ctx.coordinates.clear();
     _ctx.numCoordinates.clear();
 
+    _ctx.featureTags.clear();
+    _ctx.featureTags.assign(_ctx.keys.size(), -1);
+
+
     while(_featureIn.next()) {
         switch(_featureIn.tag) {
             // Feature ID
@@ -86,7 +92,7 @@ void PbfParser::extractFeature(ParserContext& _ctx, protobuf::message& _featureI
                 protobuf::message tagsMsg = _featureIn.getMessage();
 
                 while(tagsMsg) {
-                    std::size_t tagKey = tagsMsg.varint();
+                    auto tagKey = tagsMsg.varint();
 
                     if(_ctx.keys.size() <= tagKey) {
                         LOGE("accessing out of bound key");
@@ -98,14 +104,14 @@ void PbfParser::extractFeature(ParserContext& _ctx, protobuf::message& _featureI
                         return;
                     }
 
-                    std::size_t valueKey = tagsMsg.varint();
+                    auto valueKey = tagsMsg.varint();
 
                     if( _ctx.values.size() <= valueKey ) {
                         LOGE("accessing out of bound values");
                         return;
                     }
 
-                    _ctx.properties.emplace_back(_ctx.keys[tagKey], _ctx.values[valueKey]);
+                    _ctx.featureTags[tagKey] = valueKey;
                 }
                 break;
             }
@@ -124,7 +130,17 @@ void PbfParser::extractFeature(ParserContext& _ctx, protobuf::message& _featureI
                 break;
         }
     }
-    _out.props = std::move(_ctx.properties);
+
+    std::vector<Properties::Item> properties;
+    properties.reserve(_ctx.featureTags.size());
+
+    for (int tagKey : _ctx.orderedKeys) {
+        int tagValue = _ctx.featureTags[tagKey];
+        if (tagValue >= 0) {
+            properties.emplace_back(_ctx.keys[tagKey], _ctx.values[tagValue]);
+        }
+    }
+    _out.props.setSorted(std::move(properties));
 
     switch(_out.geometryType) {
         case GeometryType::points:
@@ -184,7 +200,7 @@ void PbfParser::extractLayer(ParserContext& _ctx, protobuf::message& _layerIn, L
     _ctx.values.clear();
     _ctx.featureMsgs.clear();
 
-    //iterate layer to populate featureMsgs, keys and values
+    //// Iterate layer to populate featureMsgs, keys and values
     while(_layerIn.next()) {
         switch(_layerIn.tag) {
             case 2: // features
@@ -245,6 +261,19 @@ void PbfParser::extractLayer(ParserContext& _ctx, protobuf::message& _layerIn, L
         }
     }
 
+    //// Assign ordering to keys for faster sorting
+    _ctx.orderedKeys.clear();
+    _ctx.orderedKeys.reserve(_ctx.keys.size());
+    // assign key ids
+    for (int i = 0, n = _ctx.keys.size(); i < n; i++) {
+        _ctx.orderedKeys.push_back(i);
+    }
+    // sort by Property key ordering
+    std::sort(_ctx.orderedKeys.begin(), _ctx.orderedKeys.end(),
+              [&](int a, int b) {
+                  return Properties::keyComparator(_ctx.keys[a], _ctx.keys[b]);
+              });
+
     _out.features.reserve(_ctx.featureMsgs.size());
     for(auto& featureMsg : _ctx.featureMsgs) {
         _out.features.emplace_back(_ctx.sourceId);

diff --git a/core/src/util/pbfParser.h b/core/src/util/pbfParser.h
@@ -1,9 +1,8 @@
 #pragma once
 
 #include "data/tileData.h"
-#include "data/propertyItem.h"
-
 #include "pbf/pbf.hpp"
+#include "util/variant.h"
 
 #include <vector>
 #include <string>
@@ -20,10 +19,13 @@ namespace PbfParser {
         int32_t sourceId;
         std::vector<std::string> keys;
         std::vector<Value> values;
-        std::vector<Properties::Item> properties;
         std::vector<protobuf::message> featureMsgs;
         std::vector<Point> coordinates;
         std::vector<int> numCoordinates;
+        // Map Key ID -> Tag values
+        std::vector<int> featureTags;
+        // Key IDs sorted by Property key ordering
+        std::vector<int> orderedKeys;
 
         int tileExtent = 0;
     };