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