Re: [R] extremely slow recursion in R?

From: Thomas Lumley <tlumley_at_u.washington.edu>
Date: Sat 26 Aug 2006 - 00:43:49 EST

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@u.washington.edu	University of Washington, Seattle

______________________________________________
R-help@stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. Received on Sat Aug 26 01:00:17 2006

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.1.8, at Sat 26 Aug 2006 - 02:23:19 EST.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.