Mon, 13 Dec 2010

RcppDE 0.1.0

A new package RcppDE has been uploaded in a first version 0.1.0 to CRAN. It provides differential evolution optimisation---a variant of stochastic optimisation that is similar to genetic algorithms but particularly suitable for the floating-point representations common in numerical optimisation. It builds of on the nice DEoptim package by Ardia et al, but reimplements the algorithm in C++ (rather than C) using a large serving of Rcpp and RcppArmadillo.

I worked on this on for a few evenings and weekends in October and November and then spent a few more evenings writing a paper / vignette (which is finished as a very first draft now) about it. This was an interesting and captivating problem as I had worked on genetic algorithms going back quite some time to the beginning and then again the end of graduate school (and traces of that early work are near the bottom of my presentations page). So what got me started? DEoptim is a really nice package, but it is implemented in old-school C. There is nothing wrong with that per se, but at the same time that I was wrestling with GAs, I also taught myself C++ which, to put it simply, offers a few more choices to the programmer. I like having those choices.

And with all the work that Romain and I have put into Rcpp, I was curious how far I could push this cart if I were to move it along. I made a bet with myself starting from the old saw shorter, easier, faster: pick any two. Would it be possible to achieve all three of these goals?

DEoptim, and I take version 2.0-7 as my reference point here, is pretty efficiently yet verbosely coded. Copying a vector takes a loop with an assignment for each element, copying a matrix does the same using two loops. Replacing that with a single statement in C++ is pretty easy. We also have a few little optimisations behind the scenes here and there in Rcpp: would all that be enough to move the needle in terms of performance? And the same time, DEoptim is also full of the uses of the old R API which we often point to in the Rcpp documentation so fixing readibility should be a relatively low-hanging fruit.

To cut a long story short, I was able to reduce code size quite easily by using a combination of C++ and Rcpp idioms. I was also able to get to faster: the paper / vignette demostrates consistent speed improvements on all setups that I tested (three standard functions on three small and three larger parameter vectors). More important speed gains were achieved by allowing use of objective functions that are written in C++ which again is both possible and easy thanks to Rcpp.

That leaves easier to prove: adding compiled objective functions is one indication; further proof could be provided by, say, moving the inner loop to parallel execution thanks to Open MP which I may attempt over the next few months. So far I'd like to give myself about half a point here. So not quite yet shorter, easier, faster: pick any three, but working on it.

Over the next few days I may try to follow up with a blog post or two contrasting some code examples and maybe showing a chart from the vignette.

/code/rcpp | permanent link