Quick evaluation of binomial likelihood in Rcpp

Question

I need to evaluate a large number of binomial likelihoods very quickly. Therefore, I am thinking of implementing this in Rcpp. One way to do it is the following:

#include <RcppArmadillo.h>

// [[Rcpp::depends(RcppArmadillo)]]

using namespace Rcpp;

// [[Rcpp::export]]
NumericVector eval_likelihood(arma::vec Yi,
                              arma::vec Ni,
                              arma::vec prob){

  // length of vector
  int N = prob.n_rows;

  // storage for evaluated log likelihoods
  NumericVector eval(N);

  for(int ii = 0; ii < N; ii++){

  int y = Yi(ii); // no. of successes
  int n = Ni(ii); // no. of trials
  double p = prob(ii); // success probability

  eval(ii) = R::dbinom(y,n,p,true); // argument 4 is set to true to return log-likelihood

  }

  return eval;

}

which returns equivalent log-likelihoods as dbinom() in R:

Rcpp::sourceCpp("dbinom.cpp") #source Rcpp script

# fake data
Yi    = 1:999  
Ni    = 2:1000
probs = runif(999)

evalR    = dbinom(Yi, Ni, probs, log = T) # vectorized solution in R
evalRcpp = eval_likelihood(Yi, Ni, probs) # my Rcpp solution

identical(evalR,evalRcpp)
[1] TRUE

That is, in general, a nice outcome. However, the vectorized R solution is on average slightly faster than my naive Rcpp solution:

microbenchmark::microbenchmark(R    = dbinom(Yi, Ni, probs, log = T),
                               Rcpp = eval_likelihood(Yi, Ni, probs))

Unit: microseconds
 expr     min      lq     mean   median       uq      max neval cld
    R 181.753 182.181 188.7497 182.6090 189.4515  286.100   100   a
 Rcpp 178.760 179.615 197.5721 179.8285 184.7470 1397.144   100   a

Does anyone have some guidance towards a faster evaluation of binomial log-likelihoods? Could be either faster code or some hack from probability theory. Thanks!

I think you're pretty unlikely to beat (at least significantly) the base R `dbinom()`. The folks at R Core team have implemented all the functions like this in very efficient C code. That doesn't mean you can't make efficiency gains by moving to C++ using Rcpp! But, a simple call to `dbinom()` isn't the context where you're going to do it. However, "I need to evaluate a large number of binomial likelihoods very quickly" sounds like you may be in a situation where bringing a lot of your project to C++ could improve efficiency. Maybe this is a weak form of [XY problem](http://xyproblem.info/) — duckmayr, May 23 '20 at 11:48
@duckmayr: The likelihood evaluation is part of a larger project where I already had good efficiency gains by moving to C++. Seems like there's not a good chance of beating base R in that scenario, though. I'll have to live with that bottleneck then. Thanks for pointing out that `dbinom` is already implemented in a highly efficient manner! — yrx1702, May 23 '20 at 11:57
In that case, from what I can see, you're solution should be fine. I don't know how much better you're going to get on the binomial likelihood part of your calculations, though maybe someone else knows of a better implementation. Little things might be using `[ii]` rather than `(ii)` to avoid bounds checking, and passing by reference rather than by value (will show benchmark this makes modest gain) — duckmayr, May 23 '20 at 12:11

duckmayr · Accepted Answer · 2020-05-23T12:30:43.340

Your implementation looks fine. As R's dbinom() is already implemented in efficient C code, you probably won't significantly improve on it. I do see a couple of things that might make small differences (which, when you're doing this a lot of times, might help):

You can use [ii] rather than (ii) to avoid bounds checking, as it sounds like you're in a situation where you don't have to worry about that (i.e., this will not be a user-called function, it would only be called within your C++ code where presumably your objects are set up in such a way that this won't be a problem)
You can pass by reference rather than by value (see, e.g. here)

So, I add the following version of your function:

// [[Rcpp::export]]
NumericVector eval_likelihood2(const arma::vec& Yi,
                               const arma::vec& Ni,
                               const arma::vec& prob){

    // length of vector
    int N = prob.n_rows;

    // storage for evaluated log likelihoods
    NumericVector eval(N);

    for(int ii = 0; ii < N; ii++){

        int y = Yi[ii]; // no. of successes
        int n = Ni[ii]; // no. of trials
        double p = prob[ii]; // success probability

        eval[ii] = R::dbinom(y,n,p,1); // argument 4 is set to true to return log-likelihood

    }

    return eval;

}

You can see I've just changed those two things.

I also use slightly bigger data for benchmark, though I also add in benchmark for your original smaller example too:

Rcpp::sourceCpp("so.cpp") #source Rcpp script

# fake data
Yi    = 1:99999
Ni    = 2:100000
probs = runif(99999)

evalR     = dbinom(Yi, Ni, probs, log = T) # vectorized solution in R
evalRcpp  = eval_likelihood(Yi, Ni, probs) # my Rcpp solution
evalRcpp2 = eval_likelihood(Yi, Ni, probs) # my Rcpp solution

identical(evalR,evalRcpp)
# [1] TRUE
identical(evalR,evalRcpp2)
# [1] TRUE

microbenchmark::microbenchmark(R     = dbinom(Yi, Ni, probs, log = T),
                               Rcpp  = eval_likelihood(Yi, Ni, probs),
                               Rcpp2 = eval_likelihood2(Yi, Ni, probs))

Unit: milliseconds
  expr      min       lq     mean   median       uq      max neval
     R 7.427669 7.577011 8.565015 7.650762 7.916891 62.63154   100
  Rcpp 7.368547 7.858408 8.884823 8.014881 8.353808 63.48417   100
 Rcpp2 6.952519 7.256376 7.859609 7.376959 7.829000 12.51065   100

Yi    = 1:999
Ni    = 2:1000
probs = runif(999)
microbenchmark::microbenchmark(R     = dbinom(Yi, Ni, probs, log = T),
                               Rcpp  = eval_likelihood(Yi, Ni, probs),
                               Rcpp2 = eval_likelihood2(Yi, Ni, probs))

Unit: microseconds
  expr    min       lq     mean   median       uq     max neval
     R 90.073 100.5035 113.5084 109.5230 122.5260 188.304   100
  Rcpp 90.188  97.8565 112.9082 105.2505 122.4255 172.975   100
 Rcpp2 86.093  92.0745 103.9474  97.9380 113.2660 148.591   100

Thanks, thoughtful answer + I learned something new about efficiency in Rcpp! — yrx1702, May 23 '20 at 13:57

Quick evaluation of binomial likelihood in Rcpp

1 Answers1