How to effectively combine a list of NumericVectors into one large NumericVector?

Question

I wrote the following Rcpp code which compiles, but the speed is not fast as expected.

// [[Rcpp::export]]
NumericVector combine_list_to_vec (const Rcpp::List& list)
{
  int list_size = list.size();
  int large_vec_size = 0;
  IntegerVector start_index(list_size);
  IntegerVector end_index(list_size);
  for (int ii = 0; ii < list_size; ii++)
  {
    NumericVector vec = list[ii];
    start_index[ii] = large_vec_size;
    large_vec_size += vec.size();
    end_index[ii] = large_vec_size - 1;
  }
  NumericVector large_vec(large_vec_size);   // Creating object after getting its size
  for (int ii = 0; ii < list_size; ii++)
  {
    int current_start_index = start_index[ii];
    NumericVector vec = list[ii];
    for (int jj = 0; jj < vec.size(); jj++)
    {
      large_vec[jj + current_start_index] = vec[jj];
    }
  }
  return large_vec;
}

The input variable 'list' contains a bunch of NumericVector, and I want to combine them into a large one, with '...tail - head -tail...' structure. The start_index and end_index variables are used to facilitate copy.

The microbenchmark test gives the following info for a specific example:

x=list();
x[[1]]=runif(1E6);  x[[2]]=runif(1E6);
x[[3]]=runif(1E6);  x[[4]]=runif(1E6);
x[[5]]=runif(1E6);  x[[6]]=runif(1E6);
x[[7]]=runif(1E6);  x[[8]]=runif(1E6);
x[[9]]=runif(1E6);  x[[10]]=runif(1E6);
microbenchmark(combine_list_to_vec(x) -> y)

# Unit: milliseconds
                        expr       min        lq       mean    median        uq       max neval
# y <- combine_list_to_vec(x) 84.166964 84.587516 89.9520601 84.728212 84.871673 349.33234   100

Another way that I tried is to call external R function do.call(c,x):

// [[Rcpp::export]]
List combine_list_to_vec (const Rcpp::List& list)
{
  int list_size = list.size();
  int large_vec_size = 0;
  IntegerVector start_index(list_size);
  IntegerVector end_index(list_size);
  for (int ii = 0; ii < list_size; ii++)
  {
    NumericVector vec = list[ii];
    start_index[ii] = large_vec_size;
    large_vec_size += vec.size();
    end_index[ii] = large_vec_size - 1;
  }
  NumericVector large_vec = internal::convert_using_rfunction(list, "sub_do_call");
  List rtn = List::create(large_vec, start_index, end_index);
  return rtn;
}

// The following codes exist as R codes instead of Rcpp
sub_do_call <- function (x)
{
  return (do.call(c, x));
}

The speed is almost 4 times faster than previous code. Is there any way that can speedup the combination operation by using pointer or other tools in Rcpp and/or RcppArmadillo, or simply code do.call(c,x) in Rcpp instead of calling it externally? Thank you.

Answer 1

If I understand correctly, you're basically asking, "how can I write base::unlist in Rcpp?" And, since base::unlist is an .Internal function (it has a C implementation) it's unlikely you'll be able to do better with Rcpp.

But, let's try anyway, for fun. Here's an implementation I would use that's similar to yours, but should be cheaper as we use std::copy rather than re-indexing on every iteration:

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
NumericVector combine(const List& list)
{
   std::size_t n = list.size();

   // Figure out the length of the output vector
   std::size_t total_length = 0;
   for (std::size_t i = 0; i < n; ++i)
      total_length += Rf_length(list[i]);

   // Allocate the vector
   NumericVector output = no_init(total_length);

   // Loop and fill
   std::size_t index = 0;
   for (std::size_t i = 0; i < n; ++i)
   {
      NumericVector el = list[i];
      std::copy(el.begin(), el.end(), output.begin() + index);

      // Update the index
      index += el.size();
   }

   return output;

}

/*** R
library(microbenchmark)
x <- replicate(10, runif(1E6), simplify = FALSE)
identical(unlist(x), combine(x))
microbenchmark(
   unlist(x),
   combine(x)
)
*/

Running this code gives me:

> Rcpp::sourceCpp('C:/Users/Kevin/scratch/combine.cpp')

> library(microbenchmark)

> x <- replicate(10, runif(1E6), simplify = FALSE)

> identical(unlist(x), combine(x))
[1] TRUE

> microbenchmark(
+    unlist(x),
+    combine(x)
+ )
Unit: milliseconds
       expr      min       lq     mean   median       uq      max neval
  unlist(x) 21.89620 22.43381 29.20832 23.14454 35.32135 68.09562   100
 combine(x) 20.96225 21.55827 28.13269 22.08985 24.13403 51.68660   100

So, effectively the same. We gain a tiny bit of time just because we don't do any type checking (which means this code blows up if we don't have a list containing only numeric vectors) but should at least be illustrative of the fact that we really can't do much better here.

(the only exception, I guess, would be with huge vectors where parallel processing might be helpful here)