How to reverse an integer vector efficiently?

Question

UPDATE

BUG: there was a bug in rev2 and it is fixed now.

rev1 and Rcpprev1 are removed.

I have also included different functions and made modifications according to the comments and answers.

Conclusion: rev4 is the best for my purpose, RcppRev3 is better for long vector.

---

I have a program which requires reversing an integer vector (fixed length) many times. I profiled the code, the rev function took up about 30% of the total time. I was very surprised by the slow performance of the function rev in R. So I decided to compare the base R rev with some other alternatives

library(Rcpp)
library(microbenchmark)
rev2 = function(x){
    nx = length(x)
    y = vector("numeric", nx)
    for(i in 1:nx) y[i] = x[nx-i+1]
    y
}
rev3 = function(x){
    x[length(x):1]
}
rev4 = function(x){
    .subset(x, length(x):1)
}

Rcpp equivalence:

sourceCpp(code='
#include <Rcpp.h>

using namespace Rcpp;


// [[Rcpp::export]]
IntegerVector Rcpprev2(IntegerVector x){
    int nx = x.size();
    IntegerVector y(nx);
    for(int i = 0; i<nx; i++){
        y[i] = x[nx-i-1];
    }
    return(y);
}

// [[Rcpp::export]]
IntegerVector RcppRev3(IntegerVector x) {
  return rev(x);
}

// [[Rcpp::export]]
std::vector<int> CppRev(std::vector<int> & x) {
  std::reverse(x.begin(), x.end());
  return x;
}

')

Microbenchmark:

> x = c(1L,2L,3L,4L)
> microbenchmark(rev(x), rev2(x), rev3(x), rev4(x), Rcpprev2(x),  RcppRev3(x), CppRev(x))
Unit: nanoseconds
        expr  min     lq median     uq   max neval
      rev(x) 4614 5501.0 6086.5 8208.0 32860   100
     rev2(x) 5765 6965.0 7803.0 8784.5 28637   100
     rev3(x) 1013 1351.0 1521.5 1985.5  9977   100
     rev4(x)  961 1317.0 1485.5 1728.5 16492   100
 Rcpprev2(x) 2008 2360.0 2558.5 3075.5 17342   100
 RcppRev3(x) 2045 2377.5 2607.5 3718.0  9184   100
   CppRev(x) 2279 2668.0 2947.0 3381.0 35614   100

It turns out the the fastest method is the pure R method rev4, it is even faster than the Rcpp functions.

Let's consider longer vector.

> x = rep(c(1L,2L,3L,4L), 1000)
> microbenchmark(rev(x), rev2(x), rev3(x), rev4(x), Rcpprev2(x),  RcppRev3(x), CppRev(x))
Unit: microseconds
        expr      min        lq    median        uq      max neval
      rev(x)   26.887   29.9425   39.2165   50.4080   71.614   100
     rev2(x) 3899.577 4195.3530 4370.5410 4743.3585 6117.387   100
     rev3(x)   22.092   24.4405   25.8340   27.8230   51.602   100
     rev4(x)   22.346   24.3150   25.8800   28.9425   90.666   100
 Rcpprev2(x)    6.039    7.6405    8.4530   11.6720   31.054   100
 RcppRev3(x)    5.384    6.1425    6.7395    8.3295   47.981   100
   CppRev(x)   10.462   12.0375   13.4130   17.6725   58.012   100

Rcpp functions are much better for long vectors.

Answer 1

You are mixing approaches which allocated new memories in copy, and those who do not.

I would try instantiating a std::vector<int> from the object pointer, and calling the appropriate reverse method of the C++ vector. And then there is of course the Rcpp sugar method ...

So two more added:

R> microbenchmark(rev(x), rev1(x), rev2(x), rev3(x), Rcpprev1(x), Rcpprev2(x), 
+                 RcppRev3(x), CppRev(x))
Unit: microseconds
        expr   min     lq median      uq      max neval
      rev(x) 7.676 9.1070 9.9870 11.1445   71.559   100
     rev1(x) 1.446 1.9565 2.1580  2.4280   23.310   100
     rev2(x) 4.333 5.2875 5.9305  6.4335   17.458   100
     rev3(x) 1.229 1.6875 1.9310  2.1115   12.841   100
 Rcpprev1(x) 1.949 2.5440 2.8875  3.3655 7313.028   100
 Rcpprev2(x) 1.686 2.0840 2.6260  3.1960 2632.929   100
 RcppRev3(x) 1.544 2.0770 2.6130  2.9330   15.722   100
   CppRev(x) 1.986 2.6100 3.0530  3.6035   14.091   100
R> 

But I suspect that with n=4 you have little to measure here.

Edit: Here is an updated version reflecting Kevin's excellent point about () versus [], and adding Randy's new rev4 -- and running it all on meaningful vectors. Edit 2: Still had one () where I needed []. The [] is close to the Rcpp sugar performance but not quite there.

R> microbenchmark(rev(x), rev2(x), rev3(x), rev4(x), Rcpprev2r(x),
+                 Rcpprev2s(x), RcppRev3(x), CppRev(x))
 Unit: microseconds
          expr      min       lq   median       uq      max neval
        rev(x) 3505.205 3603.892 4307.269 4581.047 45761.91   100
       rev2(x)  273.258  294.350  341.571 1258.093 42992.72   100
       rev3(x) 3489.653 3573.588 4462.155 4545.285 46253.93   100
       rev4(x) 3481.903 3575.505 4409.817 4567.506 48873.70   100
  Rcpprev2r(x) 3433.918 3482.274 3507.504 3554.779  4519.62   100
  Rcpprev2s(x)  364.481  379.853  403.149  484.366  1684.71   100
   RcppRev3(x)  269.145  283.750  290.870  346.462 42867.46   100
     CppRev(x)  907.719  963.175  991.787 1126.783  2313.97   100
 R> 

The sugar version still looks good to me.

For completeness, my [updated, twice] file is below.

#include <Rcpp.h>

using namespace Rcpp;

// [[Rcpp::export]]
IntegerVector Rcpprev2r(IntegerVector x){
    int nx = x.size();
    IntegerVector y(nx);
    for(int i = 0; i<nx; i++){
        y(i) = x(nx-i-1);
    }
    return(y);
}

// [[Rcpp::export]]
IntegerVector Rcpprev2s(IntegerVector x){
    int nx = x.size();
    IntegerVector y(nx);
    for(int i = 0; i<nx; i++){
        y[i] = x[nx-i-1];
    }
    return(y);
}

// [[Rcpp::export]]
IntegerVector RcppRev3(IntegerVector x) { 
  return rev(x);
} 

// [[Rcpp::export]]
std::vector<int> CppRev(std::vector<int> & x) { 
  std::reverse(x.begin(), x.end());
  return x;
} 

The R part is below:

/*** R
library(Rcpp)
library(microbenchmark)
x = rep(c(1L,2L,3L,4L), each=1e5)
rev2 = function(x){
    nx = length(x)
    y = vector("numeric", nx)
    for(i in nx) y[i] = x[nx-i+1]
    y
}
rev3 = function(x){
    x[length(x):1]
}
rev4 = function(x){
    .subset(x, length(x):1)
}
microbenchmark(rev(x), rev2(x), rev3(x), rev4(x), Rcpprev2r(x), 
               Rcpprev2s(x), RcppRev3(x), CppRev(x))
*/

Answer 2

FYI: There is a cost in using operator() instead of operator[] when indexing Rcpp vectors. This is because operator() uses the offset function, which does bounds checking, unlike operator[]. See:

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
IntegerVector RcppRev(IntegerVector x) {
  int n = x.size();
  IntegerVector output = no_init(n);
  for (int i=0; i < n; ++i) {
    output[i] = x[n - i - 1];
  }
  return output;
}

// [[Rcpp::export]]
IntegerVector RcppRev2(IntegerVector x){
    int nx = x.size();
    IntegerVector y(nx);
    for(int i = 0; i<nx; i++){
        y(i) = x(nx-i-1);
    }
    return(y);
}

/*** R
library(microbenchmark)
x <- as.integer(rnorm(1E7))
identical( rev(x), RcppRev(x) )
identical( rev(x), RcppRev2(x) )
microbenchmark( times=5, 
  rev(x),
  RcppRev(x),
  RcppRev2(x)
)
*/

sourceCpp on this gives me:

> Rcpp::sourceCpp('~/Desktop/rev.cpp')

> library(microbenchmark)

> x <- as.integer(rnorm(1E7))

> identical( rev(x), RcppRev(x) )
[1] TRUE

> identical( rev(x), RcppRev2(x) )
[1] TRUE

> microbenchmark( times=5, 
+   rev(x),
+   RcppRev(x),
+   RcppRev2(x)
+ )
Unit: milliseconds
        expr       min        lq   median        uq      max neval
      rev(x) 54.987311 55.261393 55.48561 56.083582 70.88035     5
  RcppRev(x)  8.375551  8.458457  8.70446  8.800677 63.12635     5
 RcppRev2(x) 75.398164 75.733779 75.74356 76.027000 76.59727     5

Answer 3

Your conclusion is wrong. For large vectors rev1 versions of both R and RCpp are impractical. rev2 comes out to be fast.

x = rep(c(1L, 2L, 3L, 4L), 1e+05)
microbenchmark(rev(x), rev2(x), rev3(x), Rcpprev1(x), Rcpprev2(x))
## Unit: microseconds
##         expr      min        lq    median        uq       max neval
##       rev(x) 2159.888 2202.9270 2235.3715 2515.2895 32350.315   100
##      rev2(x)  201.621  221.3185  229.9265  255.9155  1577.871   100
##      rev3(x) 2139.362 2191.5050 2212.6935 2907.7710 32202.328   100
##  Rcpprev1(x)    1.655    3.8075    9.6010   13.5740    18.871   100
##  Rcpprev2(x) 4784.596 4857.7615 4892.3580 4957.4130  5777.800   100

Update

Here are updated benchmark using Dirk's CppRev and Rcpprev3 functions.

RcppRev3 is best here.

microbenchmark(rev(x), rev2(x), rev3(x), Rcpprev2(x), RcppRev3(x), CppRev(x))
## Unit: microseconds
##         expr      min        lq   median       uq       max neval
##       rev(x) 2157.902 2227.2605 2502.874 2975.143 32623.777   100
##      rev2(x)  202.945  231.7475  250.453  829.822  1042.865   100
##      rev3(x) 2127.112 2205.9070 2321.946 2947.996 32239.076   100
##  Rcpprev2(x) 4805.453 4878.6190 4924.637 5018.495  5846.661   100
##  RcppRev3(x)  189.040  206.0900  222.478  797.874  1135.232   100
##    CppRev(x) 1368.304 1410.6810 1432.035 1489.972 31546.151   100