Be kind don’t rbind

The other day I was helping to refactor an R package and came across one of the biggest performance blockers there is: dynamically growing matrices. Of course I repeated the mantra “Always preallocate your variables” but in this case, it is not clear how big (in terms of rows) the final matrix will be. So there is no way around growing the matrix dynamically.

The chosen approach in the package was to use rbind similar to this

mat <- vector()
while(<condition>) {
    if(<condition>) {
        tmp <- <do calculation>
        mat <- rbind(mat, tmp)
    }
}

Disregarding performance, this seems like a sensible approach. Just add new rows to the end of the matrix. But a little bit of profiling showed that this was an extreme bottleneck in the function it appears. So what are viable alternatives? let’s benchmark some solutions. Note that we assume to know n here but in reality, we do not know how big it will be at the end.

As a baseline we implement a function that preallocates memory.

fmat <- function(n) {
    res <- matrix(NA, n, n)
    for (i in 1:n) {
        res[i, ] <- runif(n)
    }
    res
}

The first contender is the rbind approach.

frbind <- function(n) {
    res <- vector()
    for (i in 1:n) {
        res <- rbind(res, runif(n))
    }
    res
}

For the second approach, we try to reduce the number of rbinds by growing the final matrix in chunks. For csize = 1 we obtain frbind() and csize = n we have fmat().

fchunks <- function(n, csize = 10) {
    chunk <- matrix(NA, csize, n)
    res <- vector()
    for (i in 1:n) {
        if (i %% csize == 0) {
            chunk[csize, ] <- runif(n)
            res <- rbind(res, chunk)
            chunk <- matrix(NA, csize, n)
        } else {
            chunk[i %% csize, ] <- runif(n)
        }
    }
    res[!is.na(res[, 1]), ]
}

The last approach is to grow list which is converted to a matrix at the end.

flist <- function(n) {
    res <- list()
    for (i in 1:n) {
        res[[length(res) + 1]] <- runif(n)
    }
    do.call(rbind, res)
}

n <- 1000
bench <- microbenchmark::microbenchmark(
    fmat(n),
    frbind(n),
    fchunks(n, csize = 10),
    flist(n),
    times = 1, unit = "ms"
)

Warning in microbenchmark::microbenchmark(fmat(n), frbind(n), fchunks(n, : less
accurate nanosecond times to avoid potential integer overflows

expr	min	lq	mean	median	uq	max	neval
flist(n)	7.395457	7.395457	7.395457	7.395457	7.395457	7.395457	1
fmat(n)	10.080998	10.080998	10.080998	10.080998	10.080998	10.080998	1
fchunks(n, csize = 10)	123.720452	123.720452	123.720452	123.720452	123.720452	123.720452	1
frbind(n)	981.823269	981.823269	981.823269	981.823269	981.823269	981.823269	1

The performance of the rbind approach is really terrifyingly bad. The list approach on the other hand is extremely efficient. It performs equally well as the preallocated matrix approach. I unfortunately lack the understanding of the R internals here, but it seems as if dynamically growing a list does not have any (or at least not much) overhead.

Update

Lluís Revilla suggested that cbind might be more efficient than rbind, given that R mostly deals in columns.

fcbind <- function(n) {
    res <- vector()
    for (i in 1:n) {
        res <- cbind(res, runif(n))
    }
    t(res)
}

n <- 1000
bench <- microbenchmark::microbenchmark(
    fmat(n),
    frbind(n),
    fcbind(n),
    fchunks(n, csize = 10),
    flist(n),
    times = 1, unit = "ms"
)

expr	min	lq	mean	median	uq	max	neval
flist(n)	5.731185	5.731185	5.731185	5.731185	5.731185	5.731185	1
fmat(n)	7.040643	7.040643	7.040643	7.040643	7.040643	7.040643	1
fchunks(n, csize = 10)	117.605220	117.605220	117.605220	117.605220	117.605220	117.605220	1
fcbind(n)	396.306615	396.306615	396.306615	396.306615	396.306615	396.306615	1
frbind(n)	982.066440	982.066440	982.066440	982.066440	982.066440	982.066440	1

So cbind is indeed a lot faster than rbind, but still much worse than the list approach.