User BobH asked
on StackOverflow about accelerating path-dependent loops. He provided a simple example in which a vector gets filled conditional on the value of
the preceding element. Simple to code, but hard to vectorise.
By the time I saw that question yesterday evening,
Josh Ulrich had already posted a nice answer suggesting
to switch from
ifelse to
if to escape the overhead of a vectorised expression on simple scalars. I meekly added a comment
suggesting that
Rcpp would likely do well on this and that
someone should volunteer
such an answer. Well, it is still August and Mr. Someone is on holiday, so this morning I followed up with such an answer. And as it turns out to
work quite well indeed, we will repost it here.
Let's start with the general setup, and the two functions supplied by Josh. We also byte-compile these using the
compiler package which
is the culmination of several years of work by R core member
Luke Tierney. This package was added to R
during the last major release, and we assessed it
in this earlier blog post as well as several Rcpp-related
follow-ups. We also load the packages for on-the-fly 'inline' compilation and easy benchmarking:
library(inline)
library(rbenchmark)
library(compiler)
fun1 <- function(z)
for(i in 2:NROW(z))
z[i] <- ifelse(z[i-1]==1, 1, 0)
z
fun1c <- cmpfun(fun1)
fun2 <- function(z)
for(i in 2:NROW(z))
z[i] <- if(z[i-1]==1) 1 else 0
z
fun2c <- cmpfun(fun2)
We see that basic worker just assign to the
i-th element based on the preceding element. Function two uses the aforementioned
if statement, and both are also byte-compiled.
Writing the same code in C++ using both
Rcpp (for the R/C++ integration) and
inline for the on-the-fly compilation, linking and loading of C++ code into R is pretty
straightforward too:
funRcpp <- cxxfunction(signature(zs="numeric"), plugin="Rcpp", body="
Rcpp::NumericVector z = Rcpp::NumericVector(zs);
int n = z.size();
for (int i=1; i<n; i++)
z[i] = (z[i-1]==1.0 ? 1.0 : 0.0);
return(z);
")
This single R function call takes the code embedded in the argument to the
body variable, builds a complete function in temporary file,
and then compiles, links and loads it. We can now call
funRcpp() just like the other four functions and do so via the
benchmark() function of the
rbenchmark package.
R> z <- rep(c(1,1,0,0,0,0), 100)
R> identical(fun1(z),fun2(z),fun1c(z),fun2c(z),funRcpp(z))
[1] TRUE
R>
R> res <- benchmark(fun1(z), fun2(z),
+ fun1c(z), fun2c(z),
+ funRcpp(z),
+ columns=c("test", "replications", "elapsed", "relative", "user.self", "sys.self"),
+ order="relative",
+ replications=1000)
R> print(res)
test replications elapsed relative user.self sys.self
5 funRcpp(z) 1000 0.005 1.0 0.01 0
4 fun2c(z) 1000 0.482 96.4 0.48 0
2 fun2(z) 1000 1.989 397.8 1.98 0
3 fun1c(z) 1000 11.365 2273.0 11.37 0
1 fun1(z) 1000 13.210 2642.0 13.21 0
We can focus on the columns labelled
elapsed and
relative. The C++ version is faster by a factor of almost one-hundred compared to
the byte-compiled version of funtion2, and almost four-hundred times faster than the plain-R variant of function2. And function1 is even worse,
coming at well over twenty-two-hundred times the run-time of the C++ version. Byte-compilation also helps little here.
For comparison, we also ran the original example of a very short vector, called more frequently:
R> z <- c(1,1,0,0,0,0)
R> res2 <- benchmark(fun1(z), fun2(z),
+ fun1c(z), fun2c(z),
+ funRcpp(z),
+ columns=c("test", "replications", "elapsed", "relative", "user.self", "sys.self"),
+ order="relative",
+ replications=10000)
R> print(res2)
test replications elapsed relative user.self sys.self
5 funRcpp(z) 10000 0.047 1.00000 0.04 0
4 fun2c(z) 10000 0.134 2.85106 0.13 0
2 fun2(z) 10000 0.328 6.97872 0.32 0
3 fun1c(z) 10000 1.080 22.97872 1.08 0
1 fun1(z) 10000 1.243 26.44681 1.24 0
The qualitative ranking is unchanged: the
Rcpp version dominates. Function2 using
if instead of the vectorised
ifelse is second-best with the byte-compiled version being about twice as fast that the plain R
variant, but still almost three times slower than the C++ version. And the relative differences are less pronounced: relatively speaking, the
function call overhead matters less here and the actual looping matters more: C++ gets a bigger advantage on the actual loop operations in the longer
vectors. That it is an important result as it suggests that on more real-life sized data, the compiled version may reap a larger benefit.
All in all a nice demonstration of
Rcpp, and a gain of almost one-hundred to the best
byte-compiled version is nothing to sneeze at---especially when it is so easy to write and load a five-line C++ function thanks to
Rcpp.
Before closing, a quick reminder that I will giving two classes on
Rcpp in a few weeks. These will be in New York on September 24, and San Franciso on October 8, see
this blog post as well as
this page at Revolution Analytics (who are a
co-organiser of the classes) for details and registration information.
for the second
time, I'm at Steve's for his yearly barbecue.
After I'd done my waffles back at Banja Luka, I off-hand suggested to
do them again at the barbecue, which people replied to with an
enthousiastic 'oh yes!' from multiple mouths. So that's what
happened.
I did overdo it on the amounts, though since after I'd baked 750g
flour worth of dough, everyone still awake had already had a waffle; and
I still had 500g flour worth to go. Since the dough can't be conserved
overnight, I had to finish all of them. Which meant that I was still
making waffles at 2AM, and no-one was eating them anymore. Bummer. Oh
well, some people (including myself) had waffles this morning
instead.
Speaking of waffles, and by popular demand: A few years ago I blogged the
recipe of my waffles (hidden in a blog post about a large number of
other things).
The rest of the barbecue was fairly nice, too. I mean, obviously it
is: good food, good beer, good people to talk to, what more would you
want? Exactly.
Right now I'm waiting for food that is being prepared, after which
I'll probably get in my car and start driving home again. But that's not
for now just yet.
Yet another useful tool of which at least I heard quite late in my
Unix career is watch . For a long time I wrote one-liners like this
to monitor the output of a command:
On Day 0, we were at my favourite Jugoslawian restaurant, and
during eating and verpeiling, Andi took some pictures:
For 
As an enthusiast 
As a side-note for interested parties, 
Twenty years ago today, Linus Torvalds 
We all hate the A in ADSL, but most of us are stuck with it. So there
are any number of workarounds that keep our link to the Internet
working with a certain amount of perceived fluidity, by way of
"traffic shaping". Many of us use 
Dear Lazyweb,
since KDE4 is in unstable, the taskbar behaves very annoyingly when working with two monitors with different resolutions. I have a laptop. When I m at work, I put it into a docking station which is connected to a huge monitor. I m not working with dualhead or something, I m just using the huge monitor at work and the laptop s screen at home.
I always want the taskbar to be maximized. The problem is, that KDE s taskbar fails to adjust the size of the taskbar correctly: Starting KDE at work, the taskbar is always too small (as wide as the laptop s monitor) and my first task is to maximize the taskbar. Starting KDE when I m back home, the taskbar is too wide (as wide as the external monitor s size) for the smaller monitor and I have to (ironically) maximize it again to fit on the now smaller monitor.
Note that I m not using suspend or something. I m booting the laptop with the big screen connected or not.
I also had that problem with KDE3, but that was fixed upstream long time ago. Has anyone a solution how to avoid this problem?
.jpg)
So, we stopped our very boring story around 1992. Let's summarize
where I was at that moment: