Parallel recursive function in R?

Question

I’ve been wracking my brain around this problem all week and could really use an outside perspective. Basically I’ve built a recursive tree function where the output of each node in one layer is used as the input for a node in the subsequent layer. I’ve generated a toy example here where each call generates a large matrix, splits it into submatrices, and then passes those submatrices to subsequent calls. The key difference from similar questions on Stack is that each call of tree_search doesn't actually return anything, it just appends results onto a CSV file.

Now I'd like to parallelize this function. However, when I run it with mclapply and mc.cores=2, the runtime increases! The same happens when I run it on a multicore cluster with mc.cores=12. What’s going on here? Are the parent nodes waiting for the child nodes to return some output? Does this have something to do with fork/socket parallelization?

For background, this is part of an algorithm that models gene activation in white blood cells in response to viral infection. I’m a biologist and self-taught programmer so I’m a little out of my depth here - any help or leads would be really appreciated!

# Load libraries.
library(data.table)
library(parallel)

# Recursive tree search function.
tree_search <- function(submx = NA, loop = 0) {

  # Terminate on fifth loop.
  message(paste("Started loop", loop))
  if(loop == 5) {return(TRUE)}

  # Create large matrix and do some operation.
  bigmx <- matrix(rnorm(10), 50000, 250)
  bigmx <- sin(bigmx^2)

  # Aggregate matrix and save output.
  agg <- colMeans(bigmx)
  append <- file.exists("output.csv")
  fwrite(t(agg), file = "output.csv", append = append, row.names = F)

  # Split matrix in submatrices with 100 columns each.
  ind <- ceiling(seq_along(1:ncol(bigmx)) / 100)

  lapply(unique(ind), function(i) {

    submx <- bigmx[, ind == i]

    # Pass each submatrix to subsequent call.
    loop <- loop + 1
    tree_search(submx, loop) # sub matrix is used to generate big matrix in subsequent call (not shown)

  })

}

# Initiate tree search.
tree_search()

Jeff Bezos Jeff Bezos · Accepted Answer · 2020-04-13T02:59:41

After a lot more brain wracking and experimentation, I ended up answering my own question. I’m not going to refer to the original example since I've changed up my approach quite a bit. Instead I’ll share some general observations that might help people in similar situations.

1.) For loops are more memory efficient than lapply and recursive functions

When you use lapply, each call creates a copy of your current environment. That’s why you can do this:

x <- 5
lapply(1:10, function(i) {
   x <- x + 1
   x == 6 # TRUE
})
x == 5 # ALSO TRUE

At the end x is still 5, which means that each call of lapply was manipulating a separate copy of x. That’s not good if, say, x was actually a large dataframe with 10,000 variables. for loops, on the other hand, allow you to override the variables on each loop.

x <- 5
for(i in 1:10) {x <- x + 1}
x == 5 # FALSE

2.) Parallelize once

Distributing tasks to different nodes takes a lot of computational overhead and can cancel out any gains you make from parallelizing your script. Therefore, you should use mclapply with discretion. In my case, that meant NOT putting mclapply inside a recursive function where it was getting called tens to hundreds of times. Instead, I split the starting point into 16 parts and ran 16 different tree searches on separate nodes.

3.) You can use mclapply to throttle memory usage

If you split a job into 10 parts and process them with mclapply and mc.preschedule=F, each core will only process 10% of your job at a time. If mc.cores was set to two, for example, the other 8 "nodes" would wait until one part finished before starting a new one. This is useful if you are running into memory issues and want to prevent each loop from taking on more than it can handle.

Final Note

This is one of the more interesting problems I’ve worked on so far. However, recursive tree functions are complicated. Draw out the algorithm and force yourself to spend a few days away from your code so that you can come back with a fresh perspective.

Parallel recursive function in R?

1 Answers