Database Generation
These OSM extract for Great Britain in September 2011 (from Geofabrik) was used for these tests. 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 Memory
The 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) |
|---|---|---|---|
| 2.0 | n/a | n/a | n/a |
| 2.0.1 | 922.80 | 966.31 | 523 |
| 2.0.2 | 921.98 | 961.61 | 523 |
| 2.0.3 | 926.46 | 969.29 | 524 |
| 2.1 | 932.45 | 972.54 | 531 |
| 2.1.1 | 807.68 | 847.27 | 531 |
| 2.1.2 | 806.41 | 844.81 | 531 |
| 2.2 | 805.68 | 860.43 | 582 |
| 2.3 | 787.56 | 846.00 | 582 |
| 2.3.1 | 793.39 | 848.14 | 582 |
| 2.3.2 | 795.84 | 848.75 | 582 |
| 2.4 | 671.76 | 724.12 | 537 |
| 2.4.1 | 669.40 | 721.26 | 537 |
| 2.5 | 643.80 | 702.35 | 537 |
| 2.5.1 | 698.84 | 762.36 | 543 |
| 2.6 | 199.88 | 259.79 | 537 |
| 2.7 | 202.29 | 268.05 | 537 |
| 2.7.1 | 201.72 | 258.88 | 537 |
| 2.7.2 | 205.58 | 263.80 | 537 |
| 2.7.3 | 213.29 | 259.01 | 536 |
| 3.0 | 213.42 | 314.62 | 537 |
| 3.1 / 3.1.1 | 219.41 | 273.80 | 583 |
The first obvious thing to notice is that version 2.0 has no results. This is because this version could not process the complete input file without crashing. The interesting thing is that at the time of the release of this version it could process the current Great Britain OSM file.
Version 2.1.1 reduced 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 was the primary reason for the speed increase and the other optimisations were quite small in comparison.
Version 2.2 added 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 was increased slightly though due to the extra tables needed to perform the pruning.
Version 2.3 contained 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.
Version 2.4 contained 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 had a faster XML parser, but there are more tagging rules which cancels out this improvement.
Version 2.5.1 was slightly slower than version 2.5 which may be caused by a slight change in the order of the steps.
Version 2.6 had a large number of speed improvements; for database generation this was 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 had very few changes that impact the performance.
Version 2.7.3 had a significant change to reduce the memory use and elapsed time although the CPU time is not significantly affected. The reduced elapsed time is most significantly visible in the Low Memory Benchmarks.
Version 3.0 has no significant changes to the planetsplitter so the time taken is the same.
Version 3.1 (same as 3.1.1) uses 64-bit IDs for the nodes when reading the OSM data so there is an increase in memory usage and a slight increase in time taken.
Database Size and Contents
There is less variation in the size of the database between the different versions than there was for time and memory usage.
| Version | Nodes (k) | Super- Nodes (k) | Segments (k) | Super- Segments (k) | Ways (k) | Relations (k) |
|---|---|---|---|---|---|---|
| 2.0 | n/a | n/a | n/a | n/a | n/a | n/a |
| 2.0.1 | 12058.1 | 1701.9 | 14355.2 | 2482.2 | 484.1 | 2.2 |
| 2.0.2 | 12060.6 | 1701.9 | 14357.7 | 2482.1 | 484.9 | 2.2 |
| 2.0.3 | 12060.6 | 1701.9 | 14357.7 | 2482.1 | 484.9 | 2.2 |
| 2.1 | 12062.4 | 1707.8 | 14361.4 | 2488.4 | 485.0 | 2.1 |
| 2.1.1 | 12062.4 | 1708.1 | 14361.6 | 2488.8 | 485.0 | 2.1 |
| 2.1.2 | 12062.5 | 1708.2 | 14361.7 | 2488.8 | 485.0 | 2.1 |
| 2.2 | 7512.4 | 1698.4 | 9446.0 | 2478.7 | 487.1 | 2.1 |
| 2.3 | 7512.4 | 1698.5 | 9446.1 | 2478.9 | 487.0 | 2.1 |
| 2.3.1 | 7512.4 | 1698.5 | 9446.1 | 2478.9 | 487.0 | 2.1 |
| 2.3.2 | 7512.4 | 1697.3 | 9445.9 | 2477.5 | 487.0 | 2.1 |
| 2.4 | 7510.8 | 1687.5 | 9441.6 | 2467.7 | 497.5 | 2.1 |
| 2.4.1 | 7510.8 | 1687.5 | 9441.6 | 2467.7 | 497.5 | 2.1 |
| 2.5 | 7510.9 | 1687.7 | 9441.7 | 2468.0 | 496.9 | 2.1 |
| 2.5.1 | 7443.8 | 1696.5 | 9376.4 | 2476.9 | 497.3 | 2.1 |
| 2.6 | 7429.8 | 1696.0 | 9357.2 | 2476.4 | 497.9 | 2.1 |
| 2.7 | 7429.8 | 1696.1 | 9357.3 | 2476.5 | 498.2 | 2.1 |
| 2.7.1 | 7429.8 | 1696.1 | 9357.3 | 2476.5 | 498.2 | 2.1 |
| 2.7.2 | 7429.8 | 1696.1 | 9357.3 | 2476.5 | 498.2 | 2.1 |
| 2.7.3 | 7430.5 | 1696.1 | 9358.3 | 2476.5 | 498.2 | 2.1 |
| 3.0 | 7428.4 | 1693.4 | 9356.2 | 2473.9 | 498.0 | 2.1 |
| 3.1 / 3.1.1 | 7428.4 | 1693.4 | 9356.2 | 2473.9 | 498.0 | 2.1 |
| Version | Nodes (MB) | Segments (MB) | Ways (MB) | Relations (MB) |
|---|---|---|---|---|
| 2.0 | n/a | n/a | n/a | n/a |
| 2.0.1 | 138.143 | 273.804 | 12.354 | 0.033 |
| 2.0.2 | 138.211 | 273.852 | 12.370 | 0.033 |
| 2.0.3 | 138.211 | 273.852 | 12.370 | 0.033 |
| 2.1 | 138.232 | 273.922 | 12.370 | 0.032 |
| 2.1.1 | 138.232 | 273.926 | 12.370 | 0.032 |
| 2.1.2 | 138.233 | 273.929 | 12.370 | 0.032 |
| 2.2 | 86.161 | 180.168 | 12.402 | 0.033 |
| 2.3 | 86.161 | 180.170 | 12.402 | 0.033 |
| 2.3.1 | 86.161 | 180.170 | 12.402 | 0.033 |
| 2.3.2 | 86.162 | 180.166 | 12.402 | 0.033 |
| 2.4 | 86.143 | 180.083 | 12.561 | 0.033 |
| 2.4.1 | 86.143 | 180.083 | 12.561 | 0.033 |
| 2.5 | 86.144 | 180.086 | 12.552 | 0.033 |
| 2.5.1 | 85.376 | 178.840 | 12.559 | 0.033 |
| 2.6 | 85.216 | 178.475 | 12.568 | 0.033 |
| 2.7 | 85.216 | 178.476 | 12.572 | 0.033 |
| 2.7.1 | 85.216 | 178.476 | 12.572 | 0.033 |
| 2.7.2 | 85.216 | 178.476 | 12.572 | 0.033 |
| 2.7.3 | 85.224 | 178.495 | 12.572 | 0.033 |
| 3.0 | 85.200 | 178.455 | 12.570 | 0.033 |
| 3.1 / 3.1.1 | 85.200 | 178.455 | 12.570 | 0.033 |
Version 2.1 added 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 pruned unneeded nodes and segments by default which leads to approximately a one-third reduction in the size of the database.
Version 2.3 made 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 changed some tagging rules and removed pruned ways although extra ways are also created by pruning for different transport types.
Version 2.5 had more tagging rules which means that more highways are included in the database.
Versions 2.6, 2.7, 2.7.1, 2.7.2, 2.7.3, 3.0 and 3.1 (same as 3.1.1) change a few tagging rules but there is only a small change in database size.
Version 3.1 (same as 3.1.1) uses 64-bit IDs for the nodes when reading the OSM data but keeps 32-bt nodes in the database so there is no change in the size.
Routing
The routing is performed using 200 pairs of nodes; the statistics presented in the table and graphs are the average for all of the routes that could be found.Time and Memory
There 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) | Number Routed |
|---|---|---|---|---|
| 2.0 | n/a | n/a | n/a | n/a |
| 2.0.1 | 11.45 | 11.47 | 250 | 179 |
| 2.0.2 | 11.13 | 11.14 | 249 | 179 |
| 2.0.3 | 11.14 | 11.15 | 249 | 179 |
| 2.1 | 11.21 | 11.23 | 250 | 178 |
| 2.1.1 | 1.93 | 1.93 | 267 | 178 |
| 2.1.2 | 0.74 | 0.75 | 103 | 178 |
| 2.2 | 0.69 | 0.70 | 78 | 180 |
| 2.3 | 0.68 | 0.68 | 78 | 180 |
| 2.3.1 | 0.68 | 0.68 | 78 | 180 |
| 2.3.2 | 0.68 | 0.69 | 78 | 180 |
| 2.4 | 0.68 | 0.69 | 78 | 182 |
| 2.4.1 | 0.74 | 0.75 | 83 | 187 |
| 2.5 | 0.74 | 0.74 | 83 | 187 |
| 2.5.1 | 0.74 | 0.75 | 83 | 187 |
| 2.6 | 0.59 | 0.60 | 82 | 187 |
| 2.7 | 0.59 | 0.60 | 82 | 187 |
| 2.7.1 | 0.59 | 0.60 | 82 | 187 |
| 2.7.2 | 0.60 | 0.60 | 82 | 187 |
| 2.7.3 | 0.59 | 0.60 | 82 | 187 |
| 3.0 | 0.57 | 0.57 | 87 | 187 |
| 3.1 / 3.1.1 | 0.58 | 0.59 | 90 | 187 |
Version 2.0 suffered from a poor choice of hash function used to look up the intermediate nodes in the route. The lookup function was taking a large fraction of the total routing time when it should only be a small part.
Version 2.1.1 corrected the problem described above for the hash function but also added some other improvements which increased the speed by a further 10% at the expense of a small amount of extra memory.
Version 2.1.2 changed the method used to decide when to stop searching for better routes, this greatly reduced the number of nodes that need to be checked. This fixes a previous error and reduces the time and memory by a factor of 2.5.
Version 2.2 used a smaller database for routing with many unneeded nodes and segments having been removed. This lead to a reasonable reduction in memory required but only a very small reduction in time.
Version 2.3 did 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 did not change the routing algorithm but the database is slightly different due to the changed tagging rules.
Version 2.4.1 did not change the routing algorithm but fixed a bug that existed since version 1.1 that caused the search to terminate early if the route has low preference scores. This allowed a few extra difficult routes to be calculated which increased the average memory and time required even though the routes calculated previously take the same amount as before.
No changes to the routing algorithm were included in versions 2.5 or 2.5.1.
Version 2.6 was faster because of improvements in the data structures used for storing the results.
Versions 2.7, 2.7.1, 2.7.2 and 2.7.3 had almost no changes that affect the routing performance.
Version 3.0 has a very small reduction in time, possibly due to the parsing of the profiles files.
Version 3.1 (same as 3.1.1) performs the routing from the two ends towards the middle, this requires slightly more memory and is fractionally slower for finding a route. When there is no possible route it is often much quicker to discover this by routing from both ends.
Conclusions
Versions 2.0 through to 2.1 are very much slower at routing than earlier versions because of an inefficient hash function that causes a massive slow-down in looking up intermediate nodes.Version 2.1.1 corrected 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 made 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 database generation but no change in time taken.
Version 2.3 was virtually identical to version 2.2 in performance but with a small reduction in database generation time.
Version 2.4 provided a 10% decrease in database generation time but no significant change to the database size or routing time.
Version 2.5 had more complex tagging rules but there was no change in the overall time taken.
Version 2.6 was 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.
Version 2.7.3 reduced the database generation memory and elapsed time but this reduction in time is significantly dependent on the amount of available memory.
Version 3.0 has no significant effect on the database generation or routing time.
Version 3.1 (same as 3.1.1) uses slightly more memory for database generation due to the 64-bit nodes and slightly more memory for routing due to routing from both ends towards the middle.