Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

LMApproximator overhead #2973

Open
otbutz opened this issue Apr 15, 2024 · 3 comments · May be fixed by #2983
Open

LMApproximator overhead #2973

otbutz opened this issue Apr 15, 2024 · 3 comments · May be fixed by #2983

Comments

@otbutz
Copy link
Contributor

otbutz commented Apr 15, 2024

The overhead of the LMApproximator using DistanceCalcEarth for its BeelineWeightApproximator seems to be quite substantial:

grafik

Would it be possible to use DistancePlaneProjection instead?
@easbar
Copy link
Member

easbar commented Apr 15, 2024

I think I tried this at least once before, but was never able to measure an actual difference in performance.

@otbutz otbutz mentioned this issue Apr 17, 2024
Closed
@otbutz
Copy link
Contributor Author

otbutz commented Apr 18, 2024

Benchmarked with Germany:

DistanceCalcEarth (master)

    "routingLM12.air_distance_mean" : 316376.94,
    "routingLM12.alternative_rate" : 0.0,
    "routingLM12.distance_max" : 914021,
    "routingLM12.distance_mean" : 416693.53,
    "routingLM12.distance_min" : 53599,
    "routingLM12.failed_count" : 0,
    "routingLM12.guessed_algorithm" : "astarbi",
    "routingLM12.max" : 1031.563426,
    "routingLM12.mean" : 92.062360392,
    "routingLM12.min" : 3.254063,
    "routingLM12.sum" : 23015.590098,
    "routingLM12.visited_nodes_max" : 1020286.0,
    "routingLM12.visited_nodes_mean" : 101094.77,
    "routingLM12_alt.air_distance_mean" : 324986.8,
    "routingLM12_alt.alternative_rate" : 2.0,
    "routingLM12_alt.distance_max" : 826770,
    "routingLM12_alt.distance_mean" : 865228.6,
    "routingLM12_alt.distance_min" : 244616,
    "routingLM12_alt.failed_count" : 0,
    "routingLM12_alt.guessed_algorithm" : "astarbi",
    "routingLM12_alt.max" : 26939.2914,
    "routingLM12_alt.mean" : 6366.9998749999995,
    "routingLM12_alt.min" : 1948.363507,
    "routingLM12_alt.sum" : 63669.99875,
    "routingLM12_alt.visited_nodes_max" : 1.60165E7,
    "routingLM12_alt.visited_nodes_mean" : 4188019.5,
    "routingLM12_alt_edge.air_distance_mean" : 324986.8,
    "routingLM12_alt_edge.alternative_rate" : 2.0,
    "routingLM12_alt_edge.distance_max" : 826770,
    "routingLM12_alt_edge.distance_mean" : 865138.2,
    "routingLM12_alt_edge.distance_min" : 244616,
    "routingLM12_alt_edge.failed_count" : 0,
    "routingLM12_alt_edge.guessed_algorithm" : "astarbi",
    "routingLM12_alt_edge.max" : 94947.77928,
    "routingLM12_alt_edge.mean" : 22229.3876304,
    "routingLM12_alt_edge.min" : 6632.955266,
    "routingLM12_alt_edge.sum" : 222293.876304,
    "routingLM12_alt_edge.visited_nodes_max" : 3.557357E7,
    "routingLM12_alt_edge.visited_nodes_mean" : 9198762.0,
    "routingLM12_edge.air_distance_mean" : 316376.94,
    "routingLM12_edge.alternative_rate" : 0.0,
    "routingLM12_edge.distance_max" : 914021,
    "routingLM12_edge.distance_mean" : 416622.34,
    "routingLM12_edge.distance_min" : 53599,
    "routingLM12_edge.failed_count" : 0,
    "routingLM12_edge.guessed_algorithm" : "astarbi",
    "routingLM12_edge.max" : 3852.492645,
    "routingLM12_edge.mean" : 283.204306744,
    "routingLM12_edge.min" : 4.126827,
    "routingLM12_edge.sum" : 70801.076686,
    "routingLM12_edge.visited_nodes_max" : 2096962.0,
    "routingLM12_edge.visited_nodes_mean" : 203694.23,
    "routingLM4.air_distance_mean" : 316376.94,
    "routingLM4.alternative_rate" : 0.0,
    "routingLM4.distance_max" : 914021,
    "routingLM4.distance_mean" : 416693.53,
    "routingLM4.distance_min" : 53599,
    "routingLM4.failed_count" : 0,
    "routingLM4.guessed_algorithm" : "astarbi",
    "routingLM4.max" : 1136.424316,
    "routingLM4.mean" : 96.635791928,
    "routingLM4.min" : 3.326033,
    "routingLM4.sum" : 24158.947982,
    "routingLM4.visited_nodes_max" : 1015184.0,
    "routingLM4.visited_nodes_mean" : 111462.01,
    "routingLM4_alt.air_distance_mean" : 324986.8,
    "routingLM4_alt.alternative_rate" : 2.0,
    "routingLM4_alt.distance_max" : 826770,
    "routingLM4_alt.distance_mean" : 867216.2,
    "routingLM4_alt.distance_min" : 244616,
    "routingLM4_alt.failed_count" : 0,
    "routingLM4_alt.guessed_algorithm" : "astarbi",
    "routingLM4_alt.max" : 24420.295967,
    "routingLM4_alt.mean" : 5624.1070828,
    "routingLM4_alt.min" : 1751.430174,
    "routingLM4_alt.sum" : 56241.070828,
    "routingLM4_alt.visited_nodes_max" : 1.6360458E7,
    "routingLM4_alt.visited_nodes_mean" : 4231704.0,
    "routingLM4_alt_edge.air_distance_mean" : 324986.8,
    "routingLM4_alt_edge.alternative_rate" : 2.0,
    "routingLM4_alt_edge.distance_max" : 826770,
    "routingLM4_alt_edge.distance_mean" : 864737.2,
    "routingLM4_alt_edge.distance_min" : 244616,
    "routingLM4_alt_edge.failed_count" : 0,
    "routingLM4_alt_edge.guessed_algorithm" : "astarbi",
    "routingLM4_alt_edge.max" : 86817.804512,
    "routingLM4_alt_edge.mean" : 19948.8597405,
    "routingLM4_alt_edge.min" : 6315.177194,
    "routingLM4_alt_edge.sum" : 199488.597405,
    "routingLM4_alt_edge.visited_nodes_max" : 3.6045144E7,
    "routingLM4_alt_edge.visited_nodes_mean" : 9260096.0,
    "routingLM4_edge.air_distance_mean" : 316376.94,
    "routingLM4_edge.alternative_rate" : 0.0,
    "routingLM4_edge.distance_max" : 914021,
    "routingLM4_edge.distance_mean" : 416622.34,
    "routingLM4_edge.distance_min" : 53599,
    "routingLM4_edge.failed_count" : 0,
    "routingLM4_edge.guessed_algorithm" : "astarbi",
    "routingLM4_edge.max" : 3517.975164,
    "routingLM4_edge.mean" : 284.33085598400004,
    "routingLM4_edge.min" : 3.914209,
    "routingLM4_edge.sum" : 71082.713996,
    "routingLM4_edge.visited_nodes_max" : 2043466.0,
    "routingLM4_edge.visited_nodes_mean" : 225164.77,
    "routingLM8.air_distance_mean" : 316376.94,
    "routingLM8.alternative_rate" : 0.0,
    "routingLM8.distance_max" : 914021,
    "routingLM8.distance_mean" : 416693.53,
    "routingLM8.distance_min" : 53599,
    "routingLM8.failed_count" : 0,
    "routingLM8.guessed_algorithm" : "astarbi",
    "routingLM8.max" : 981.782023,
    "routingLM8.mean" : 91.583882,
    "routingLM8.min" : 3.149981,
    "routingLM8.sum" : 22895.9705,
    "routingLM8.visited_nodes_max" : 1006692.0,
    "routingLM8.visited_nodes_mean" : 101226.17,
    "routingLM8_alt.air_distance_mean" : 324986.8,
    "routingLM8_alt.alternative_rate" : 2.0,
    "routingLM8_alt.distance_max" : 826770,
    "routingLM8_alt.distance_mean" : 865228.6,
    "routingLM8_alt.distance_min" : 244616,
    "routingLM8_alt.failed_count" : 0,
    "routingLM8_alt.guessed_algorithm" : "astarbi",
    "routingLM8_alt.max" : 24142.541178,
    "routingLM8_alt.mean" : 5661.6324046,
    "routingLM8_alt.min" : 1755.481453,
    "routingLM8_alt.sum" : 56616.324046,
    "routingLM8_alt.visited_nodes_max" : 1.590316E7,
    "routingLM8_alt.visited_nodes_mean" : 4157924.5,
    "routingLM8_alt_edge.air_distance_mean" : 324986.8,
    "routingLM8_alt_edge.alternative_rate" : 2.0,
    "routingLM8_alt_edge.distance_max" : 826770,
    "routingLM8_alt_edge.distance_mean" : 865138.2,
    "routingLM8_alt_edge.distance_min" : 244616,
    "routingLM8_alt_edge.failed_count" : 0,
    "routingLM8_alt_edge.guessed_algorithm" : "astarbi",
    "routingLM8_alt_edge.max" : 86756.621042,
    "routingLM8_alt_edge.mean" : 20262.907914,
    "routingLM8_alt_edge.min" : 6339.359972,
    "routingLM8_alt_edge.sum" : 202629.07914,
    "routingLM8_alt_edge.visited_nodes_max" : 3.532676E7,
    "routingLM8_alt_edge.visited_nodes_mean" : 9137712.0,
    "routingLM8_edge.air_distance_mean" : 316376.94,
    "routingLM8_edge.alternative_rate" : 0.0,
    "routingLM8_edge.distance_max" : 914021,
    "routingLM8_edge.distance_mean" : 416622.34,
    "routingLM8_edge.distance_min" : 53599,
    "routingLM8_edge.failed_count" : 0,
    "routingLM8_edge.guessed_algorithm" : "astarbi",
    "routingLM8_edge.max" : 3344.82336,
    "routingLM8_edge.mean" : 244.9189362,
    "routingLM8_edge.min" : 3.830768,
    "routingLM8_edge.sum" : 61229.73405,
    "routingLM8_edge.visited_nodes_max" : 2061052.0,
    "routingLM8_edge.visited_nodes_mean" : 203949.6,

DistancePlaneProjection (patched)

    "routingLM12.air_distance_mean" : 316376.94,
    "routingLM12.alternative_rate" : 0.0,
    "routingLM12.distance_max" : 914021,
    "routingLM12.distance_mean" : 416693.53,
    "routingLM12.distance_min" : 53599,
    "routingLM12.failed_count" : 0,
    "routingLM12.guessed_algorithm" : "astarbi",
    "routingLM12.max" : 967.724863,
    "routingLM12.mean" : 83.564688148,
    "routingLM12.min" : 3.090671,
    "routingLM12.sum" : 20891.172037,
    "routingLM12.visited_nodes_max" : 1020286.0,
    "routingLM12.visited_nodes_mean" : 101094.766,
    "routingLM12_alt.air_distance_mean" : 324986.8,
    "routingLM12_alt.alternative_rate" : 2.0,
    "routingLM12_alt.distance_max" : 826770,
    "routingLM12_alt.distance_mean" : 865228.6,
    "routingLM12_alt.distance_min" : 244616,
    "routingLM12_alt.failed_count" : 0,
    "routingLM12_alt.guessed_algorithm" : "astarbi",
    "routingLM12_alt.max" : 24106.615505,
    "routingLM12_alt.mean" : 5681.6960086,
    "routingLM12_alt.min" : 1731.275614,
    "routingLM12_alt.sum" : 56816.960086,
    "routingLM12_alt.visited_nodes_max" : 1.6016494E7,
    "routingLM12_alt.visited_nodes_mean" : 4188019.2,
    "routingLM12_alt_edge.air_distance_mean" : 324986.8,
    "routingLM12_alt_edge.alternative_rate" : 2.0,
    "routingLM12_alt_edge.distance_max" : 826770,
    "routingLM12_alt_edge.distance_mean" : 865138.2,
    "routingLM12_alt_edge.distance_min" : 244616,
    "routingLM12_alt_edge.failed_count" : 0,
    "routingLM12_alt_edge.guessed_algorithm" : "astarbi",
    "routingLM12_alt_edge.max" : 85482.298255,
    "routingLM12_alt_edge.mean" : 19841.9368178,
    "routingLM12_alt_edge.min" : 6324.057051,
    "routingLM12_alt_edge.sum" : 198419.368178,
    "routingLM12_alt_edge.visited_nodes_max" : 3.5573572E7,
    "routingLM12_alt_edge.visited_nodes_mean" : 9198762.0,
    "routingLM12_edge.air_distance_mean" : 316376.94,
    "routingLM12_edge.alternative_rate" : 0.0,
    "routingLM12_edge.distance_max" : 914021,
    "routingLM12_edge.distance_mean" : 416622.34,
    "routingLM12_edge.distance_min" : 53599,
    "routingLM12_edge.failed_count" : 0,
    "routingLM12_edge.guessed_algorithm" : "astarbi",
    "routingLM12_edge.max" : 3331.373649,
    "routingLM12_edge.mean" : 238.784344272,
    "routingLM12_edge.min" : 3.704084,
    "routingLM12_edge.sum" : 59696.086068,
    "routingLM12_edge.visited_nodes_max" : 2096960.0,
    "routingLM12_edge.visited_nodes_mean" : 203694.25,
    "routingLM4.air_distance_mean" : 316376.94,
    "routingLM4.alternative_rate" : 0.0,
    "routingLM4.distance_max" : 914021,
    "routingLM4.distance_mean" : 416693.53,
    "routingLM4.distance_min" : 53599,
    "routingLM4.failed_count" : 0,
    "routingLM4.guessed_algorithm" : "astarbi",
    "routingLM4.max" : 1019.917553,
    "routingLM4.mean" : 86.571496224,
    "routingLM4.min" : 2.828941,
    "routingLM4.sum" : 21642.874056,
    "routingLM4.visited_nodes_max" : 1015184.0,
    "routingLM4.visited_nodes_mean" : 111462.2,
    "routingLM4_alt.air_distance_mean" : 324986.8,
    "routingLM4_alt.alternative_rate" : 2.0,
    "routingLM4_alt.distance_max" : 826770,
    "routingLM4_alt.distance_mean" : 867216.2,
    "routingLM4_alt.distance_min" : 244616,
    "routingLM4_alt.failed_count" : 0,
    "routingLM4_alt.guessed_algorithm" : "astarbi",
    "routingLM4_alt.max" : 21824.624591,
    "routingLM4_alt.mean" : 5101.0869832,
    "routingLM4_alt.min" : 1563.170707,
    "routingLM4_alt.sum" : 51010.869832,
    "routingLM4_alt.visited_nodes_max" : 1.6360262E7,
    "routingLM4_alt.visited_nodes_mean" : 4231683.0,
    "routingLM4_alt_edge.air_distance_mean" : 324986.8,
    "routingLM4_alt_edge.alternative_rate" : 2.0,
    "routingLM4_alt_edge.distance_max" : 826770,
    "routingLM4_alt_edge.distance_mean" : 864737.2,
    "routingLM4_alt_edge.distance_min" : 244616,
    "routingLM4_alt_edge.failed_count" : 0,
    "routingLM4_alt_edge.guessed_algorithm" : "astarbi",
    "routingLM4_alt_edge.max" : 83519.970437,
    "routingLM4_alt_edge.mean" : 19422.404587999998,
    "routingLM4_alt_edge.min" : 6018.883511,
    "routingLM4_alt_edge.sum" : 194224.04588,
    "routingLM4_alt_edge.visited_nodes_max" : 3.6044936E7,
    "routingLM4_alt_edge.visited_nodes_mean" : 9260069.0,
    "routingLM4_edge.air_distance_mean" : 316376.94,
    "routingLM4_edge.alternative_rate" : 0.0,
    "routingLM4_edge.distance_max" : 914021,
    "routingLM4_edge.distance_mean" : 416622.34,
    "routingLM4_edge.distance_min" : 53599,
    "routingLM4_edge.failed_count" : 0,
    "routingLM4_edge.guessed_algorithm" : "astarbi",
    "routingLM4_edge.max" : 3317.852128,
    "routingLM4_edge.mean" : 251.267180932,
    "routingLM4_edge.min" : 3.353839,
    "routingLM4_edge.sum" : 62816.795233,
    "routingLM4_edge.visited_nodes_max" : 2043466.0,
    "routingLM4_edge.visited_nodes_mean" : 225164.39,
    "routingLM8.air_distance_mean" : 316376.94,
    "routingLM8.alternative_rate" : 0.0,
    "routingLM8.distance_max" : 914021,
    "routingLM8.distance_mean" : 416693.53,
    "routingLM8.distance_min" : 53599,
    "routingLM8.failed_count" : 0,
    "routingLM8.guessed_algorithm" : "astarbi",
    "routingLM8.max" : 879.342119,
    "routingLM8.mean" : 78.738613008,
    "routingLM8.min" : 2.807712,
    "routingLM8.sum" : 19684.653252,
    "routingLM8.visited_nodes_max" : 1006692.0,
    "routingLM8.visited_nodes_mean" : 101226.19,
    "routingLM8_alt.air_distance_mean" : 324986.8,
    "routingLM8_alt.alternative_rate" : 2.0,
    "routingLM8_alt.distance_max" : 826770,
    "routingLM8_alt.distance_mean" : 865228.6,
    "routingLM8_alt.distance_min" : 244616,
    "routingLM8_alt.failed_count" : 0,
    "routingLM8_alt.guessed_algorithm" : "astarbi",
    "routingLM8_alt.max" : 23143.498499,
    "routingLM8_alt.mean" : 5306.832682,
    "routingLM8_alt.min" : 1642.126488,
    "routingLM8_alt.sum" : 53068.32682,
    "routingLM8_alt.visited_nodes_max" : 1.5903182E7,
    "routingLM8_alt.visited_nodes_mean" : 4157923.5,
    "routingLM8_alt_edge.air_distance_mean" : 324986.8,
    "routingLM8_alt_edge.alternative_rate" : 2.0,
    "routingLM8_alt_edge.distance_max" : 826770,
    "routingLM8_alt_edge.distance_mean" : 865138.2,
    "routingLM8_alt_edge.distance_min" : 244616,
    "routingLM8_alt_edge.failed_count" : 0,
    "routingLM8_alt_edge.guessed_algorithm" : "astarbi",
    "routingLM8_alt_edge.max" : 82545.75053,
    "routingLM8_alt_edge.mean" : 19336.441592199997,
    "routingLM8_alt_edge.min" : 5803.57939,
    "routingLM8_alt_edge.sum" : 193364.415922,
    "routingLM8_alt_edge.visited_nodes_max" : 3.5326704E7,
    "routingLM8_alt_edge.visited_nodes_mean" : 9137702.0,
    "routingLM8_edge.air_distance_mean" : 316376.94,
    "routingLM8_edge.alternative_rate" : 0.0,
    "routingLM8_edge.distance_max" : 914021,
    "routingLM8_edge.distance_mean" : 416622.34,
    "routingLM8_edge.distance_min" : 53599,
    "routingLM8_edge.failed_count" : 0,
    "routingLM8_edge.guessed_algorithm" : "astarbi",
    "routingLM8_edge.max" : 3696.95915,
    "routingLM8_edge.mean" : 238.790923752,
    "routingLM8_edge.min" : 3.688309,
    "routingLM8_edge.sum" : 59697.730938,
    "routingLM8_edge.visited_nodes_max" : 2061052.0,
    "routingLM8_edge.visited_nodes_mean" : 203949.5,

@otbutz
Copy link
Contributor Author

otbutz commented Apr 18, 2024

That's roughly a speedup of 11% if I'm interpreting the results correctly.

@otbutz otbutz linked a pull request Apr 22, 2024 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Approximate with DistancePlaneProjection otbutz/graphhopper
2 participants
@easbar @otbutz