Efficient loops in R — the complexity versus speed trade-off

[This article was first published on Life in Code, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

I’ve written before about the up- and downsides of the plyr package — I love it’s simplicity, but it can’t be mindlessly applied, no pun intended. This week, I started building a agent-based model for a large population, and I figured I’d use something like a binomial per-timestep birth-death process for between-agent connections.

My ballpark estimate was 1e6 agents using a weekly timestep for about 50 years. This is a stochastic model, so I’d like to replicate it at least 100 times. So, I’ll need at least 50*50*100 = 250,000 steps. I figured I’d be happy if I could get my step runtimes down to ~1 second — dividing the 100 runs over 4 cores, this would give a total runtime of ~17.5 hours. Not short, but not a problem.

At first, I was disheartened to see the runtime of my prototype step function stretching into the minutes. What’s going on? Well, I’d used plyr in a very inappropriate way — for a very large loop. I began to investigate, and discovered that writing an aesthetically unappealing while gave me a 30+x speed-up.

All of which got me thinking — how expensive are loops and function calls in R? Next week I’m leading a tutorial in R and C++ using the wonderful Rcpp and inline packages here at Santa Fe Institute’s 2011 Complex Systems Summer School. Might this make a nice example?

It does, and in spades. Below are the test functions, and you can see that the code complexity increases somewhat from one to the other, but outcomes are identical, again with 30+x speedup for each subsequent case. Here, I’m using the native R API. I also tested using Rcpp to import rbinom(), but that ended up taking twice as long as the naive while loop.

So, the moral of the story seems to be that if you can write a long loop in pure C++, it’s a really easy win.

Note — The as< double >(y); in src below doesn’t seem to copy-and-paste correctly for some reason. If testfun2 doesn’t compile, check to make sure this bit pasted correctly.

The pure R function definitions

## use aaply -- the simplest code
require(plyr)
testfun0 

Rcpp function definitions (with lots of comments)

## define source code as string, pass to inline
src 

The tests

## Input vector
bb 

Postlude

After posting this to the very friendly Rcpp-devel mailing list, I got an in-depth reply from Douglas Bates pointing out that, in this case, the performance of vanilla apply() beats the while loop by a narrow margin. He also gives an interesting example of how to use an STL template and an iterator to achieve the same result. I admit that templates are still near-magic to me, and for now I prefer the clarity of the above. Still, if you’re curious, this should whet your appetite for some of the wonders of Rcpp.

## Using Rcpp, inline and STL algorithms and containers
 
 ## use the std::binary_function templated struct
inc 

To leave a comment for the author, please follow the link and comment on their blog: Life in Code.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)