RationaleOne of the criticisms of Routino version 2.0 was that it was very much slower than earlier versions (a point raised by a user of Routino in an e-mail). I thought that the reason for this was the introduction of turn relations which means that the direction of travel is as important as the location when calculating the route. Even so I was surprised to be told that calculating a route took five times as long as before. After the release of version 2.1 it seemed like a good time to start making some proper measurements of the time taken for generating the database and calculating routes. With version 2.1.1 the cause of the slowdown has been identified and minimised. Moving forward from version 2.2 the benchmarks will be updated with each release to ensure that regressions like those in version 2.0 do not appear again.
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.
General MethodThe general idea for the benchmarking was to take all released versions of Routino and run the same tests on them. These tests would measure the amount of time and memory that it takes for each of them to generate the routing database and calculate some routes. The size of the database and the number of entries would also be recorded. The results are then collated and compared to try and find out the differences.
All tests were 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.
The results for time and memory were found by using /usr/bin/time -f "%S %U %e %M" which prints out the system (kernel) CPU time, user CPU time, elapsed time and maximum resident set size (memory usage). The sum of the two CPU times has been used for the results reported below.
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).
Time and MemoryThe results for time and memory are presented below as a table and a pair of graphs with explanations for the major features.
|Version||CPU Time (s)||Elapsed Time (s)||Max Resident|
Set Size (MB)
- Versions 1.0 and 1.1 contain a bug that was fixed in version 1.2 that caused a memory leak during OSM parsing. The bug fix from version 1.2 was applied to these versions because without it they ran out of memory.
- Versions 1.5 and 2.0 failed to run without crashing - since bug-fix releases are available (1.5.1 and 2.0.1) there was no point in patching the source code to allow them to run.
The first obvious thing to notice is that version 1.5 and version 2.0 have no results. This is because neither of these two versions could process the complete input file without crashing. Both of these versions were followed up by bug-fix versions which did work correctly. The interesting thing is that at the time of the release of these two versions they could process the Great Britain OSM file because that is the one used as the example on the Routino website.
Version 1.2 introduced new sorting functions that operate with limited memory overhead rather than using the operating system supplied qsort function which seemed to use an extra copy of the data. This explains the large reduction in memory used between version 1.1 and version 1.2. There were some other memory leaks fixed in version 1.2 but these were probably small by comparison. The reduction in memory usage in this version is offset by the increase in time which is mostly system time and related to the use of temporary files for sorting.
Version 1.4 added the use of tagging rules from an XML configuration file which made very little difference to the memory usage although the time increased but then decreased again in version 1.4.1.
Version 1.5 added processing for node properties and route relations and this seems to have increased the memory usage although the time taken is the same.
Version 2.0 changed the internal data structure so that each segment is only stored once and the rule for finding super-nodes. This would be expected to halve the amount of memory required for segments (which probably explains the reduction in memory to about 2/3 of that in version 1.5.1).
Version 2.1.1 reduces the default number of iterations from 10 down to 5 because tests showed that there was no significant change in the routing time by doing this. This is the primary reason for the speed increase and the other optimisations were quite small in comparison.
Version 2.2 adds the new feature of pruning unneeded nodes and segments which takes time but produces a smaller database. The time taken to identify and remove the unneeded points is compensated by the reduction in time to process the smaller remaining data set. The memory usage is increased slightly though due to the extra tables needed to perform the pruning.
Version 2.3 contains only small improvements to the database generation for the XML parsing and the option of multi-threaded data sorting which is not used for these benchmarks and gives only a small improvement. Before considering the multi-threaded sorting the amount of RAM allocated to the sort functions should be increased.
Version 2.4 contains some large changes to the database generation with fewer sorting operations and less disk I/O due to rearranging or combining the processing steps.
Version 2.5 has a faster XML parser, but there are more tagging rules which cancels out this improvement.
Version 2.5.1 is slightly slower than version 2.5 which may be caused by a slight change in the order of the steps.
Version 2.6 has had a large number of speed improvements; for database generation this is primarily because of using file buffering so that reads and writes are performed on large blocks (4 kB) rather than a few bytes.
Versions 2.7, 2.7.1 and 2.7.2 have very few changes that impact the performance.
Database Size and ContentsThere is less variation in the size of the database between the different versions than there was for time and memory usage.
|Ways (k)||Relations (k)|
|Version||Nodes (MB)||Segments (MB)||Ways (MB)||Relations (MB)|
Version 1.2 combines together ways with identical properties which accounts for the large reduction in the number of them and the size of the file containing them.
Version 1.3 added a lot more highway properties which will reduce the number of identical ways and leads to the 25% increase in the size of the file although the number of ways remains about the same.
Version 1.4 uses the tagging rules in the configuration file and the additional rules compared to the built-in ones earlier explain the small increase in nodes, segments and ways.
Version 1.4.1 changed the algorithm used to find super-nodes (fewer of them) which will change the number of super-segments (more of them). This explains the increase in the number of segments although the number of nodes and ways remains the same.
Version 1.5 added node properties which explains the increase in the file size even though the number of nodes stays the same.
Version 2.0 changed the method of finding super-nodes back to what it was in version 1.4 which explains the change in the number of super-nodes and super-segments and the reduction in the number of segments.
Version 2.1 adds more tagging rules which explains the increase in the number of nodes, segments and ways since more highways are now considered valid.
Version 2.2 prunes unneeded nodes and segments by default which leads to approximately a one-third reduction in the size of the database.
Version 2.3 makes no significant changes to the database format and therefore size except version 2.3.2 which changes the way that some barriers are stored (not as super-nodes).
Version 2.4 changes some tagging rules and removes pruned ways although extra ways are also created by pruning for different transport types.
Version 2.5 has more tagging rules which means that more highways are included in the database.
Versions 2.6, 2.7, 2.7.1 and 2.7.2 change a few tagging rules but there is only a small change in database size.
RoutingThe routing was performed 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 statistics presented in the table and graphs are the average for all of the routes that could be found. The routes that cannot be found typically take much longer and introduce a bias.
Time and MemoryThere are some significant differences in the time taken and memory used for routing between the different versions.
|Version||CPU Time (s)||Elapsed Time (s)||Max Resident|
Set Size (MB)
There is a gradual increase in routing time between version 1.0 and 1.5.1 as new features are added (like highway properties and node restrictions) that mean that extra factors need to be taken account at each stage.
Version 2.0 added turn relations and because of this the direction of travel is as important as the location when calculating the route. At each intermediate node in the route there will likely be more than one possible route heading in different directions towards the final destination. The large increase in routing time is due to the fact that the hash function used to look up the intermediate nodes had not been modified to expect this. The lookup function was therefore taking a large fraction of the total routing time when it should only be a small part. This change was made in version 1.4.1 and caused no problems until version 2.0 when the routing changed.
Version 2.1.1 corrects the problem described above for the hash function but also adds some other improvements which increased the speed by a further 10%.
Version 2.1.2 changes the method used to decide when to stop searching for better routes, this greatly reduces the number of nodes that need to be checked. The method used now is the method that was always intended but wasn't implemented correctly before. This change reduces the time and memory by a factor of 2.5.
Version 2.2 uses a smaller database for routing with many unneeded nodes and segments having been removed. This leads to a reasonable reduction in memory required but only a very small reduction in time.
Version 2.3 does not have any changes to the routing algorithm so the observed changes in the time taken are just an indication of the measurement error.
Version 2.4 does not change the routing algorithm but the database is slightly different due to the changed tagging rules.
Version 2.4.1 does not change the routing algorithm but fixes a bug that has existed since version 1.1 that caused the search to terminate early if the route has low preference scores. This allows a few extra difficult routes to be calculated which increases the average memory and time required even though the routes calculated previously take the same amount as before.
No changes to the routing algorithm have been included in version 2.5.
Version 2.5.1 fixes some routing bugs, but these do not affect the results.
Version 2.6 is faster because of improvements in the data structures used for storing the results.
Versions 2.7 and 2.7.1 have almost no changes that affect the router performance.
ConclusionsVersions 1.0 and 1.1 of Routino are quite different from the later versions in their requirements for memory and execution time. They can be considered as quite primitive compared to the later versions.
Versions 2.0 through to 2.1 are very much slower at routing because of an inefficient hash function that causes a massive slow-down in looking up intermediate nodes.
Version 2.1.1 corrects the problems of versions 2.0 to 2.1 as well as some further small speed improvements. Version 2.1.2 makes significant changes to the routing speed and memory usage by better detection of when the optimum route has been found.
Version 2.2 makes a large reduction in the database size but only a modest reduction in routing memory. The price to pay for the reduced database is a slight increase in the amount of memory for the planetsplitter but no change in time taken.
Version 2.3 is virtually identical to version 2.2 in performance but with a small reduction in database generation time.
Version 2.4 provides a 10% decrease in database generation time but no significant change to the database size or the routing time.
Version 2.5 has more complex tagging rules but there is no change in the overall time taken.
Version 2.6 is considerably faster for database generation and slightly faster for routing. Changes are primarily due to low level changes to the data handling rather than improvements in the algorithms.
Versions 2.7, 2.7.1 and 2.7.2 are almost unchanged from version 2.6.