Routino : Benchmarking

Rationale

One 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 Overview

The 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 Generation

The 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.

Routing

The 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.

Benchmark Types

There are four types of benchmarks reported here, these depend on the method of running the Routino software and the amount of memory available.

Standard Benchmarks

The standard benchmarks are run on a computer that has sufficient memory to process the data set without swapping or paging. The tests are run on 32-bit Linux running on a ~3GHz Core i3 processor with 4 GB of RAM. Since the programs are all run single-threaded only one core would be used and since it is a 32-bit system no more than 3 GB of virtual memory is available to the programs.

Slim Mode Benchmarks

The slim mode benchmarks use the same computer as the standard benchmarks but they use the planetsplitter-slim and router-slim programs instead of the planetsplitter and router programs. The difference between the two is that in slim mode no memory mapping is used which leads to a lower memory requirement but more disk accesses.

Low Memory Benchmarks

When running the Routino software on computers with limited amounts of memory the amount of time taken to generate the database can be significantly increased. When swapping and/or paging is required the order in which the disk-backed memory is accessed can have signifcant impact on the elapsed time even though the CPU time is only slightly increased. A series of tests have been run on a virtual machine (running on the computer described above under VirtualBox) with different amounts of memory allocated.

Motor-only Benchmarks

The database that Routino uses can be customised by selecting the types of highway that are to be included and the methods of transport to be considered. This can reduce the size of the database and increase the speed with which routes can be generated. A set of benchmarks have been performed for one version of Routino with different sets of users considered (driving, riding, walking or all).