Make cumulative sum faster

Question

I'm trying to take cumulative sums for each column of a matrix. Here's my code in R:

testMatrix = matrix(1:65536, ncol=256);
microbenchmark(apply(testMatrix, 2, cumsum), times=100L);

Unit: milliseconds
                         expr      min       lq     mean  median       uq      max neval
 apply(testMatrix, 2, cumsum) 1.599051 1.766112 2.329932 2.15326 2.221538 93.84911 10000

I used Rcpp for comparison:

cppFunction('NumericMatrix apply_cumsum_col(NumericMatrix m) {
    for (int j = 0; j < m.ncol(); ++j) {
        for (int i = 1; i < m.nrow(); ++i) {
            m(i, j) += m(i - 1, j);
        }
    }
    return m;
}');
microbenchmark(apply_cumsum_col(testMatrix), times=10000L);

Unit: microseconds
                         expr     min      lq     mean  median      uq      max neval
 apply_cumsum_col(testMatrix) 205.833 257.719 309.9949 265.986 276.534 96398.93 10000

So the C++ code is 7.5 times as fast. Is it possible to do better than apply(testMatrix, 2, cumsum) in pure R? It feels like I have an order of magnitude overhead for no reason.

Answer 1

Using a byte-compiled for loop is slightly faster than the apply call on my system. I expected it to be faster because it does less work than apply. As expected, the R loop is still slower than the simple C++ function you wrote.

colCumsum <- compiler::cmpfun(function(x) {
  for (i in 1:ncol(x))
    x[,i] <- cumsum(x[,i])
  x
})

testMatrix <- matrix(1:65536, ncol=256)
m <- testMatrix
require(microbenchmark)
microbenchmark(colCumsum(m), apply_cumsum_col(m), apply(m, 2, cumsum), times=100L)
# Unit: microseconds
#                 expr      min        lq    median        uq       max neval
#      matrixCumsum(m) 1478.671 1540.5945 1586.1185 2199.9530 37377.114   100
#  apply_cumsum_col(m)  178.214  192.4375  204.3905  234.8245  1616.030   100
#  apply(m, 2, cumsum) 1879.850 1940.1615 1991.3125 2745.8975  4346.802   100
all.equal(colCumsum(m), apply(m, 2, cumsum))
# [1] TRUE

Answer 2

It is difficult to beat C++ with just R code. The fastest way I can think of doing it is if you are willing to split your matrix in to a list. That way, R is using primitive functions and doesn't copy the object with each iteration (apply is essentially a pretty loop). You can see that C++ still wins out but there is a significant speedup with the list approach if you really just want to use R code.

fun1 <- function(){
    apply(testMatrix, 2, cumsum)
}

testList <- split(testMatrix, col(testMatrix))

fun2 <- function(){
    lapply(testList, cumsum)
}

microbenchmark(fun1(),
               fun2(),
               apply_cumsum_col(testMatrix),
               times=100L)


Unit: microseconds
                         expr      min        lq      mean   median        uq      max neval
                       fun1() 3298.534 3411.9910 4376.4544 3477.608 3699.2485 9249.919   100
                       fun2()  558.800  596.0605  766.2377  630.841  659.3015 5153.100   100
 apply_cumsum_col(testMatrix)  219.651  282.8570  576.9958  311.562  339.5680 4915.290   100

EDIT Please note that this method is slower than fun1 if you include the time to split the matrix in to a list.

Answer 3

Maybe it is to late but I will write my answer so anyone else can see it.

First of all, in your C++ code you need to clone you matrix otherwise you are write into R's memory and it is forbiden by CRAN. So your code becomes:

rcpp_apply<-cppFunction('NumericMatrix apply_cumsum_col(NumericMatrix m) {
    NumericMatrix g=clone(m);
    for (int j = 0; j < m.ncol(); ++j) {
        for (int i = 1; i < m.nrow(); ++i) {
            g(i, j) += g(i - 1, j);
        }
    }
    return g;
}');

Since your matrix is typeof integer then you can change your C++'s argument to be IntegerMatrix.

rcpp_apply_integer<-cppFunction('IntegerMatrix apply_cumsum_col(IntegerMatrix m) {
    NumericMatrix g=clone(m);
    for (int j = 0; j < m.ncol(); ++j) {
        for (int i = 1; i < m.nrow(); ++i) {
            g(i, j) += g(i - 1, j);
        }
    }
    return g;
}');

This impoved the code about 2 times. Here is a benchmark:

microbenchmark::microbenchmark(R=apply(testMatrix, 2, cumsum),Rcpp=rcpp_apply(testMatrix),Rcpp_integer=rcpp_apply_integer(testMatrix), times=10)

Unit: microseconds
        expr      min       lq      mean    median       uq      max neval
           R 1552.217 1706.165 1770.1264 1740.0345 1897.884 1940.989    10
        Rcpp  502.900  523.838  637.7188  665.0605  699.134  743.471    10
Rcpp_integer  220.455  274.645  274.9327  275.8770  277.930  316.109    10



all.equal(rcpp_apply(testMatrix),rcpp_apply_integer(testMatrix))
[1] TRUE

If your matrix has large values then you have to use NumericMatrix.