Unfortunately, this change causes performance degradation. There are timings:
master

all items: 13630
percentiles	10%	50%	90%	99%	100%
response_time	0.010s	0.052s	0.201s	1.484s	3.118s
mean = 0.1130

branch

all items: 13630
percentiles	10%	50%	90%	99%	100%
response_time	0.011s	0.068s	0.249s	1.520s	3.213s
mean = 0.1324

We can see that in average timings increased by ~15%. The good news that for long routes (more important metric) it's only ~10% increase.

What is the performance impact of computing 2 additional distances?

I didn't check it, but I think it's unnoticeable.

In dense environments one generally has to travel less distance to move up to the next hierarchy - counting upward hierarchy transitions ensures enough candidates are found. Similarly in rural environments one has to generally travel further to ensure enough transitions onto higher class roads are made.

I agree with that. But for some cases in dense environments we exhaust transition count limit too fast (look at the example in the issue #3075 , the local road we skipped is very close to the destination point but the limits were exhausted before we got it). So, my point here is the following:
near the origin or the destination point optimal route can use lower level and higher level roads (but in the middle of the route it should be only higher level roads). Current logic doesn't guarantee that for dense places all lower level roads near the origin/destination will be expanded, so I used distance threshold for that purpose.

You probably don't need absolute distance - rather you perhaps could avoid sqrt calls for these 2 by using distance squared and configuring the hierarchy distances to be squared distance. Maybe do a performance comparison between using GetDistance and GetDistanceSquared (I think you need a new method in astarheuristic.h). I just remember through the years doing a lot of work to avoid sqrt calls as much as possible.

Also, is there a way to avoid computing these distances for modes that do not use hierarchies (pedestrian, bicycle)?

I just did a comparison with bicycle routes and noted a 6.7% drop in performance with no change in the route and no change in the number of EdgeLabels added. So this PR drops bicycle routing performance significantly with no impact to the actual route computation. I think this is almost entirely due to the cost of the new GetDistance calls - there may be a slight cost to propogate into EdgeLabel but otherwise there is no change.

Also, is there a way to avoid computing these distances for modes that do not use hierarchies (pedestrian, bicycle)?

I just did a comparison with bicycle routes and noted a 6.7% drop in performance with no change in the route and no change in the number of EdgeLabels added. So this PR drops bicycle routing performance significantly with no impact to the actual route computation. I think this is almost entirely due to the cost of the new GetDistance calls - there may be a slight cost to propogate into EdgeLabel but otherwise there is no change.

how did you test performance for bicycles ? did you generate some random routes or use from test_requests folder ?

I test a single, long bicycle route that I have tracked performance on for several years. I use valhalla_run_route with multi-run set to 100. This will then average the PathAlgorithm time over 100 successive calls (ignores the first to make sure all data is in cache). Obviosuly this doesn't cover a wide range of conditions (e.g. road densities, etc.) but it fully stresses just the PathAlgorithm - there is no I/O and CPU is 100% for the one thread computing the route. I also did this for auto routes while at Mapzen and Mapbox so that I could track performance of a known route over time - comparing code changes and data set changes.

The command is:

./valhalla_run_route --config ../../conf/planetv14.json --multi-run 100 -j '{"locations":[{"lat":39.64225,"lon":-76.10536,"type":"break"},{"lat":38.899677,"lon":-77.050916,"type":"break"}],"costing":"bicycle","costing_options":{"bicycle":{"bicycle_type":"Road","use_roads":"0.0","cycling_speed":"25.0","use_hills":"0.5"}}}' | grep GetBestPath

I test a single, long bicycle
The command is:

./valhalla_run_route --config ../../conf/planetv14.json --multi-run 100 -j '{"locations":[{"lat":39.64225,"lon":-76.10536,"type":"break"},{"lat":38.899677,"lon":-77.050916,"type":"break"}],"costing":"bicycle","costing_options":{"bicycle":{"bicycle_type":"Road","use_roads":"0.0","cycling_speed":"25.0","use_hills":"0.5"}}}' | grep GetBestPath

Thank you! will try the same.

hm, I'm getting not very stable results with a such test. variance is about 10%.

Instead of that I created requests.txt file with the bicycle request which is repeated 1000 times. Here results were more stable (variance less than 1%). So, I didn't catch the difference between cases when we use pure distance and squared.

I always reboot my laptop (so all other apps are stopped) and make sure no browsers are open prior to running this benchmark. When I do that I get very good consistency between results (usually only vary by a couple ms for the request).

I always reboot my laptop (so all other apps are stopped) and make sure no browsers are open prior to running this benchmark. When I do that I get very good consistency between results (usually only vary by a couple ms for the request).

did the same. So, results became more stable, but less than using run_with_server.py script. any case, I got the following:
master (4 runs)

2021/06/21 12:26:27.002326 [INFO] PathAlgorithm GetBestPath took 706 ms
2021/06/21 12:27:34.603899 [INFO] PathAlgorithm GetBestPath average: 650 ms
2021/06/21 12:27:36.203482 [INFO] PathAlgorithm GetBestPath took 714 ms
2021/06/21 12:28:43.844173 [INFO] PathAlgorithm GetBestPath average: 650 ms
2021/06/21 12:28:45.446597 [INFO] PathAlgorithm GetBestPath took 714 ms
2021/06/21 12:29:54.289498 [INFO] PathAlgorithm GetBestPath average: 662 ms
2021/06/21 12:29:55.912541 [INFO] PathAlgorithm GetBestPath took 728 ms
2021/06/21 12:31:04.902405 [INFO] PathAlgorithm GetBestPath average: 663 ms

mean = 656.25, std = 6.26

branch

2021/06/21 12:32:56.320354 [INFO] PathAlgorithm GetBestPath took 700 ms
2021/06/21 12:34:03.447519 [INFO] PathAlgorithm GetBestPath average: 646 ms
2021/06/21 12:34:05.018854 [INFO] PathAlgorithm GetBestPath took 717 ms
2021/06/21 12:35:12.692285 [INFO] PathAlgorithm GetBestPath average: 651 ms
2021/06/21 12:35:14.274132 [INFO] PathAlgorithm GetBestPath took 717 ms
2021/06/21 12:36:22.092979 [INFO] PathAlgorithm GetBestPath average: 653 ms
2021/06/21 12:36:23.671287 [INFO] PathAlgorithm GetBestPath took 720 ms
2021/06/21 12:37:34.180110 [INFO] PathAlgorithm GetBestPath average: 679 ms

mean = 657.25, std = 12.81

It's almost the same, but I agree that we can avoid distance calculation for cases when hierarchy limits are disabled (bicycle and pedestrian).

@dnesbitt61 @kevinkreiser I've finished with RAD tests. I ran locally (with my local planet) ~14000 requests for auto costing model. I got 561 differences in ETA, where 386 were better than in master and 175 worse. It was kind of unexpected for me, actually I expected that almost all routes should be improved (by ETA). Then I selected top 30 routes with increased ETA and top 30 routes with decreased ETA and looked at each of them manually.

Most significant improvements in ETA were achieved on routes that include ferries or country crossing (I suspect because near ferries or country borders lie lower level edges that were covered by the branch and missed by master).
There were also several small differences near the origin or destination. This is because we're traversing more lower level edges near origin or destination points that guarantees local optimality near these points.

Each route with downgraded ETA can be explained in one of the following ways:

ETA is bigger but the route cost is smaller.

It turned out that for some routes cost were improved but ETA not. As far as our actual score is cost, we can treat such routes as improved.

Bidirectional astar stops iterating too early.

This is well known problem #2928. For some routes, when I temporary fixed cost threshold in the branch (or even enabled alternatives that extend cost threshold) I got the same routes as in master.

Inaccurate shortcut's costs.

Cost for some shortcuts may be slightly different from the sum of costs of superseded edges. Due to the changes in hierarchy limits logic some shortcuts may be still unavailable in branch (https://github.com/valhalla/valhalla/blob/master/src/thor/bidirectional_astar.cc#L166) because they lie too close to the origin/destination point but may be used in master. In some cases it may lead to different optimal routes.

Hierarchy limits + multiple starting edges.

We initialize forward/reverse search with different starting edges. For each edge we calculate initial cost (equal to squared distance from the origin/destination point to the edge). In some cases initial cost can be very big. It may lead to a very unbalanced search and a situation when we complete a route before exhaust hierarchy limits. So, we can miss local optimality near the origin/destination point. I think this is a separate issue that shouldn't be fixed in this PR.

@kevinkreiser do you know why prime_server build is failing on osx ? https://app.circleci.com/pipelines/github/valhalla/valhalla/7155/workflows/bf03b7a0-942a-4b47-9e1b-800458f85419/jobs/44939

This looks fine to me but I can only really test bicycle routing. No performance difference in my use case. I don't create data with hierarchies so that was expected/desired.

thanks!

Bidirectional astar stops iterating too early.

I know what you mean by this problem but are you saying that this happens more frequently with this branch? I am missing the bigger point about what you were seeing with respect to this problem in the branch. Can you maybe reiterate?

Hierarchy limits + multiple starting edges.

That one is a long standing problem. Its very hard to tune the penalty to make sense. Originally i had it set to be walking speed cost of straight line distance to the snap point but this was sometimes not enough penalty. That is why we have options to disable the penality (which is a bandaid but at least it gives the option).

Bidirectional astar stops iterating too early.

I know what you mean by this problem but are you saying that this happens more frequently with this branch? I am missing the bigger point about what you were seeing with respect to this problem in the branch. Can you maybe reiterate?

I don't say that for this branch it happens more frequently. I just analyzed downgraded routes and for some of them it was a reason. That's expected to me.

Hierarchy limits + multiple starting edges.

That one is a long standing problem. Its very hard to tune the penalty to make sense. Originally i had it set to be walking speed cost of straight line distance to the snap point but this was sometimes not enough penalty. That is why we have options to disable the penality (which is a bandaid but at least it gives the option).

As for me, it worth a separate issue. And, actually there are 2 problems here:

1. unbalanced search;
2. nonoptimal routes due to unbalanced search + hierarchy limits.

@kevinkreiser did I answer your question? Or some more clarifications are needed ?