Skip to content
Prev 54789 / 63424 Next
Original Raw

[parallel] fixes load balancing of parLapplyLB

Christian Krause 
Dear R-Devel List,

**TL;DR:** The function **parLapplyLB** of the parallel package has [reportedly][1] (see also attached RRD output) not
been doing its job, i.e. not actually balancing the load. My colleague Dirk Sarpe and I found the cause of the problem
and we also have a patch to fix it (attached). A similar fix has also been provided [here][2].

[1]: https://stackoverflow.com/questions/38230831/why-does-parlapplylb-not-actually-balance-load
[2]: https://bugs.r-project.org/bugzilla3/show_bug.cgi?id=16792


## The Call Chain

First, we traced the relevant R function calls through the code, beginning with `parLapplyLB`:

1.  **parLapplyLB:** clusterApply.R:177, calls **splitList**, then **clusterApplyLB**
2.  **splitList:** clusterApply.R:157
3.  **clusterApplyLB:** clusterApply.R:87, calls **dynamicClusterApply**
4.  **dynamicClusterApply:** clusterApply.R:39


## splitList

We used both our whiteboard and an R session to manually *run* a few examples. We were using lists of 100 elements and 5
workers. First, lets take a look at **splitList**:

```r
[1] 20 20 20 20 20
[1] 20 19 19 19 20
[1] 5 5 5 5 4 5 5 5 5 5 4 5 5 5 5 4 5 5 5 5
```

As we can see in the examples, the work is distributed as equally as possible.


## dynamicClusterApply

**dynamicClusterApply** works this way (simplified):

1.  it first gives a chunk to each worker
2.  once a worker comes back with the result, it is given the next chunk

**This is the important part:** As long as there are **more** chunks than workers, there will be load balancing. If
there are fewer chunks than workers, each worker will get **at most one chunk** and there is **no** load balancing.


## parLapplyLB

This is how **parLapplyLB** splits the input list (with a bit of refactoring, for readability):

```r
parLapplyLB <- function(cl = NULL, X, fun, ...)
{
    cl <- defaultCluster(cl)

    chunks <- splitList(X, length(cl))

    do.call(c,
            clusterApplyLB(cl, x = chunks, fun = lapply, fun, ...),
            quote = TRUE)
}
```

For our examples, the chunks have these sizes:

```r
[1] 20 20 20 20 20
```

There we have it: 5 chunks. 5 workers. With this work distribution, there can't possibly be any load balancing, because
each worker is given a single chunk and then it stops working because there are no more chunks.

Instead, **parLapplyLB** should look like this (patch is attached):

```r
parLapplyLB <- function(cl = NULL, X, fun, ...)
{
    cl <- defaultCluster(cl)

    chunkSize <- max(length(cl), ceiling(length(X) / length(cl)))

    chunks <- splitList(X, chunkSize)

    do.call(c,
            clusterApplyLB(cl, x = chunks, fun = lapply, fun, ...),
            quote = TRUE)
}
```

Examples with a cluster of 5 workers:

```r
# length(cl) < length(X)
[1] 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

# length(cl) >= length(X)
[1] 1 1 1 1
# one worker idles here, but we can't do better than that
```

With this patch, the number of chunks is larger than the number of workers, if possible at all, and then load balancing
should work.

Best Regards

Thread (5 messages)

Christian Krause fixes load balancing of parLapplyLB Feb 12 Christian Krause fixes load balancing of parLapplyLB Feb 19 Henrik Bengtsson fixes load balancing of parLapplyLB Feb 19 Christian Krause fixes load balancing of parLapplyLB Feb 20 Tomas Kalibera fixes load balancing of parLapplyLB Feb 26