Skip to content

Instantly share code, notes, and snippets.

@mjjbell

mjjbell/mld_performance_analysis.md

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.
Download ZIP
Raw
mld_performance_analysis.md

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 - Route

Coordinate set 1

Request Duration

_route - coordinate set #1

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 191 206 15 7.85%
10 2699 2677 -22 -0.82%
20 3811 3755 -56 -1.47%
30 4817 4739 -78 -1.62%
40 5731 5615 -116 -2.02%
50 6577 6438 -139 -2.11%
60 7363 7197 -166 -2.25%
70 8151 7949 -202 -2.48%
80 9017 8765 -252 -2.79%
90 10168 9821 -347 -3.41%
99 13128 11865 -1263 -9.62%
100 20409 61216 19262 -41954

Smallest Route Weight

master same snap_candidates
0 20339 69

Coordinate set 2

Request Duration

_route - coordinate set #2

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 254 263 9 3.54%
10 2574 2544 -30 -1.17%
20 3655 3603 -52 -1.42%
30 4664 4571 -93 -1.99%
40 5551 5426 -125 -2.25%
50 6383 6223 -160 -2.51%
60 7138 6952 -186 -2.61%
70 7881 7652 -229 -2.91%
80 8732 8460 -272 -3.11%
90 9824 9489 -335 -3.41%
99 12813 11544 -1269 -9.90%
100 62067 22891 -39176 -63.12%

Smallest Route Weight

master same snap_candidates
0 18985 234

Coordinate set 3

Request Duration

_route - coordinate set #3

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 20259 18610 -1649 -8.14%
10 72965 69544 -3421 -4.69%
20 79356 75579 -3777 -4.76%
30 84175 79994 -4181 -4.97%
40 88540 84097 -4443 -5.02%
50 92673 87791 -4882 -5.27%
60 96912 91527 -5385 -5.56%
70 102007 95714 -6293 -6.17%
80 108422 100979 -7443 -6.86%
90 119044 108129 -10915 -9.17%
99 154996 130629 -24367 -15.72%
100 189290 175303 -13987 -7.39%

Smallest Route Weight

master same snap_candidates
0 16381 1006

Coordinate set 4

Request Duration

_route - coordinate set #4

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 26027 24643 -1384 -5.32%
10 826175 802970 -23205 -2.81%
20 849155 826253 -22902 -2.70%
30 865527 844124 -21403 -2.47%
40 879508 859189 -20319 -2.31%
50 893439 874151 -19288 -2.16%
60 906356 887493 -18863 -2.08%
70 920765 901348 -19417 -2.11%
80 939201 918676 -20525 -2.19%
90 963488 942796 -20692 -2.15%
99 1022129 996668 -25461 -2.49%
100 1271754 1059575 -212179 -16.68%

Smallest Route Weight

master same snap_candidates
0 4562 2995

Reduction in route weight, master to snap_candidates(1)

Coordinate set 5

Request Duration

_route - coordinate set #5

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 246515 238028 -8487 -3.44%
10 7218184 6578807 -639377 -8.86%
20 8738214 8260482 -477732 -5.47%
30 8851087 8335135 -515952 -5.83%
40 8929549 8394167 -535382 -6.00%
50 9014303 8449014 -565289 -6.27%
60 9086152 8486446 -599706 -6.60%
70 9167710 8538946 -628764 -6.86%
80 9234377 8601204 -633173 -6.86%
90 9339052 8694945 -644107 -6.90%
99 9503115 8917490 -585625 -6.16%
100 9614365 9090437 -523928 -5.45%

Smallest Route Weight

master same snap_candidates
0 86 676

Reduction in route weight, master to snap_candidates

@mjjbell
Copy link
Author

mjjbell commented Mar 4, 2021 •
edited
Loading

Results - Route continue_straight=false

We start the results from coordinate set 3, as continue_straight=false will have no effect on waypoint lists of length two.

Coordinate set 3

Request Duration

_route continue_straight=false - coordinate set #3

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 25968 25684 -284 -1.09%
10 48777 48349 -428 -0.88%
20 52441 51936 -505 -0.96%
30 55186 54732 -454 -0.82%
40 57616 57075 -541 -0.94%
50 59956 59424 -532 -0.89%
60 62274 61647 -627 -1.01%
70 64748 64109 -639 -0.99%
80 67621 66936 -685 -1.01%
90 71858 70950 -908 -1.26%
99 85017 80024 -4993 -5.87%
100 147983 110495 -37488 -25.33%

Smallest Route Weight

master same snap_candidates
0 15990 1397

Coordinate set 4

Request Duration

_route continue_straight=false - coordinate set #4

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 39272 39500 228 0.58%
10 529232 527943 -1289 -0.24%
20 542929 541186 -1743 -0.32%
30 552660 550807 -1853 -0.34%
40 561330 559191 -2139 -0.38%
50 569271 567183 -2088 -0.37%
60 578132 576143 -1989 -0.34%
70 588247 585402 -2845 -0.48%
80 600690 597214 -3476 -0.58%
90 618845 614260 -4585 -0.74%
99 658436 652032 -6404 -0.97%
100 684868 746375 61507 8.98%

Smallest Route Weight

master same snap_candidates
0 3465 4092

Reduction in route weight, master to snap_candidates(2)

Coordinate set 5

Request Duration

_route continue_straight=false - coordinate set #5

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 277467 229236 -48231 -17.38%
10 5689477 5559239 -130238 -2.29%
20 5779226 5599639 -179587 -3.11%
30 5844208 5630572 -213636 -3.66%
40 5884572 5655901 -228671 -3.89%
50 5917350 5677855 -239495 -4.05%
60 5944903 5701768 -243135 -4.09%
70 5977675 5725726 -251949 -4.21%
80 6006590 5750340 -256250 -4.27%
90 6060820 5794069 -266751 -4.40%
99 6198503 5917515 -280988 -4.53%
100 6361507 6499697 138190 2.17%

Smallest Route Weight

master same snap_candidates
0 15 747

Reduction in route weight, master to snap_candidates(3)

@mjjbell
Copy link
Author

mjjbell commented Mar 4, 2021

Results - Table

N.B. Here we are not able to compare route weights, as the table response does not contain them. Instead we compare route durations. In some cases we do get shorter duration results with master. Upon inspection of these results, snap_candidates results have smaller weight.

Coordinate set 1

Request Duration

_table - coordinate set #1

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 9543 9687 144 1.51%
10 11218 11315 97 0.86%
20 11741 11844 103 0.88%
30 12411 12542 131 1.06%
40 12885 13035 150 1.16%
50 13393 13544 151 1.13%
60 14232 14428 196 1.38%
70 14684 14955 271 1.85%
80 15236 15496 260 1.71%
90 16375 16674 299 1.83%
99 39678 18660 -21018 -52.97%
100 68796 21505 -47291 -68.74%

Smallest Route Duration

master same snap_candidates
3 81495 134

Coordinate set 2

Request Duration

_table - coordinate set #2

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 9428 9356 -72 -0.76%
10 11229 11297 68 0.61%
20 11739 11813 74 0.63%
30 12374 12465 91 0.74%
40 12871 12989 118 0.92%
50 13413 13522 109 0.81%
60 14265 14444 179 1.25%
70 14731 14973 242 1.64%
80 15275 15544 269 1.76%
90 16402 16726 324 1.98%
99 20892 18974 -1918 -9.18%
100 67241 66555 -686 -1.02%

Smallest Route Duration

master same snap_candidates
1 76415 460

Coordinate set 3

Request Duration

_table - coordinate set #3

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 62562 62323 -239 -0.38%
10 73624 73074 -550 -0.75%
20 75461 75102 -359 -0.48%
30 76864 76632 -232 -0.30%
40 78061 77918 -143 -0.18%
50 79184 79159 -25 -0.03%
60 80332 80396 64 0.08%
70 81550 81825 275 0.34%
80 82997 83531 534 0.64%
90 85090 86231 1141 1.34%
99 89937 127111 37174 41.33%
100 125075 142601 17526 14.01%

Smallest Route Duration

master same snap_candidates
81 2080480 23266

Coordinate set 4

Request Duration

_table - coordinate set #4

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 733529 724432 -9097 -1.24%
10 766979 761122 -5857 -0.76%
20 774666 768969 -5697 -0.74%
30 780960 775088 -5872 -0.75%
40 786560 780583 -5977 -0.76%
50 792538 786469 -6069 -0.77%
60 800181 793287 -6894 -0.86%
70 809528 802312 -7216 -0.89%
80 820908 817684 -3224 -0.39%
90 835112 833243 -1869 -0.22%
99 855010 858603 3593 0.42%
100 1039140 1036650 -2490 -0.24%

Smallest Route Duration

master same snap_candidates
3840 76183721 901396

Coordinate set 5

Request Duration

_table - coordinate set #5

Percentile master (μs) snap_candidates (μs) diff (μs) % diff
0 9987989 9969406 -18583 -0.19%
10 10055301 10247058 191757 1.91%
20 10102091 10296925 194834 1.93%
30 10137060 10337673 200613 1.98%
40 10165482 10379846 214364 2.11%
50 10201108 10415049 213941 2.10%
60 10253334 10478485 225151 2.20%
70 10400480 10611614 211134 2.03%
80 10641719 10735836 94117 0.88%
90 10716611 10837811 121200 1.13%
99 10867009 11000653 133644 1.23%
100 11111950 11287640 175690 1.58%

Smallest Route Duration

master same snap_candidates
38163 754484539 9002060

@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