[graphtooltickets] [graphtool] Page: Performance changed
graphtool
webmaster at skewed.de
Wed Mar 6 12:04:41 UTC 2013
* The user 'tiago peixoto' has changed the page: Performance.
* Diff link: <URL:http://graphtool.skewed.de/wiki/Performance?action=diff&version=11>
Index: Performance
==============================================================================
 Performance (version: 10)
+++ Performance (version: 11)
@@ 9,17 +9,18 @@
The graph used here is the strongly connected component of the PGP web
of trust network. It is a directed graph, with N=39796 vertices and
E=301498 edges.
+E=301498 edges. The network can be downloaded here: attachment:pgp.xml
The functions are called several times, and the average time take per
function call is computed. The results can be seen below. In the
following are shown the results on the same
+For this test we used graphtool version 2.2.23dev, igraph 0.6.4 and
+NetworkX 1.7.
+
+The functions are called several times, and the **average time take per
+function call** is computed and shown below. All results are for the same
[https://en.wikipedia.org/wiki/List_of_Intel_Core_i7_microprocessors#Sandy_Bridge_microarchitecture Intel Core i7 2620M]
CPU with 4 cores. In the second column are shown
the results for graphtool with [https://en.wikipedia.org/wiki/OpenMP OpenMP]
enabled using 4 threads, and the third column shows the results
using only one core.

=Algorithm == graphtool (OpenMP) == graphtool == igraph == NetworkX =
Shortest paths  0.0106 s  0.0098 s  0.00989 s  
@@ 29,19 +30,21 @@
Betweenness  579.7 s   1182.6 s  
The conclusion is that graphtool and igraph deliver overall comparable
+Both graphtool and igraph seem to deliver overall comparable
performance, at least when OpenMP is disabled. In this case, the largest
difference is the example above is !PageRank, where igraph is around
1.6x slower, but igraph comes out around 1.2x faster when computing
Kcore decomposition.
As expected, graphtool becomes faster by a factor of 4 on algorithms
which run in parallel (!PageRank and Betweenness), and thus beats igraph
in these algorithms.
+As expected, graphtool becomes faster by a factor of 4 when OpenMP is
+enabled on algorithms which run in parallel (!PageRank and Betweenness),
+and thus beats igraph in these cases.
NetworkX, on the other hand, comes at a distant third with running times
in the order of **10 to 170 times slower** than graphtool and
igraph. This is mostly due to its pure Python implementation.
+igraph. This is mostly due to its pure Python implementation, which is
+known to be usually much slower than C/C++ (see
+[http://www.scipy.org/PerformancePython here] for further comparisons).
Performance alone is not the only issue which should be considered. All
these libraries have their own advantages and disadvantages, which need

Page URL: <URL:http://graphtool.skewed.de/wiki/Performance>
graphtool <URL:http://graphtool.skewed.de/>
An efficient python module for graph analysis and manipulation.
 next part 
* The user 'tiago peixoto' has changed the page: Performance.
* Diff link: <URL:http://graphtool.skewed.de/wiki/Performance?action=diff&version=11>
Index: Performance
==============================================================================
 Performance (version: 10)
+++ Performance (version: 11)
@@ 9,17 +9,18 @@
The graph used here is the strongly connected component of the PGP web
of trust network. It is a directed graph, with N=39796 vertices and
E=301498 edges.
+E=301498 edges. The network can be downloaded here: attachment:pgp.xml
The functions are called several times, and the average time take per
function call is computed. The results can be seen below. In the
following are shown the results on the same
+For this test we used graphtool version 2.2.23dev, igraph 0.6.4 and
+NetworkX 1.7.
+
+The functions are called several times, and the **average time take per
+function call** is computed and shown below. All results are for the same
[https://en.wikipedia.org/wiki/List_of_Intel_Core_i7_microprocessors#Sandy_Bridge_microarchitecture Intel Core i7 2620M]
CPU with 4 cores. In the second column are shown
the results for graphtool with [https://en.wikipedia.org/wiki/OpenMP OpenMP]
enabled using 4 threads, and the third column shows the results
using only one core.

=Algorithm == graphtool (OpenMP) == graphtool == igraph == NetworkX =
Shortest paths  0.0106 s  0.0098 s  0.00989 s  
@@ 29,19 +30,21 @@
Betweenness  579.7 s   1182.6 s  
The conclusion is that graphtool and igraph deliver overall comparable
+Both graphtool and igraph seem to deliver overall comparable
performance, at least when OpenMP is disabled. In this case, the largest
difference is the example above is !PageRank, where igraph is around
1.6x slower, but igraph comes out around 1.2x faster when computing
Kcore decomposition.
As expected, graphtool becomes faster by a factor of 4 on algorithms
which run in parallel (!PageRank and Betweenness), and thus beats igraph
in these algorithms.
+As expected, graphtool becomes faster by a factor of 4 when OpenMP is
+enabled on algorithms which run in parallel (!PageRank and Betweenness),
+and thus beats igraph in these cases.
NetworkX, on the other hand, comes at a distant third with running times
in the order of **10 to 170 times slower** than graphtool and
igraph. This is mostly due to its pure Python implementation.
+igraph. This is mostly due to its pure Python implementation, which is
+known to be usually much slower than C/C++ (see
+[http://www.scipy.org/PerformancePython here] for further comparisons).
Performance alone is not the only issue which should be considered. All
these libraries have their own advantages and disadvantages, which need

Page URL: <URL:http://graphtool.skewed.de/wiki/Performance>
graphtool <URL:http://graphtool.skewed.de/>
An efficient python module for graph analysis and manipulation.
More information about the graphtooltickets
mailing list