Efficiency recommendations

[springmeyer]

As @artemp mentioned today over chat, it is important to ensure code is correct before optimizing it. Because, of course, Faster code that gets the wrong answer is not superior to correct code. per https://howardhinnant.github.io/coding_guidelines.html.

#28 indicates a potentially critical bug involving the closest point results, so clearly we should be wary to optimize around the closest point code path until #28 is resolved.

However there are other code paths that:

• Look and behave correctly
• Exhibit potential for optimization

Below are some recommendations to consider for optimization.

Use more appropriate container types

Currently the code is using std::map<std::string, variant_type> to hold feature properties. The most efficient container is the one that is fastest for your purpose. In our case creation and iteration speed are what matters (e.g. we don't search so that does not matter). In my experience std::vector<std::pair<std::string, variant_type>> can be created faster than std::map and therefore is a better container when fast search is not needed. So, I would recommend changing to std::vector<std::pair<std::string, variant_type>>.

Don't risk blocking the main loop

Only the code inside Execute() runs in the threadpool. The code before entering the threadpool and after (HandleOKCallback()) all run on the main event loop and therefore is synchronous. If that synchronous code is slow (does CPU intensive work or triggers many allocations) then that is going to block the main loop and potentially reduce the ability to dispatch work to the threadpool. This problem is also going to be more severe when the code is running in a larger application where other JS is running on the main event loop.

So, I would recommend reverting a175212#diff-d293222b917c4d9edf75c1288538554fL281 and moving the results_to_json_string(result_string_, results_); out of the HandleOKCallback() function and back into the Execute().

@@ -283,6 +283,7 @@ struct Worker : Nan::AsyncWorker {
             std::sort(results_.begin(), results_.end(), [](const ResultObject& a, const ResultObject& b) { return a.distance < b.distance; });
 
             // TODO(sam) create new results vector (from results_) of length specific to num_results option
+            results_to_json_string(result_string_, results_);
 
         } catch (const std::exception& e) {
             SetErrorMessage(e.what());
@@ -299,7 +300,6 @@ struct Worker : Nan::AsyncWorker {
     void HandleOKCallback() override {
         Nan::HandleScope scope;
 
-        results_to_json_string(result_string_, results_);
 
         auto const argc = 2u;
         v8::Local<v8::Value> argv[argc] = {

Reducing unnecessary copies/reallocation

This is especially important when custom objects are being copied because:

• Custom objects may be large and poorly packed (and therefore larger than they would be if packed in a more optimized way).
• Contain other object members that are large and require allocation and deallocation to be copied themselves (like std::vector or std::map).

Accidental copies are easy to have happen and a common cause of slow code. They are one of the reasons, in my experience, why it is easy to write C++ that is slower than Javascript (v8 goes to extreme lengths to avoid allocations for you). To write C++ faster than Javascript we need to aim for zero copy code. To achieve that we need to either pass objects by reference or leverage C++11 move semantics.

Okay, enough context, let's dive in...

We need to avoid copying the results passed to the json generator. Passing by reference here makes sense:

- void results_to_json_string(std::string & s, std::vector<ResultObject> results) {
+ void results_to_json_string(std::string & s, std::vector<ResultObject> const& results) {

Also the properties arg being passed to the ResultObject constructor is currently being copied. And the ResultObject itself is being allocated, then copied, when it could be constructed in place. To avoid these extra allocations do:

@@ -32,7 +32,7 @@ struct ResultObject {
     ResultObject(
         mapbox::geometry::point<double> p,
         double distance0,
-        std::map<std::string, ResultObject::variant_type> props_map,
+        std::map<std::string, ResultObject::variant_type> && props_map,
         std::string name,
         GeomType geom_type)
         : coordinates(p),
@@ -272,8 +272,7 @@ struct Worker : Nan::AsyncWorker {
                                 properties_map.insert(std::pair<std::string, variant_type>(key, value));
                             }
 
-                            ResultObject r(feature_lnglat, meters, properties_map, layer_name, original_geometry_type);
-                            results_.emplace_back(r);
+                            results_.emplace_back(feature_lnglat, meters, std::move(properties_map), layer_name, original_geometry_type);
                         }
                     } // end tile.layer.feature loop
                 }     // end tile.layer loop

Also, the individual properties are suffering from an extra copy currently due to the use of insert. Instead we want to use C++11 emplace:

@@ -267,9 +267,9 @@ struct Worker : Nan::AsyncWorker {
                             using variant_type = ResultObject::variant_type;
                             ResultObject::properties_type properties_map;
                             while (auto prop = feature.next_property()) {
-                                std::string key = std::string{prop.key()};
-                                variant_type value = vtzero::convert_property_value<variant_type>(prop.value());
-                                properties_map.insert(std::pair<std::string, variant_type>(key, value));
+                                properties_map.emplace(
+                                    std::string{prop.key()},
+                                    vtzero::convert_property_value<variant_type>(prop.value()));
                             }
 
                             ResultObject r(feature_lnglat, meters, properties_map, layer_name, original_geometry_type);

Also, all this is probably of minor cost compared to the re-allocation cost that is more hidden:

• Reallocation of the ResultObjects inside the std::vector<ResultObject> as it grows
• Reallocation of the ResultObjects inside the std::vector<ResultObject> when it is sorted

We want to avoid both:

• the amount of reallocation
• the cost of reallocation.

The best way to avoid the amount of allocation is to call vector.reserve(<max possible size>). However in our case it is tricky to know <max possible size> because we don't know how many ResultObject we will end up with. This needs some experimentation and may or may not result in faster code. This post has some details on this.

The real win possible in vtquery currently is in reducing the cost of reallocation. The cost is large currently because the ResultObject does not ban copying or implement a move assignment or move constructor. If we were to dig deep in https://www.slideshare.net/ripplelabs/howard-hinnant-accu2014 we'd learn that if we delete the copy constructor and copy assignment operator and define the move assignment or move constructor, then the reallocation happening during std::sort will magically start using move semantics and will avoid the reallocation from copying data around during sort.

This can be done by adding these operators to the ResultObject class:

+    // non-copyable
+    ResultObject(ResultObject const&) = delete;
+    ResultObject& operator=(ResultObject const&) = delete;
+
+    // movable
+    ResultObject(ResultObject&&) = default;
+    ResultObject& operator=(ResultObject&&) = default;

Be more lazy

Currently the feature properties are:

• Being pushed into a std::map
• Being decoded into a variant

These structures require allocations.

Given that:

• All we do with the feature properties is ultimately turn them into JSON objects, and
• When limiting results is implemented (I noticed num_results is currently not respected), we will only return a subset of features and therefore the creation of properties will be wasted.

I think:

• We should be more lazy and not decode into a variant or std::map during the layer.next_feature() loop.
• Instead we should take a reference to the data_view representing the vtzero::feature
• After sorting, we can decode only the top N features directly from their data_view into a JSON object without std::map or variant intermediate objects.

Note: Unless a better solution were devised, this would probably require bringing back the std::deque<vtzero::layer> layers; that was removed in 84606a3 (to be able to keep the vtzero::layer referenced by the vtzero::feature alive). It should be possible to store a data_view representing the property values to avoid needing to keep the layer around (the layer is only needed to get the right property key/value, but once gotten it should be safe to use them without the layer alive?).

/cc @mapbox/core-tech

[mapsam]

@springmeyer thanks for writing this up! One quick note:

results_to_json_string(result_string_, results_);

will eventually be a function named create_v8_object (to return actual JSON and not stringified JSON) so my understanding is that we'll need to do this within the HandleOKCallback() function to have access to the v8 thread again.

[springmeyer]

@mapsam thanks for noting that: yes, it will make sense to keep the logic in the HandleOKCallback in that case 👍

[mapsam]

Update here:

Use more appropriate container types

This was done in #27!

Don't risk blocking the main loop

We're doing out best to avoid blocking the main loop, but need to use v8 objects to construct the response data structure. According to #31 the slowdown is insignificant.

Reducing unnecessary copies/reallocation

I haven't actively worked on this one yet. Will plan on making a PR and running benchmarks!

Be more lazy

Agree. We are currently not implementing this fully, but we are only decoding properties once they are in the hit list. num_results hasn't been implemented yet either, which will be part of this update.

---

Next main step for me is to profile vtquery to determine:

• whether closest_point is a meaningful bottleneck
• if things like allocation and copies are meaningful bottlenecks

cc @flippmoke

[springmeyer]

Agree. We are currently not implementing this fully, but we are only decoding properties once they are in the hit list.

I see the latest code is using using properties_type = std::vector<std::pair<std::string, vtzero::property_value_view>>; - That looks really good. Storing the property view should be quiet efficient - less work to get it and cheap to move around.

Reducing unnecessary copies/reallocation

I haven't actively worked on this one yet. Will plan on making a PR and running benchmarks!

👍 But per above, now that you are not longer storing the raw variant_type and rather the property_value_view the largest cost from copying is now likely gone.

[springmeyer]

Reducing unnecessary copies/reallocation

Just learned a cool trick for ensuring this is working (classes are movable and not copyable) by noticing a commit from @joto: mapbox/vtzero@5e70144...7d81c92#diff-3844a7a45e2d031efa91412ecf30e370R15. If we moved on #14, doing this in a pure C++ unit test (asserting that the custom classes we use are noncopyable) would be feasible.

[mapsam]

@springmeyer looks like that link just shows an empty diff - mind updating it?

[mapsam]

Profiling results from 62fbf0d

Profiled five different fixtures:

1. single tile, SF, radius large enough to encompass most of the tile
2. 9 tiles, SF, radius large enough to encompass all tiles
3. single tile, all points, no properties
4. single tile, all points, with properties

Will plan on profiling linestrings/polygons if they seem necessary.

General takeaways

• std::sort lambda is definitely the most expensive operation in the codebase, each thread using anywhere from 20-50% of it's time executing.
• second most expensive operation is the ResultObject allocation - anywhere from 10-30% of the thread's time
• with properties, the std::vectorstd::pair allocation for key/value pairs can take some significant time ~10% but sometimes as low as 3% when there are no properties, and high as 17% with mapbox streets tiles
• vtzero next_feature sometimes shows high percentages (when there aren't properties - so it's relative) and when not appearing high it's ~1-5% of the thread's time
• the variant_helper shows up ~5% of the time
• free_tiny, locks, and waits account for ~3-7% of the thread's time
• closest_point, no matter the fixture, never went above 2.5% and was typically ~1.5%

next steps

• I think the biggest next things to hit are the ResultsObject efficiency - making sure we are only moving it and not copying. Unfortunately the results object needs to be reallocated every time we get a new hit, so if we work on updating the sort algorithm to "sort during" we can feed two birds with one hand, A) reduce sort cost and B) set the size of our ResultsObject vector immediately without emplacing and allocating every addition.
• optimize our key/value storage to prevent copying it
• I think closest_point is totally okay right now - we may see an increase if we move to doubles radius=0 leads to zero results with PIP #36 but let's save those benchmarks for a different time.

Benchmarks

Current benchmarks at ce9f99c are:

1: pip: many building polygons ... 2273 runs/s (440ms)
2: pip: many building polygons, single layer ... 2481 runs/s (403ms)
3: query: many building polygons, single layer ... 418 runs/s (2390ms)
4: query: linestrings, mapbox streets roads ... 870 runs/s (1149ms)
5: query: polygons, mapbox streets buildings ... 469 runs/s (2134ms)
6: query: all things - dense single tile ... 259 runs/s (3859ms)
7: query: all things - dense nine tiles ... 37 runs/s (27085ms)
8: elevation: terrain tile nepal ... 2012 runs/s (497ms)
9: geometry: 2000 points in a single tile, no properties ... 2079 runs/s (481ms)
10: geometry: 2000 points in a single tile, with properties ... 492 runs/s (2033ms)
11: geometry: 2000 linestrings in a single tile, no properties ... 1437 runs/s (696ms)
12: geometry: 2000 linestrings in a single tile, with properties ... 454 runs/s (2205ms)
13: geometry: 2000 polygons in a single tile, no properties ... 1340 runs/s (746ms)
14: geometry: 2000 polygons in a single tile, with properties ... 519 runs/s (1925ms)

cc @flippmoke @springmeyer

[artemp]

@mapsam

std::sort lambda is definitely the most expensive operation in the codebase, each thread using anywhere from 20-50% of it's time executing.

This is good ^ and it demonstrates well what's wrong with your approach - e.g sorting expensive objects which results in copying and re-allocations. Instead you should sort references or some kind of IDs (index into original vector). HTH
/cc @springmeyer @flippmoke

[mapsam]

Thanks @artemp! Had a good session with @flippmoke to implement your thoughts - take a look in #39

[mapsam]

vector-tile 2.x is implemented in #42 which helps out with a lot of the optimizations here. Plus we are sorting during the loop instead of after, and only copying necessary information.

The last piece, key/value storage is now completely handled by vector-tile. We are only decoding properties IF they are added to the priority_queue, which is resulting in fewer operations overall. I'm going to run some profiles of this specific branch and will report back.

[springmeyer]

Great work @mapsam @flippmoke - I think this is good to close up then from my perspective as long at the changes in #42 are working as you'd expect. Let me know if you'd like my or @artemp's eyes on reviewing #42.

[mapsam]

Agreed @springmeyer - closing this with a profile of commit 105f1d6

https://callgraph.herokuapp.com/53adc43d300262333da56d43d1562414

• 48% - polygon extraction (vector-tile 2.x)
• 14% - closest_point algorithm
• 13% - variant helper
• 5.5% - vtzero::layer::next_feature()
• 3.2% - linestring extraction (vector-tile 2.x)
• 2% - vtzero::vector_tile::next_layer()
• 1% - extract properties (vector-tile 2.x)