Why does this parallel code in D scale so badly?

Question

Here is one experiment I performed comparing parallelism in C++ and D. I implemented an algorithm (a parallel label propagation scheme for community detection in networks) in both languages, using the same design: A parallel iterator gets a handle function (normally a closure) and applies it for every node in the graph. Here is the iterator in D, implemented using `taskPool` from `std.parallelism`: ``` /** * Iterate in parallel over all nodes of the graph and call handler (lambda closure). */ void parallelForNodes(F)(F handle) { foreach (node v; taskPool.parallel(std.range.iota(z))) { // call here handle(v); } } ``` And this is the handle function which is passed: ``` auto propagateLabels = (node v){ if (active[v] && (G.degree(v) > 0)) { integer[label] labelCounts; G.forNeighborsOf(v, (node w) { label lw = labels[w]; labelCounts[lw] += 1; // add weight of edge {v, w} }); // get dominant label label dominant; integer lcmax = 0; foreach (label l, integer lc; labelCounts) { if (lc > lcma…

Accepted Answer

It's hard to say because I don't fully understand how your algorithm is supposed to work, but it looks like your code is not thread-safe, which is causing the algorithm to run more iterations than necessary.

I added this to the end of `PLP.run`:

```
writeln(nIterations);
```

With 1 thread `nIterations = 19` With 10 threads `nIterations = 34` With 100 threads `nIterations = 90`

So as you can see, it's taking longer not because of some issues with `std.parallelism`, but simply because it's doing more work.

Why is your code not thread-safe?

The function you run in parallel is `propagateLabels`, which has shared, unsynchronised access to `labels`, `nUpdated`, and `active`. Who knows what bizarre behaviour this is causing, but it can't be good.

Before you start profiling, you need to fix the algorithm to be thread-safe.

Why does this parallel code in D scale so badly?

Solution

Problem