Performance

TODO this is outdated information from 2012

All queries are performed on unterfranken with a 32bit ubuntu and 1.6.0_33. similar results for jdk1.7.0_05. The path length is ~150km on average.

The average query time is printed for some selected algorithms and is in ms. See RoutingAlgorithmIntegrationTests.runShortestPathPerf for more information. edges:872k, nodes:815k

Storage	-Xmx	Dijkstra	A*	bi-Dijkstra	bi-Dijkstra[1]	bi-Dijkstra[3]	bi-A*[4]	bi-A*[1][4]
GraphStorage[2]	300m	300	120	200	67	3	85	27
Neo4J	1500m	~1600	730	1190	-	-	-	-

[1] a bidirectional algorithm on an optimized graph where every 2-degree node is avoided
[2] RAMDirectory is used
[3] contraction hierarchy
[4] paths from bidirectional A* are not always optimal. See code.

Tests are run with an old Intel Core 2 Duo CPU P8600 @ 2.40GHz. E.g. as a reference the encryption tool "john --test" gives me for "Traditional DES":

Many salts:	1044K c/s real, 1050K c/s virtual
Only one salt:	960486 c/s real, 960486 c/s virtual