Skip to content

Instantly share code, notes, and snippets.

@mjjbell
Last active March 4, 2021 22:20
Show Gist options
  • Save mjjbell/85e9f4875935bf621a6c2ba341e96c02 to your computer and use it in GitHub Desktop.
Save mjjbell/85e9f4875935bf621a6c2ba341e96c02 to your computer and use it in GitHub Desktop.

See Project-OSRM/osrm-backend#5953 for details of the changes made and test setup used in the following performance analysis.

The results are for the Multi Level Dijkstra (MLD) algorithm.

@mjjbell
Copy link
Author

mjjbell commented Mar 4, 2021

Results - Trip

Running Trip on coordinate sets 1 and 2 is effectively finding the shortest route between two endpoints in either direction.

Coordinate set 1

Request Duration

_trip - coordinate set #1

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 9637 10378 741 7.69%
10 17194 18555 1361 7.92%
20 19794 21239 1445 7.30%
30 21800 23268 1468 6.73%
40 23571 25078 1507 6.39%
50 25189 26707 1518 6.03%
60 26694 28232 1538 5.76%
70 28281 29869 1588 5.62%
80 30355 31974 1619 5.33%
90 33383 34959 1576 4.72%
99 67270 40700 -26570 -39.50%
100 89903 87678 -2225 -2.47%

Smallest Route Weight

master same snap_candidates
0 20335 73

Coordinate set 2

Request Duration

_trip - coordinate set #2

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 10063 10746 683 6.79%
10 16785 17835 1050 6.26%
20 19341 20465 1124 5.81%
30 21371 22529 1158 5.42%
40 23132 24323 1191 5.15%
50 24722 25941 1219 4.93%
60 26160 27436 1276 4.88%
70 27609 28854 1245 4.51%
80 29437 30733 1296 4.40%
90 32259 33643 1384 4.29%
99 38896 39281 385 0.99%
100 87565 89950 2385 2.72%

Smallest Route Weight

master same snap_candidates
0 18923 296

Coordinate set 3

Request Duration

_trip - coordinate set #3

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 65446 70092 4646 7.10%
10 98615 105879 7264 7.37%
20 101209 108796 7587 7.50%
30 103043 110733 7690 7.46%
40 104631 112475 7844 7.50%
50 106071 114101 8030 7.57%
60 107556 115711 8155 7.58%
70 109112 117497 8385 7.68%
80 110892 119620 8728 7.87%
90 113269 122836 9567 8.45%
99 118833 161437 42604 35.85%
100 150740 200883 50143 33.26%

Smallest Route Weight

master same snap_candidates
4 15913 1470

Reduction in route weight, master to snap_candidates(4)

Coordinate set 4

Request Duration

_trip - coordinate set #4

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 719048 729341 10293 1.43%
10 835866 867492 31626 3.78%
20 850031 875895 25864 3.04%
30 860366 882237 21871 2.54%
40 869645 888036 18391 2.11%
50 876525 894257 17732 2.02%
60 882396 901358 18962 2.15%
70 888066 911344 23278 2.62%
80 894657 925679 31022 3.47%
90 902461 940728 38267 4.24%
99 923876 964312 40436 4.38%
100 1107637 1144079 36442 3.29%

Smallest Route Weight

master same snap_candidates
69 3370 4118

Reduction in route weight, master to snap_candidates(5)

Coordinate set 5

Request Duration

_trip - coordinate set #5

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 9552874 10112788 559914 5.86%
10 10568918 11213538 644620 6.10%
20 10621258 11303946 682688 6.43%
30 10657139 11598541 941402 8.83%
40 10695790 11673871 978081 9.14%
50 10723084 11706517 983433 9.17%
60 10761409 11746447 985038 9.15%
70 10846269 11782930 936661 8.64%
80 11139303 11814396 675093 6.06%
90 11245697 11861417 615720 5.48%
99 11374665 12010559 635894 5.59%
100 11635893 13516671 1880778 16.16%

Smallest Route Weight

master same snap_candidates
77 15 670

Reduction in route weight, master to snap_candidates(6)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment