Use faster method for calculating distances. by danpat · Pull Request #5041 · Project-OSRM/osrm-backend

danpat · 2018-04-19T23:36:54Z

Our use of the haversineDistance function is a bit trigonometry heavy. Trig functions are relatively expensive, especially when used a lot.

With work on the distances branch, we'll be performing a lot of distance calculations within matrix requests. A 100x100 table with distances without caching will spend over 50% of it's time in haversineDistnace().

This PR switches from using the haversineDistance function, to a new fccApproximateDistance function, supplied by the https://github.com/mapbox/cheap-ruler-cpp library.

Don't let the name fool you - the fccApproximateDistance method is actually more precise than Haversine, and significantly faster. For short distances (up to a handful of km), which covers almost all the geometry we care about, it has almost 0 difference to the Vincenty method.

In simple tests, this change reduced a 100x100 table request with annotations=distances from 8900ms down to about 4500ms. There's a big speedup here because there are a lot of distance calculations made. Regular /route requests are unlikely to see such a boost, as the distance calcs they do form a much smaller part of the overall request workload.

Before the change, this was the CPU profile in a table request with distances:

after this change:

This PR is not ready to merge, see checklist below.

Tasklist

danpat · 2018-04-19T23:39:19Z

src/util/coordinate_calculation.cpp

+    const auto lat1 = static_cast<double>(util::toFloating(coordinate_1.lat));
+    const auto lon2 = static_cast<double>(util::toFloating(coordinate_2.lon));
+    const auto lat2 = static_cast<double>(util::toFloating(coordinate_2.lat));
+    return cheap_ruler_cache[std::lround(lat1 / 10) + 9].distance({lon1, lat1}, {lon2, lat2});


Should probably add assertion here that bucket number is within range for our cache.

chaupow · 2018-04-20T08:01:04Z

awesome @danpat
let me rerun the measurements with this!

emiltin · 2018-04-20T08:02:24Z

sweet

chaupow · 2018-04-20T10:02:07Z

Aaaaaand numbers are out!

What	`distances` PR	`faster-distances` PR
100x100 in `us-west`	`12s`	`5.6s`
100x100 in la max dist 20km	`3.7s`	`800ms`

emiltin · 2018-04-20T11:02:02Z

i like what i see

chaupow · 2018-04-20T14:08:52Z

@danpat if you're ok with it, I will take it on from here working on your tasklist? 😄

mourner · 2018-04-24T06:13:21Z

Wow, that's a massive speedup! Happy how this is turning out :)

cffk · 2018-04-24T07:24:07Z

This method of calculating the distance has the following problems:

The distance between points with longitudes ± 179.9° is (badly!) off.
d(p1, p2) ≠ d(p2, p1) if p1 and p2 fall in different latitude buckets; this might throw off some calculations.
The error in the distance is about 10% for points on latitude 55°. (It's off by a factor of 2 for points on latitude 85°.)

(For comparison, the error in the great-circle distance is about 0.5%.)

danpat · 2018-04-24T07:42:31Z

The error in the distance is about 10% for points on latitude 55°. (It's off by a factor of 2 for points on latitude 85°.)

@cffk Are you implying a problem with the method itself, or a bug in the implementation? Those error values are unexpectedly large.

Assuming it's correct, https://github.com/mapbox/cheap-ruler#precision shows the expected precision at various latitudes. It never comes anywhere near 10% for up to 1000km lines.

Thanks for the other notes though - I've added some items to the checklist. We're fortunate that we don't care much about being a general purpose distance calculator, and we also only care about fairly short geometry (most "segments" from OSM maps are quite short). A lot of the geometry we care about should fall in ranges where this method (supposedly) works, and we can detect and fallback to other methods for the outliers.

cffk · 2018-04-24T08:04:03Z

@danpat The problem is the latitude binning. The distance between two points on latitude 55° uses the latitude scale factor for 60°. The main term in the latitude scale factor is cos(latitude) and cos(60d) differs from cos(55d) by about 10%.

I noticed you saying that the approximation "falls apart" for longitudes ±179.9°. This isn't the case! You just need to make sure to reduce the longitude difference to [−180°, 180°].

mourner · 2018-04-24T08:31:57Z

@danpat yeah, rounding difference of 5 degrees is definitely too much. I'd suggest to 1) calculate the cheap ruler cache lazily; 2) bin much more granularly, e.g. 0.01 deg.

chaupow · 2018-04-24T14:35:12Z

@mourner @cffk

yup, I'm working on this. I think @danpat just used few buckets here to see whether it works at all and see the speed gain.

I am adding more buckets (currently at 180, with .5 diff of latitude but still doing Q&A) and the results seem nice. Thanks for flagging this 😄

cffk

I recommend

centering the bins (now the N and S polar regions are treated the same)
halving the number of bins using symmetry

Thus, in constructor

step(90.0 / number_of_rulers)
cheap_ruler_cache[n] = mapbox::cheap_ruler::CheapRuler(step * (n + 0.5), mapbox::cheap_ruler::CheapRuler::Meters);

and in getRuler

return cheap_ruler_cache[std::min((int)std::floor(abs(lat)/step), (int)cheap_ruler_cache.size() - 1)];

and instantiate with

CheapRulerContainer cheap_ruler_container(1800);

Finally, in the distance function invoke with the mean latitude

return cheap_ruler_container.getRuler(0.5 * (lat1 + lat2)).distance({lon1, lat1}, {lon2, lat2});

cffk · 2018-04-25T18:38:45Z

FYI, I submitted a pull request to cheap-ruler-cpp to fix the longitude wrapping bug.

chaupow · 2018-04-25T20:19:48Z

@cffk thanks so much! I adjusted the changes you suggested in the last commit.

cffk · 2018-04-25T21:57:06Z

A couple of additional comments:

I submitted another pull request for cheap-ruler-cpp to improve the accuracy and to let you switch to the WGS84 ellipsoid (from Clarke 1866).
To minimize the errors for a given number of buckets, you would distribute the buckets according to cos(lat). Since this would slow down selecting the bucket, I don't think there's any way to take advantage of this.

oxidase · 2018-04-26T18:26:24Z

@chaupow std::experimental::optional is not supported in MSVC2015. I changed it to mapbox::optional in feature.hpp and pushed a commit to make a CI check.

TheMarex · 2018-04-26T21:21:47Z

Pushed some optimizations that removed the rounding and replaced it with integer math, which yielded a nice 5% speedup.

Measurements for 10x10 on Berlin:

TheMarex

Looks great! Did some performance measurements and they are looking great!

TheMarex · 2018-04-26T19:57:50Z

src/util/coordinate_calculation.cpp

+    std::vector<mapbox::cheap_ruler::CheapRuler> cheap_ruler_cache;
+    const double step;
+};
+CheapRulerContainer cheap_ruler_container(1800);


Should be marked as static.

danpat · 2018-04-26T21:39:37Z

src/util/coordinate_calculation.cpp

+    mapbox::cheap_ruler::CheapRuler &getRuler(const FixedLatitude lat)
+    {
+        BOOST_ASSERT(step > 1);
+        auto bin = (std::abs(static_cast<int>(lat)) - 1) / step;


What if the request is for lat = 0 here? This'll could lead to bin = -1 if step is only 2. Or will integer division guarantee this is always 0 or bigger? Either way, an assert that bin >= 0 && bin < cheap_ruler_cache.size() should probably be here.

Good catch! Didn't realize rounding direction was not actually defined for 1/2.

fix cmakelist

emiltin · 2018-04-26T21:55:36Z

features/testbot/distance_matrix.feature

-            | a | 0   | 100 |
-            | b | 100 | 0   |
+            |   | a      | b      |
+            | a | 0      | 100+-1 |


Elsewhere (like in the "When I route I should get " tests) the syntax used is "100m +-3", rather than "100+-3". For consistency it might be good to follow this syntax.

chaupow · 2018-04-27T13:53:27Z

Awesome, thanks a ton @oxidase !

danpat force-pushed the faster_distances branch from 3e34b2c to 452eed7 Compare April 19, 2018 23:38

danpat commented Apr 19, 2018

View reviewed changes

danpat added Experimental - Do not merge Work In Progress labels Apr 19, 2018

ghoshkaj force-pushed the distances branch from 5705f95 to 81b0756 Compare April 20, 2018 02:47

chaupow mentioned this pull request Apr 20, 2018

Distances in matrix - CH #4990

Merged

11 tasks

chaupow self-assigned this Apr 20, 2018

ghoshkaj force-pushed the distances branch 3 times, most recently from 649e0af to 5ebc145 Compare April 20, 2018 21:21

chaupow changed the base branch from distances to master April 23, 2018 18:30

This was referenced Apr 23, 2018

Bad value of EARTH_RADIUS #5051

Closed

Haversine distance should use spherical Earth radius mapbox/turf-swift#26

Open

TheMarex added this to the distance-matrix milestone Apr 24, 2018

TheMarex removed the Experimental - Do not merge label Apr 24, 2018

cffk suggested changes Apr 25, 2018

View reviewed changes

chaupow force-pushed the faster_distances branch from 6b69ab6 to f0d08e5 Compare April 25, 2018 19:42

TheMarex added Review and removed Work In Progress labels Apr 26, 2018

TheMarex approved these changes Apr 26, 2018

View reviewed changes

danpat commented Apr 26, 2018

View reviewed changes

danpat and others added 7 commits April 26, 2018 21:48

Use faster method for calculating distances.

51b388d

fix cmakelist

refactor cheap ruler cache

3430374

change haversine computation to cheap ruler in distance tables

42f819c

only use half of rulers because earth is symmetric

0bebb7e

clang format

bef0763

make eslint happy

195eed1

Use mapbox::util::optional instead of std::experimental::optional

df38ab5

TheMarex force-pushed the faster_distances branch from 4387030 to 08c5eed Compare April 26, 2018 21:48

emiltin reviewed Apr 26, 2018

View reviewed changes

TheMarex force-pushed the faster_distances branch from 08c5eed to eb92579 Compare April 26, 2018 22:05

TheMarex added 2 commits April 26, 2018 22:27

Optimize distance calculation by getting rid of rounding

cdf0dde

Make cheap rulers static

6f60524

TheMarex force-pushed the faster_distances branch from eb92579 to 6f60524 Compare April 26, 2018 22:27

TheMarex merged commit ae805f9 into master Apr 27, 2018

TheMarex deleted the faster_distances branch April 27, 2018 03:21

twelch mentioned this pull request Jul 7, 2024

Calculate area with higher accuracy Turfjs/turf#2643

Closed

Uh oh!

Conversation

danpat commented Apr 19, 2018 • edited by TheMarex Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Tasklist

Uh oh!

danpat Apr 19, 2018

Choose a reason for hiding this comment

Uh oh!

chaupow commented Apr 20, 2018

Uh oh!

emiltin commented Apr 20, 2018

Uh oh!

chaupow commented Apr 20, 2018

Uh oh!

emiltin commented Apr 20, 2018

Uh oh!

chaupow commented Apr 20, 2018

Uh oh!

mourner commented Apr 24, 2018

Uh oh!

cffk commented Apr 24, 2018

Uh oh!

danpat commented Apr 24, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

cffk commented Apr 24, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mourner commented Apr 24, 2018

Uh oh!

chaupow commented Apr 24, 2018

Uh oh!

cffk left a comment

Choose a reason for hiding this comment

Uh oh!

cffk commented Apr 25, 2018

Uh oh!

chaupow commented Apr 25, 2018

Uh oh!

cffk commented Apr 25, 2018

Uh oh!

oxidase commented Apr 26, 2018

Uh oh!

TheMarex commented Apr 26, 2018

Uh oh!

TheMarex left a comment

Choose a reason for hiding this comment

Uh oh!

TheMarex Apr 26, 2018

Choose a reason for hiding this comment

Uh oh!

danpat Apr 26, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

TheMarex Apr 26, 2018

Choose a reason for hiding this comment

Uh oh!

emiltin Apr 26, 2018

Choose a reason for hiding this comment

Uh oh!

chaupow commented Apr 27, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

danpat commented Apr 19, 2018 •

edited by TheMarex

Loading

danpat commented Apr 24, 2018 •

edited

Loading

cffk commented Apr 24, 2018 •

edited

Loading

danpat Apr 26, 2018 •

edited

Loading