Re: [Rd] overhead of function calls

From: Prof Brian Ripley <ripley_at_stats.ox.ac.uk>
Date: Sat 18 Nov 2006 - 17:32:56 GMT

On Sat, 18 Nov 2006, Tamas K Papp wrote:

> Hi,
>
> Profiling shows that 65-70% of the time of my program is spent inside
> a single function -- this is not surprising, as it is inside an
> optimize call inside a loop (this is a dynamic programming problem).
> I would like to speed this up.
>
> The function does very little: has a single argument, evaluates a
> spline at that argument, does some simple arithmetic with it (adding
> constants, multiplication). With R being a functional programming
> language, I implemented this by calling several functions inside the
> function:
>
> ## RHS of bellman equation
> f <- function(knext,k,ei) {
> util(consf(knext,k))+quickeval(knext,gridsecpp,Vkbarpp)
> }
>
> where quickeval evaluates a spline at knext (on gridsecpp, pp-form
> Vkbarpp), util is a function in the environment, and so is consf:
>
> ## consumption
> consf <- function(knext,k) {
> rp*k+W+knext*A
> }
>
> A, W, and rp are constants in the environment.
>
> Then I call
>
> optimize(f, lower=...,upper=...,k=...)
>
> to find the maximum.
>
> Questions:
>
> 1. does function calling give a significant overhead in R?

Not compared with all but the very simplest computations: the overhead is of the order of a few microseconds. If it were otherwise, R would not to a large extent be implemented by function wrappers round .Internal calls (rather than .Primitives).

> If so, I would rewrite the function into a single one. I tried to test
> this by
>
>> f <- function(x) 1+x
>> g <- function(x) f(x)
>> x <- rnorm(1e6)
>> system.time(sapply(x,f))

> [1] 11.315 0.157 11.735 0.000 0.000
>> system.time(sapply(x,g))
> [1] 8.850 0.140 9.283 0.000 0.000
>> system.time(for (i in seq_along(x)) f(x[i]))
> [1] 2.466 0.036 2.884 0.000 0.000
>> system.time(for (i in seq_along(x)) g(x[i]))
> [1] 3.548 0.045 4.165 0.000 0.000
>
> but I find that hard to interpret -- the overhead looks significant in
> the first case, but something strange (at least to my limited
> knowledge) is happening with sapply.

Note that subsequent calls change quite a lot:

> system.time(sapply(x,f))

[1] 12.989 0.150 13.215 0.000 0.000
> system.time(sapply(x,f))

[1] 8.751 0.105 8.923 0.000 0.000
> system.time(sapply(x,f))

[1] 7.993 0.175 8.191 0.000 0.000
> system.time(sapply(x,f))

[1] 7.016 0.058 7.074 0.000 0.000
> system.time(sapply(x,f))

[1] 7.748 0.181 7.932 0.000 0.000
> system.time(sapply(x,g))

[1] 8.289 0.074 8.371 0.000 0.000

Several things are going on here, but most likely the most important is that the memory manager is being tuned. On my (64-bit) system:

> gc()

           used (Mb) gc trigger (Mb) max used (Mb)
Ncells  224202 12.0     407500 21.8   350000 18.7
Vcells 1115457 8.6 1519644 11.6 1419269 10.9
> for(i in 1:5) sapply(x,f)
> gc()

           used (Mb) gc trigger (Mb) max used (Mb) Ncells 224206 12.0 2156470 115.2 2665684 142.4 Vcells 2115455 16.2 7060137 53.9 8164087 62.3

Note the factor 5x differences.

It is better to profile here, so if I profile

> for (i in seq_along(x)) g(x[i])

I get

     self.time self.pct total.time total.pct
"f"      2.18     62.6       2.34      67.2
"g"      1.14     32.8       3.48     100.0
"+"      0.16      4.6       0.16       4.6


The extra call to g is taking about 1 usec (as I expected). Note that lazy evaluation means (I think) that f is being charged for the evaluation of the argument, not g.

> 2. Do calls to .C or .Fortran carry large overhead? If they don't, I
> would recode f in either.

No (and calls to .Call carry less, as there is no duplication on call and return).

-- 
Brian D. Ripley,                  ripley@stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595

______________________________________________
R-devel@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
Received on Sun Nov 19 07:50:23 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 18 Nov 2006 - 21:30:48 GMT.

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