[R] extremely slow recursion in R?
Thomas Lumley
tlumley at u.washington.edu
Fri Aug 25 16:43:49 CEST 2006
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
More information about the R-help
mailing list