One of the great benefits of open data is that anyone can download it and write software to do really cool things with it. One example of that is route-finding and there are several good bits of software which you can use, ranging from those on the embedded or mobile environment to the server environment.
I tested two of the leading server implementations; OSRM and GraphHopper to see what the differences between them are.
OSRM, written and maintained by Dennis Luxen, was the original implementation of contraction hierarchies, an advanced technique for preprocessing the routing network to make route finding extremely fast. OSRM has a comprehensive demo website and fearsome reputation for eating RAM, although there are changes coming which will apparently drastically reduce the memory usage.
A newer project, GraphHopper, also uses contraction hierarchies and claims to scale from mobile to server applications - although I'm only testing it on a server installation. It comes with an Android implementation, so should be interesting to anyone wanting to add routing abilities to their OSM-based apps. GraphHopper also has a demo website.
- OSRM requires a 112GB of memory to process the whole planet for car routing. If you want to do this, you should probably be looking for a server with at least 192GB installed.
- GraphHopper appears to be faster than OSRM, and take less memory, perhaps because it doesn't yet support turn restrictions.
- The reason why OSRM has requires >3x more RAM to pre-process than GraphHopper is apparently due to its support for turn costs, including turn restrictions.
- The extra edges produced by the expansion for turn costs is probably the reason that the median response in this benchmark is 2.5x slower from OSRM than GraphHopper.
I'm mainly interested in how these two bits of software scale up to routing on the whole world, so the benchmark is to:
- Take the whole planet file (I used the PBF from 2014-01-31).
- Use the default car / fastest routing profile.
- Time how long the planet file takes to import, including any time to pre-process the data, and how much memory was used.
- Run the same set of route requests against both bits of software and time the responses and how much memory was used.
To produce a set of route requests which would be somewhat realistic,
I took the set of
place=city nodes for the whole planet and made a
route from each to its nearest three neighbours. In total, this
produced a set of 21,102 routes with:
- A median length of 69km.
- 5% of routes less than 7km.
- 95% of routes less than 346km.
- 99% of routes less than 802km.
I don't know if this is representative of real world usage of a routing engine, and I strongly suspect that real world usage will vary considerably depending on what it's being used for. For example, a pizza delivery company, or chain, is likely to produce much shorter routes while a haulage company would likely produce generally longer ones.
Despite the wide variance of "real world" usage, the test case is the same for both applications and should produce meaningful results - although it's worth stating the caveat here: if your usage scenario is different from the one above, then you should conduct your own benchmarking before making a decision.
It should be noted up-front that the version of GraphHopper I tested does not support turn restrictions yet. If this is an important for your usage scenario then you should wait to test the version of GraphHopper which implements it, or use OSRM.
At the time, this seemed entirely reasonable, given that a year ago it took 55GB of RAM to run the whole OSRM tool-chain according to the OSRM wiki.
The server was running Ubuntu 13.10, updated to the latest packages for everything.
Setting up GraphHopper was a little harder, partly because I'm not as
mvn's quirks and incomprehensible error messages as I
make's quirks and incomprehensible error messages.
The main issue was that following the instructions meant running
an "all-in-one" script, which always makes me a little bit
wary. However, I didn't get it quite right installing the WAR file,
and spent a long while trying to figure that out before realising that
it makes a difference whether you run
mvn war:war in the top level
source directory as opposed to in the
web/ subdirectory. Oh well,
that's one quirk that
Before diving into the results; the usual caveats about this applying to the machine and environment on which I ran it. It may, or may not, apply to your use case, machine or environment.
Setup / import
Neither of these setup / import times include the time taken to download the planet file. Times given are wall-clock times and memory consumption is the peak level.
GraphHopper ran in 253 minutes and consumed 33.5GB of RAM. This was using the default "car/fastest" routing profile, and no extra tuning was done.
I was expecting OSRM to need a lot of RAM... The first stage, "prepare", ran in 160 minutes and consumed 16.2GB of RAM. This wasn't so bad, but OSRM has a two-step import, with the latter requring 112GB of RAM. It ran in 783 minutes, but it would be unfair to use that for comparison since about half of that peak requirement wasn't resident in main memory, the process was swapping and largely idle waiting on disk.
Neither OSRM not GraphHopper seemed to have any trouble running in 64GB memory, and both performed very well.
All of the requests were run with the same options; to return the geometry of the route, but not the turn-by-turn directions. It is possible that different combinations of options would have produced very different results.
For consistency, I checked that both OSRM and GraphHopper are finding the same routes, or at least, are generally finding similar routes. The number of routes between the two input points which were found or not found shows that, broadly, they are finding similar paths.
|OSRM found||GH found||Number of inputs|
The vast majority of paths were found, and found by both OSRM and GraphHopper, and it's only those 18,918 paths which will be used for looking at the response times:
|Data %ile||OSRM distance (m)||OSRM response time (ms)||GH distance (m)||GH response time (ms)|
The first thing I noticed is that, even without turn restriction support, the distance numbers are quite comparable. However, it is likely that support for turn restrictions would have a much greater impact on short, urban journeys than on the medium-to-long distance ones in this test.
GraphHopper returns its results 2.5x quicker in the median case than OSRM, but this is probably due to the smaller graph that GraphHopper is working with. The gap widens for shorter routes and closes for longer ones, possibly implying that GraphHopper is benefitting from better locality of access for short routes.
Update: There's a better, more detailed analysis of the response times in a later blog post.
Quite why OSRM needed >3x the amount of memory that GraphHopper did wasn't clear to me, so I looked at the logs created by each process:
- GraphHopper imported a graph containing 93.9 million nodes and 125 million edges, and pre-processing expanded that to 221 million edges.
- OSRM imported a graph with 461 million nodes, 487 million edges and 230 thousand restrictions. It expanded those to 936 million nodes and 2.7 billion edges.
I asked OSRM's maintainer, Dennis Luxen, about the difference here and he explained that comparing the edge count between these two bits of software is like comparing apples to oranges. OSRM counts bidirectional edges as two edges, whereas it appears than GraphHopper does not. Even taking that into account, OSRM appears to begin with more edges than GraphHopper.
OSRM's support for turn restrictions pushes this even higher. As Dennis explained in a recent blog post, the routing graph is transformed into its dual in order to account for turn costs at every junction, even those which don't have variable turn costs or restrictions:
Obviously, we are adding much more detail into graph, which does increase the memory requirements of a factor of 3-4.
It seems that because of the increase in graph size, and the resultant increase in memory consumption, the median case is taking about 2.5x longer to compute with OSRM than GraphHopper.
Of course, this may not be the case: I have not conducted profiling to prove that the route finding, rather than the geometry extraction or JSON serialisation, was the major component of the response calculation.
The conclusion appears to be: Turn restrictions are an expensive feature to implement, and if your application does not need them, then you should turn them off for lower resource requirements when pre-processing and probably better performance. However, there are interesting things coming soon; GraphHopper may soon get turn restriction support, and OSRM is getting some "careful optimization" which may bring memory consumption down to "roughly 32GB".
It will be interesting to run the benchmark again once those two features have arrived.