Skip to content

Instantly share code, notes, and snippets.

@easbar

easbar/fast_paths_abstreet_performance.md

Last active September 13, 2021 05:53
Show Gist options
  • Save easbar/a7980e834206b6065e848ba29e228fdd to your computer and use it in GitHub Desktop.
Save easbar/a7980e834206b6065e848ba29e228fdd to your computer and use it in GitHub Desktop.
Download ZIP
Raw
fast_paths_abstreet_performance.md
  • nr = max_settled_nodes_neighbor_relevance
  • nc = max_settled_nodes_contraction
  • nco = max_settled_nodes_contraction_with_order

bike

nodes edges nr nc nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
25459 44371 0 0 0 230995 240947 38651 307 1262 308
25459 44371 0 1 1 230995 240947 40905 317 801 314
25459 44371 0 3 3 241798 248331 68862 350 1154 364
25459 44371 0 5 5 244203 264733 101215 454 1861 416
25459 44371 0 10 10 197972 259441 79115 440 2041 433
25459 44371 0 30 30 140755 171070 16324 247 1482 255
25459 44371 0 50 50 120009 137368 4669 182 1004 183
25459 44371 0 100 100 116119 120025 2474 142 931 141
25459 44371 1 0 0 140687 141358 7139 137 219 139
25459 44371 1 1 1 140687 141358 7128 148 181 141
25459 44371 1 3 3 124034 132720 5486 126 228 118
25459 44371 1 5 5 122686 126953 7185 119 248 120
25459 44371 1 10 10 108005 120820 5362 103 292 111
25459 44371 1 30 30 97242 105199 3367 105 374 111
25459 44371 1 50 50 93964 98286 1724 80 379 91
25459 44371 1 100 100 90876 93078 1591 78 378 84
25459 44371 5 0 0 119645 112534 4630 76 99 76
25459 44371 5 1 1 119645 112534 4335 73 105 76
25459 44371 5 3 3 105937 101401 3725 78 95 59
25459 44371 5 5 5 98673 95468 3574 77 129 60
25459 44371 5 10 10 91675 91849 3296 83 157 85
25459 44371 5 30 30 82205 81545 1765 58 184 57
25459 44371 5 50 50 79396 79275 1368 51 200 51
25459 44371 5 100 100 78913 76560 1193 46 201 47
25459 44371 10 0 0 129769 118868 8251 82 113 84
25459 44371 10 1 1 129769 118868 7294 84 119 84
25459 44371 10 3 3 114821 106335 7359 77 133 77
25459 44371 10 5 5 104186 100009 5661 74 146 73
25459 44371 10 10 10 87970 87605 3738 65 139 65
25459 44371 10 30 30 79260 78068 2050 54 167 55
25459 44371 10 50 50 76273 74673 1510 49 170 50
25459 44371 10 100 100 75007 73357 1119 34 150 37
25459 44371 50 0 0 220272 185633 168180 139 489 140
25459 44371 50 1 1 220272 185633 168661 140 381 132
25459 44371 50 3 3 180440 147051 92140 140 337 149
25459 44371 50 5 5 153038 132461 58446 113 330 101
25459 44371 50 10 10 121862 107900 38337 92 245 109
25459 44371 50 30 30 81865 80441 7561 66 282 67
25459 44371 50 50 50 72845 73245 3126 47 240 45
25459 44371 50 100 100 71449 71739 2590 41 174 44
25459 44371 100 0 0 309075 237843 879189 233 1458 221
25459 44371 100 1 1 309075 237843 878638 230 880 229

bus

nodes edges nr nc nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
25459 42710 0 0 0 220966 212901 35577 279 1171 280
25459 42710 0 1 1 220966 212901 36028 273 707 271
25459 42710 0 3 3 217888 219106 48366 288 1009 302
25459 42710 0 5 5 197641 242409 71800 328 1486 338
25459 42710 0 10 10 151200 184626 29135 272 1077 293
25459 42710 0 30 30 109826 137249 7471 190 805 196
25459 42710 0 50 50 102324 115570 3588 144 774 145
25459 42710 0 100 100 94618 96467 1811 117 493 99
25459 42710 1 0 0 128002 131860 6638 114 200 113
25459 42710 1 1 1 128002 131860 7240 113 171 116
25459 42710 1 3 3 111007 115016 3532 97 180 97
25459 42710 1 5 5 111422 118864 6586 108 240 109
25459 42710 1 10 10 100014 112047 7285 112 300 117
25459 42710 1 30 30 81121 87739 2208 88 264 74
25459 42710 1 50 50 79512 84389 1630 78 319 82
25459 42710 1 100 100 78112 79188 1216 66 317 65
25459 42710 5 0 0 112206 104704 4357 64 91 64
25459 42710 5 1 1 112206 104704 4170 66 93 65
25459 42710 5 3 3 99624 95447 2967 64 111 73
25459 42710 5 5 5 92143 90808 2987 66 122 76
25459 42710 5 10 10 81150 79881 1942 58 132 58
25459 42710 5 30 30 70719 70972 1165 45 153 46
25459 42710 5 50 50 68488 67526 941 43 158 43
25459 42710 5 100 100 66931 65890 828 40 185 41
25459 42710 10 0 0 125950 115038 8304 92 116 87
25459 42710 10 1 1 125950 115038 9889 85 118 84
25459 42710 10 3 3 110460 101662 8255 80 136 80
25459 42710 10 5 5 95160 91029 4559 66 121 67
25459 42710 10 10 10 79601 78679 2911 63 137 65
25459 42710 10 30 30 67518 67280 1266 42 210 40
25459 42710 10 50 50 65959 65010 974 36 124 39
25459 42710 10 100 100 65205 64079 931 34 167 38
25459 42710 50 0 0 217812 177190 153777 143 466 139
25459 42710 50 1 1 217812 177190 156266 137 321 129
25459 42710 50 3 3 187768 148990 113406 126 378 128
25459 42710 50 5 5 157891 132710 83940 132 572 105
25459 42710 50 10 10 121633 101812 47894 113 293 113
25459 42710 50 30 30 70800 69280 4211 51 184 59
25459 42710 50 50 50 62878 62934 2377 48 136 32
25459 42710 50 100 100 61705 61650 2096 36 193 34
25459 42710 100 0 0 308315 270126 1074157 197 1692 207
25459 42710 100 1 1 308315 270126 1051465 219 1126 220

car

nodes edges nr nc nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
25459 42644 0 0 0 223497 207240 36371 296 1151 271
25459 42644 0 1 1 223497 207240 35851 300 726 302
25459 42644 0 3 3 228681 261814 95472 378 1510 391
25459 42644 0 5 5 204221 250619 78697 375 1478 345
25459 42644 0 10 10 174567 206349 56466 332 1630 321
25459 42644 0 30 30 104279 127623 5707 157 826 157
25459 42644 0 50 50 95326 107129 2325 118 608 115
25459 42644 0 100 100 91102 96892 1611 99 602 98
25459 42644 1 0 0 128927 132802 7013 121 192 138
25459 42644 1 1 1 128927 132802 7041 124 189 125
25459 42644 1 3 3 112650 119255 4381 114 175 113
25459 42644 1 5 5 108925 113843 4760 91 194 92
25459 42644 1 10 10 104027 114280 8575 134 315 142
25459 42644 1 30 30 80331 87650 1559 72 291 79
25459 42644 1 50 50 77371 80578 1176 60 232 56
25459 42644 1 100 100 76862 77648 1070 60 299 65
25459 42644 5 0 0 111503 104374 4389 63 89 63
25459 42644 5 1 1 111503 104374 4546 75 98 67
25459 42644 5 3 3 98258 95792 3773 74 115 74
25459 42644 5 5 5 90997 88768 3119 75 130 79
25459 42644 5 10 10 80128 79737 2199 58 127 58
25459 42644 5 30 30 69706 69145 1023 44 143 45
25459 42644 5 50 50 67555 66662 865 39 156 39
25459 42644 5 100 100 67110 65471 929 39 189 40
25459 42644 10 0 0 132300 118624 14295 90 137 94
25459 42644 10 1 1 132300 118624 14254 89 125 76
25459 42644 10 3 3 111853 103223 8350 87 139 89
25459 42644 10 5 5 95992 92043 5187 62 111 65
25459 42644 10 10 10 80760 79117 3538 61 131 63
25459 42644 10 30 30 66826 66067 1019 37 112 33
25459 42644 10 50 50 65161 64771 1068 37 146 39
25459 42644 10 100 100 64070 63719 1124 42 165 35
25459 42644 50 0 0 224113 182156 192965 140 507 141
25459 42644 50 1 1 224113 182156 188770 123 361 134
25459 42644 50 3 3 190070 154222 115224 129 403 122
25459 42644 50 5 5 157618 128270 83075 126 354 134
25459 42644 50 10 10 113196 100186 31227 89 266 103
25459 42644 50 30 30 70272 68549 4793 52 169 52
25459 42644 50 50 50 62461 62268 2023 41 189 41
25459 42644 50 100 100 60864 60993 1941 36 150 34
25459 42644 100 0 0 337389 268129 1204535 228 1810 228

walk

nodes edges nr nc nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
50368 126481 0 0 0 239928 239927 3085 101 282 100
50368 126481 0 1 1 239928 239927 3273 109 288 110
50368 126481 0 3 3 215376 216496 4221 116 345 117
50368 126481 0 5 5 204827 215218 6603 147 481 145
50368 126481 0 10 10 181510 189875 3710 140 470 136
50368 126481 0 30 30 150580 152613 769 65 365 66
50368 126481 0 50 50 147456 148457 659 53 303 53
50368 126481 0 100 100 145297 145582 660 53 340 53
50368 126481 1 0 0 221976 221975 3756 80 186 72
50368 126481 1 1 1 221976 221975 3249 83 212 80
50368 126481 1 3 3 200543 201954 4511 113 264 114
50368 126481 1 5 5 186396 188014 3544 84 269 85
50368 126481 1 10 10 169260 173935 2913 80 316 80
50368 126481 1 30 30 148610 149502 1145 49 268 43
50368 126481 1 50 50 146134 146522 785 44 310 44
50368 126481 1 100 100 144114 144293 817 60 370 48
50368 126481 5 0 0 233922 233921 6531 75 205 76
50368 126481 5 1 1 233922 233921 6506 75 237 81
50368 126481 5 3 3 200124 195341 5772 78 243 80
50368 126481 5 5 5 181024 177952 5360 84 239 78
50368 126481 5 10 10 159652 160514 3064 70 278 70
50368 126481 5 30 30 140306 141067 1101 39 281 39
50368 126481 5 50 50 137503 137790 958 36 274 36
50368 126481 5 100 100 135852 135958 990 35 286 35
50368 126481 10 0 0 251015 251014 11865 91 277 76
50368 126481 10 1 1 251015 251014 11463 77 282 77
50368 126481 10 3 3 213921 208575 12416 79 269 76
50368 126481 10 5 5 190586 187157 9731 87 283 80
50368 126481 10 10 10 159548 158626 3721 60 261 69
50368 126481 10 30 30 137824 138176 1120 34 256 36
50368 126481 10 50 50 135363 135615 1277 34 319 37
50368 126481 10 100 100 133586 133760 1113 32 255 32
50368 126481 50 0 0 377796 377795 155536 129 688 130
50368 126481 50 1 1 377796 377795 163438 130 707 127
50368 126481 50 3 3 316614 289675 176336 135 575 129
50368 126481 50 5 5 281111 258395 180074 139 680 150
50368 126481 50 10 10 210731 202395 58549 111 546 112
50368 126481 50 30 30 142736 143150 5859 68 380 53
50368 126481 50 50 50 133026 133303 1992 36 271 39
50368 126481 50 100 100 130890 130943 1820 46 400 48
50368 126481 100 0 0 503645 503644 860460 226 1853 228

hierarchy depth factor

  • nr = max_settled_nodes_neighbor_relevance
  • nc = max_settled_nodes_contraction
  • nco = max_settled_nodes_contraction_with_order
  • hdf = hierarchy_depth_factor

bike

nodes edges nr nc hdf nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
25459 44371 10 100 0.001 100 70615 69216 842 46 140 47
25459 44371 10 100 0.002 100 71270 70090 967 41 158 41
25459 44371 10 100 0.005 100 71131 69797 967 45 156 45
25459 44371 10 100 0.007 100 70846 69668 918 36 149 37
25459 44371 10 100 0.01 100 71629 69948 961 44 148 46
25459 44371 10 100 0.015 100 71818 71043 1061 41 162 40
25459 44371 10 100 0.02 100 72621 70854 1021 38 146 42
25459 44371 10 100 0.05 100 73429 72722 1194 44 162 43
25459 44371 10 100 0.07 100 74501 72584 1183 43 264 48
25459 44371 10 100 0.1 100 75007 73357 1268 42 180 44
25459 44371 10 100 0.15 100 76207 75009 1155 33 151 34
25459 44371 10 100 0.2 100 77856 75677 1235 38 184 41
25459 44371 10 100 0.3 100 79519 77676 1317 36 171 39
25459 44371 10 100 0.5 100 84472 81774 1969 42 211 46
25459 44371 10 100 0.7 100 86575 84352 2185 47 224 47
25459 44371 10 100 1 100 90014 87142 2463 59 456 58

bus

nodes edges nr nc hdf nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
25459 42710 10 100 0.001 100 61422 60115 808 43 141 44
25459 42710 10 100 0.002 100 61394 60461 762 35 142 36
25459 42710 10 100 0.005 100 61226 60475 750 35 138 35
25459 42710 10 100 0.007 100 61838 60753 773 41 148 42
25459 42710 10 100 0.01 100 61739 60991 709 34 127 32
25459 42710 10 100 0.015 100 62144 61238 820 37 146 37
25459 42710 10 100 0.02 100 62074 61533 828 34 141 34
25459 42710 10 100 0.05 100 63120 62702 887 35 152 34
25459 42710 10 100 0.07 100 63553 62533 776 29 134 30
25459 42710 10 100 0.1 100 65205 64079 1099 38 181 37
25459 42710 10 100 0.15 100 65874 65309 937 35 167 35
25459 42710 10 100 0.2 100 67425 66056 1113 34 173 35
25459 42710 10 100 0.3 100 68798 67703 1099 37 185 37
25459 42710 10 100 0.5 100 72125 71160 1710 34 172 35
25459 42710 10 100 0.7 100 73831 73161 1621 39 217 39
25459 42710 10 100 1 100 76592 75034 1638 42 476 41

car

nodes edges nr nc hdf nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
25459 42644 10 100 0.001 100 60698 60083 715 41 141 41
25459 42644 10 100 0.002 100 60966 60049 926 39 125 36
25459 42644 10 100 0.005 100 60911 60405 734 37 138 36
25459 42644 10 100 0.007 100 61038 60120 742 37 136 37
25459 42644 10 100 0.01 100 61070 60192 664 32 143 35
25459 42644 10 100 0.015 100 61192 60589 785 36 146 38
25459 42644 10 100 0.02 100 61597 60975 826 35 140 36
25459 42644 10 100 0.05 100 62762 62060 862 34 144 34
25459 42644 10 100 0.07 100 63082 62647 811 34 153 35
25459 42644 10 100 0.1 100 64070 63719 954 35 154 33
25459 42644 10 100 0.15 100 65177 64309 967 37 216 34
25459 42644 10 100 0.2 100 66240 65246 1056 37 167 37
25459 42644 10 100 0.3 100 68321 67464 1226 37 177 37
25459 42644 10 100 0.5 100 70989 70176 1249 35 176 39
25459 42644 10 100 0.7 100 73553 72264 1363 36 177 37
25459 42644 10 100 1 100 75265 74314 1563 43 361 50

walk

nodes edges nr nc hdf nco fast_graph_out fast_graph_in prep (ms) query (μs) prep order (ms) query order (μs)
50368 126481 10 100 0.001 100 123384 123613 901 45 224 45
50368 126481 10 100 0.002 100 123513 123667 783 34 207 37
50368 126481 10 100 0.005 100 123525 123645 880 34 219 35
50368 126481 10 100 0.007 100 123787 123909 874 34 218 34
50368 126481 10 100 0.01 100 124209 124345 892 35 228 35
50368 126481 10 100 0.015 100 124933 125010 984 34 224 35
50368 126481 10 100 0.02 100 125874 125951 892 33 224 34
50368 126481 10 100 0.05 100 129991 130092 970 31 234 31
50368 126481 10 100 0.07 100 132076 132126 1010 31 252 32
50368 126481 10 100 0.1 100 133586 133760 1133 36 237 28
50368 126481 10 100 0.15 100 139422 139573 1007 29 256 28
50368 126481 10 100 0.2 100 141189 141315 1178 33 282 34
50368 126481 10 100 0.3 100 146078 146198 1286 32 295 31
50368 126481 10 100 0.5 100 150877 151008 1393 33 328 33
50368 126481 10 100 0.7 100 155437 155587 1615 49 373 39
50368 126481 10 100 1 100 157287 157496 1893 39 365 39
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment