LightOSM.jl Benchmarks¶
This is a benchmark analysis of LightOSM.jl, a Julia package for downloading, ingesting and analyising geospatial data from OpenStreetMap APIs. BenchmarkTools.jl is used to compare LightOSM's runtime performance for shortest path algorithms (Dijkstra and A*) against two other Julia packages, LightGraphs.jl and OpenStreetMapX.
Methodology¶
This experiment generates a series of random origin-destination nodes for each package to calculate the shortest path between them. The following parameters were used:
- Directed graph with 29718 nodes and 43550 edges
- Experiment sets of 1, 100, 1000 and 10000 random paths
Notes¶
- LightOSM shortest path algorithms account for turn restrictions in the OpenStreetMap transport network.
- Precomputing Dijkstra shortest path parent states with LightOSM can significantly improve path calculation (rather, path retrieval) as long as the graph has a reasonable amount of nodes and the user has sufficient memory to perform such an operation. This option is particularly useful if you need to generate paths in the millions.
- Precomputation took roughly 130s in this experiment.
- To replicate this experiment see the benchmark directory of LightOSM.
- This experiment was run on a 2019 MacBook Pro with a 2.4 GHz Intel Core i5 processor, 16 GB memory, and macOS Mojave 10.14.6.
Results¶
include("benchmark/benchmarks_plot.jl");
Dijkstra¶
OpenStreetMapX (osmx) had the longest runtime for the Dijkstra algorithm with 21.54s for 1000 paths, LightGraphs (lg) took half long with 9.54s, LightOSM (losm) took the least amount of time with 5.3s. Runtime for precomputed LightOSM (losm_precomputed) was almost neglible.
plot_dijkstra_time()
We observe similar results with memory usage.
plot_dijkstra_memory()
A*¶
LightGraphs had the longest runtime for the A* algorithm with 24.89s for 1000 paths, OpenStreetMapX took less than half as much time with 6.56s, LightOSM again took the least amount of time with 2.73s. Runtime for precomputed LightOSM was again almost neglible.
plot_astar_time()
This time we see significantly less memory usage for LightOSM in comparison to the other packages.
plot_astar_memory()
Conclusion¶
LightOSM without precomputation was about 4x faster than OpenStreetMapX and 2x faster than LightGraphs computing Dijkstra shortest paths. Memory usage had similar results.
Meanwhile, LightOSM without precomputation was about 2.5x faster than OpenStreetMapX and 9x faster than LightGraphs computing A* shortest paths. LightOSM used about 10x less memory than OpenStreetMapX and 28x less memory than LightGraphs.
LightOSM runtime retrieval of shortest paths with precomputation was almost neglible.
Appendix¶
dijkstra_results
astar_results