[Networkit] PageRank was slow because...

Christian Staudt christian.staudt at kit.edu
Wed Jul 15 16:40:07 CEST 2015


Dear NetworKit developers,
here’s a cautionary tale on how using graph iterators correctly is crucial for performance. I just got a speedup of 30x (9.5 mins to 18 secs on 117 M edges) for PageRank by changing two lines of code. Compare

		G.balancedParallelForNodes([&](node u) {
			pr[u] = 0.0;
			G.forInEdgesOf(u, [&](node u, node v) {
				pr[u] += scoreData[v] * G.weight(v, u) / deg[v];
			});
			pr[u] *= damp;
			pr[u] += teleportProb;
		});

to

		G.balancedParallelForNodes([&](node u) {
			pr[u] = 0.0;
			G.forInEdgesOf(u, [&](node u, node v, edgeweight w) {
				pr[u] += scoreData[v] * w / deg[v];
			});
			pr[u] *= damp;
			pr[u] += teleportProb;
		});


G.weight(v, u) hides a running time of O(deg(v)), so don’t use it in critical loops. Instead, use iterators and accept the edge weight as a parameter of the iterator function.

It is very likely that this is the cause of other performance bugs, so please check the code base.

Best,
Chris




-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150715/baaebf7b/attachment.sig>


More information about the NetworKit mailing list