[graph-tool-tickets] [graph-tool] Page: Performance changed

graph-tool 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://graph-tool.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 graph-tool 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 graph-tool with [https://en.wikipedia.org/wiki/OpenMP OpenMP]
 enabled using 4 threads, and the third column shows the results
 using only one core.
-
 
 ||=Algorithm           =||= graph-tool (OpenMP) =||= graph-tool =||=   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 graph-tool and igraph deliver overall comparable
+Both graph-tool 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
 K-core decomposition.
 
-As expected, graph-tool 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, graph-tool 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 graph-tool 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://graph-tool.skewed.de/wiki/Performance>
graph-tool <URL:http://graph-tool.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://graph-tool.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 graph-tool 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 graph-tool with [https://en.wikipedia.org/wiki/OpenMP OpenMP]
 enabled using 4 threads, and the third column shows the results
 using only one core.
-
 
 ||=Algorithm           =||= graph-tool (OpenMP) =||= graph-tool =||=   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 graph-tool and igraph deliver overall comparable
+Both graph-tool 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
 K-core decomposition.
 
-As expected, graph-tool 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, graph-tool 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 graph-tool 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://graph-tool.skewed.de/wiki/Performance>
graph-tool <URL:http://graph-tool.skewed.de/>
An efficient python module for graph analysis and manipulation.


More information about the graph-tool-tickets mailing list