Speed up recursion in R 600-fold with Rcpp

Rcpp package co-author Dirk Eddelbuettel provides another case study in speeding up R code by rewriting repeatedly-called R code as inline C++ functions, using the classic Fibonacci recursion algorithm as an example.

The speed gains here are impressive — over 600x compared to native recursive R code — but you could also improve performance by using a more efficient, non-recursive algorithm in R directly. But sometimes recoding can be both easier and safer, as Dirk explains:

Improved algorithms for well-understood problems are surely one way to accelerate solutions. But there are (many ?) times when we do not have the luxury of being able to think through to a new and improved approach. Or worse, such an approach may even introduce new errors or inaccurracies if we get it wrong on a first try. With Rcpp, we are able to the express the problem as written in its original statement: a simple recursion. The gain relative to a slow R implementation is noteworthy—and could of course be improved further if we really needed to by relying on better algorithms like memoization. But for day to day tasks, I gladly take speedups of (up to) a few hundred times thanks to Rcpp without having to do hard algorithmic work.

If you'd like to learn more techniques for using Rcpp for improving the performance of R code, Dirk is giving two live one-day workshops on Rcpp on September 24 in New York, and on October 8 in San Francisco.

Thinking Inside the Box: Faster (recursive) function calls: Another quick Rcpp case study