RationaleOne of the criticisms of Routino version 2.0 was that it was very much slower than earlier versions. This version introduced turn relations which means that the direction of travel is as important as the location when calculating the route. Even so an increase of a factor of five in the time to calculate a route was unexpected. Starting with version 2.1 the time to generate the routing database and to calculate routes has been measured and used to check and improve the performance.
One thing that this benchmarking does not do is compare the speed of Routino to other routers using OSM data. Since it only makes sense to compare programs that do the same thing and all of the routers have different features any such simple comparison would be meaningless.
Benchmarking OverviewThe general idea for the benchmarking is to take all released versions of Routino and run the same tests on them. These tests measure the time and amount of memory that it takes for each of them to generate the routing database and calculate a given set of routes. The size of the database and the number of entries are also recorded. These results are collated and compared to examine the differences.
Database GenerationThe first step in calculating a route is to generate the routing database. For these tests an OSM extract for Great Britain in September 2011 (from Geofabrik) was used. This file is 6.1GB when uncompressed and contains 92.9 million lines, 30 million nodes, 3.7 million highways and 77,000 relations (statistics come from planetsplitter output).
The amount of time that it takes to run the planetsplitter program using default options is measured (both CPU time and elapsed time). The size of the generated database is measured and the number of entries are counted.
RoutingThe routing test data set was generated by selecting pairs of random nodes from the generated database (using version 2.1) and using these as the start and finish points of routes. A total of 200 pairs of nodes were used and when the test was run not all combinations were routable (typically 90% routed with version 2.x).
The average time to calculate this set of routes is calculated only for the routes that were succesfully found. This avoids a bias caused by the extra time taken to attempt to find a route that is impossible.