[R] extremely slow recursion in R?

[Thomas Lumley]

On Fri, 25 Aug 2006, Joerg van den Hoff wrote:
>
> maybe someone's interested:
> I made the same observation of seemingly very slow recursion recently: just 
> for fun I used the (in)famously inefficient
>
> fib <- function(n = 1) {
>   if (n < 2)
>      fn <- 1
>   else
>      fn <- fib(n - 1) + fib(n - 2)
>   fn
> }
>
> for calculating the fibonacci numbers and compared `fib(30)' (about 1.3e6 
> recursive function calls ...) to some other languages (times in sec):
>
> language  time
> ==============
> C          0.034  (compiled, using integers)
> Ocaml      0.041  (compiled, using integers)
> Ocaml      0.048  (interpreted, using integers)
> C          0.059  (compiled, using floats)
> Lua        1.1
> ruby       3.4
> R          21
> octave    120
>
> apart from octave (which seems to have a _real_ issue with recursive function 
> calls), R is by far the slowest in this list and still a factor 7-20 slower 
> than the interpreter based Lua and ruby. the speed loss compared to C or 
> Ocaml is about a factor of 350-600 here (Ocaml keeps its speed more or less 
> in this simple example even in 'script mode', which is remarkable, I think 
> (and it usually loses only a factor of about 7 or so in script mode compared 
> to the compiled variant)
>
> for the specialists the bad performance of R in this situation might not be 
> surprising, but I was not aware that recursive function calls are seemingly 
> as expensive as explicit loops (where the execution time ratio of R to C 
> again is of the same order, i.e. =~ 400).

Recursive function calls are likely to be *more* expensive than explicit 
loops, because of the memory and function call overhead.  This is true in 
most languages, and is why tail recursion optimization is a basic feature 
of compilers for functional languages.

> of course, such comparsions don't make too much sense: the reason to use R 
> will definitely not be its speed (which, luckily, often does not matter), but 
> the combination of flexible language, the number of available libraries and 
> the good 2D graphics.

The benchmarks are interesting (and reinforce my feeling that I need to
look at ocaml sometime).  They might be more interesting on a problem for 
which recursion was a sensible solution -- something simple like printing 
the nodes of a tree, or a more complicated problem like depth-first search 
in a graph.

It's certainly true that people don't pick R over other minority languages 
like Ocaml for its blazing speed, but for other reasons. As programming 
blogger Steve Yegge has observed when comparing advantages and 
disadvantages of various languages: "ML and Haskell are both from Planet 
Weird. And the people of that planet evidently do not believe in 
libraries".

More to the point, the ratio of speeds is much lower for many uses. For 
example, I recently translated to C an R program that computed the 
conditional score estimator for a Cox model with measurement error, and 
the C version ran about five times faster.  This was about the same speed 
increase than I had already obtained in the interpreted code by replacing 
a bisection search with uniroot().

In some cases the ratio may even be less than 1 -- since R can use 
optimized BLAS routines you might expect that some matrix operations would 
be faster in interpreted R than in C code written by the average user.  I 
have a second-hand report from a student here that this was actually the 
case -- he wrote compiled matrix routines and his code got slower.

It would certainly be nice if there were a faster statistical language 
with nice features, whether by speeding up R or by adding statistical 
features to something that compiles to native code, like Common Lisp or 
ocaml, or by taking better advantage of multicore computers as they 
proliferate.  These problems do need more people to work on them 
(especially as Bell Labs isn't in the statistical computing business any 
more).  There's a conference in New Zealand in February and abstract 
submissions are still open.


 	-thomas

Thomas Lumley			Assoc. Professor, Biostatistics
tlumley at u.washington.edu	University of Washington, Seattle