Compiling C code to be called from R
Some timings for the Fibonacci sequence

As an interpreted language, R has some limitations when it comes to racing against the clock. Calling precompiled code is a common trick to speed-up R code. Computationally intensive tasks can be implemented in a compiled language such as C. Then, the function can be loaded in R as a shared object using using ‘dyn.load(). A call to C functions can be arranged from R by means of the function ‘.C()’. See this section of the manual for further details about how to interface with foreign languages.

In this post I report some timings for the Fibonacci sequence using different compilers and options. The table below reports the timings for each version of the procedure, respectively for Fibonacci sequences of length 30, 40 and 45. The files used in this exercise can be obtained here.

Just to introduce the context, the Fibonacci sequence is defined as follows. The first two numbers in the sequence are 0 and 1. Each subsequent number is the sum of the previous two. The first number are therefore: 0, 1, 1, 2, 3, 5, 8, 13, 21,… A direct implementation based on a recursion gives us a cumbersome function suitable for our experimental purposes.

fib <- function(n)
  if (n < 2)
  z1 <- fib(n-1)
  z2 <- fib(n-2)
  z1 + z2

The version labelled 'fib00' is the a pure R function. We can see that we certainly chose a cumbersome procedure that will be suitable for the sake of comparisons.

Timings for Fibonacci sequences (in seconds)
Label Compiler Options Parallel fib(30) fib(40) fib(45)
fib00 R intrepreter - No 6.241 >60.000 >60.000
fib10 gcc default No 0.017 2.035 22.553
fib11 gcc no -fpic No 0.007 0.907 10.253
fib12 cilkplus gcc default No 0.014 1.665 18.284
fib13 cilkplus gcc no -fpic No 0.007 0.863 9.503
fib20 cilkplus gcc default Yes 0.009 1.042 11.370
fib21 cilkplus gcc no -fpic Yes 0.004 0.539 5.903

We observe the following main points:

  1. Given a compiler, when the tag '-fpic' is included the computations are slower. For example 'fib10' (the default 'R CMD SHLIB') takes around 22 seconds to run fib(45) while 'fib11' (the same as 'R CMD SHLIB' but with no '-fpic') computes fib(45) in half the time of 'fib10'.
  2. Ceteris paribus, the cilkplus gcc compiler leads to faster functions. 'fib12' is slightly faster than 'fib10'; similarly 'fib13' is slightly faster than 'fib11'. Differences are negligible for lowest values of the Fibonacci sequence considered in the examples, fib(30).
  3. As expected for relatively long Fibonacci sequences, parallelization speeds-up the code. When the gcc compiler is used (with no parallelization) 'fib10', parallelization, 'fib20', reduces the computation time by around a 50%. Given the cilkplus gcc compiler and the options passed to the compiler, parallelization reduces the computation time by around a 38%.

These results cannot be generalized to other algorithms or scenario. In fact, foretelling which approach will be faster is often difficult. Nevertheless, these timings can be useful as a reference.

This entry was posted in performance and tagged , , , . Bookmark the permalink.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *