Speeding up parentheses (and lots more) in R

2010-08-19 at 1:07 pm 14 comments

As I noted here, enclosing sub-expressions in parentheses is slower in R than enclosing them in curly brackets. I now know why, and I’ve modified R to reduce (but not eliminate) the slowness of parentheses. The modification speeds up many other operations in R as well, for an average speedup of something like 5% for programs that aren’t dominated by large built-in operations like matrix multiplies.

I looked at the source code for the latest version of R, 2.11.1, and figured out what’s going on. The difference between parentheses and curly brackets comes about because R treats curly brackets as a “special” operator, whose arguments are not automatically evaluated, but it treats parentheses as a “built in” operator, whose arguments (just one for parentheses) are evaluated automatically, with the results of this evaluation stored in a LISP-style list. Creating this list requires allocation of memory and other operations which seem to be slow enough to cause the difference, since the curly bracket operator just evaluates the expressions inside and returns the last of them, without creating such a list. Furthermore, the implementation allocates one more “CONS” cell than is necessary when creating this list, apparently because the programmer found this slightly easier than writing code to avoid creating the extra cell.

Since this is time critical code, not just for parentheses but for most operators, allocating a cell unnecessarily is a bad idea. I modified the program to avoid this, changing the evalList and evalListKeepMissing procedures in the eval.c source file in the src/main directory. Here are the old and new versions of these procedures (probably of interest only to R hackers).

Here are some timing results. First with the R 2.11.1 unmodified, on an Intel Linux system:

> a <- 5; b <- 1; c <- 4
> f <- function (n) for (i in 1:n) d <- 1/{a*{b+c}}
> g <- function (n) for (i in 1:n) d <- 1/(a*(b+c))
> system.time(f(1000000))
 user  system elapsed
 1.830   0.010   1.842
> system.time(g(1000000))
 user  system elapsed
 1.990   0.000   1.988

Parentheses are 8.7% slower than curly brackets.

Now here are the results with my modified version:

> a <- 5; b <- 1; c <- 4
> f <- function (n) for (i in 1:n) d <- 1/{a*{b+c}}
> g <- function (n) for (i in 1:n) d <- 1/(a*(b+c))
> system.time(f(1000000))
 user  system elapsed
 1.780   0.000   1.783
> system.time(g(1000000))
 user  system elapsed
 1.820   0.000   1.828

Now parentheses are only 2.2% slower than curly brackets. Furthermore, the curly bracket version is 2.7% faster than before, and the parenthesis version is 8.5% faster.

Here’s a test on a program that implements EM for a simple model. First, with the unmodified version of R (running far more iterations of EM than really needed):

> system.time(print(EM.censored.poisson(5,3.2,20,iterations=1000000)))
[1] 1.049699
 user  system elapsed
 13.690   0.020  13.703

And now my modified version of R:

> system.time(print(EM.censored.poisson(5,3.2,20,iterations=1000000)))
[1] 1.049699
 user  system elapsed
 12.860   0.020  12.878

My new version is 6% faster than the old version of R.

The size of the improvement will vary a lot from one R program to another, of course. (The nature of the change is such that I don’t think any programs will be slower.)  But one can see that the simple modification I made has produced a significant improvement — a 6% speedup is a lot for such a small change.  From looking at the source code for R, I think a number of other improvements can be made without great effort.  In particular, arithmetic on large vectors can be speeded up substantially, including the squaring operation discussed here. The changes to do this will also speed up arithmetic on short vectors, including scalars, but I don’t yet know how significant the improvement will be in that context.

The fundamental reason for the slowness of the current R implementation seems to be a lack of attention by the implementors to efficiency in code that is on the critical interpretive pathway. This is the opposite fault to what is often seen among hackers — an obsessive focus on efficiency even where it doesn’t matter. One should focus on efficiency where it matters, and focus on other things where it doesn’t matter (which is typically 95% of a program). On the plus side, the R source code is fairly readable, even though it lacks much in the way of informative comments. It was readable enough that I was able to figure out what’s going on and modify the program in less than a day. My next task is to figure out how to get the modification into the next release of R…

UPDATE: I forgot to mention that the real solution to speeding up parentheses is to get rid of them entirely. The only reason for them to be preserved in R’s internal expression tree is so that they can be printed when an expression is deparsed. But for that, one could just have a field in each expression node saying how many pairs of parentheses directly enclose it (usually 0 or 1, except for people who really like redundant parentheses), which can be accessed when deparsing the expression, but which would not slow down execution of the program.

About these ads

Entry filed under: Computing, R Programming, Statistics, Statistics - Computing. Tags: .

Two Surpising Things about R Fourteen patches to speed up R

14 Comments Add your own

  • 1. RedBlue  |  2010-08-20 at 5:56 am

    Thanks, a very useful tip.

    Reply
  • 2. Bjoern  |  2010-08-20 at 12:52 pm

    Strange that no one else noticed this before. I hope this will be incorporated in future versions of R. Despite all the advantages of R, it remains just unbelievably slow, particularly for iterative simulations…

    Reply
  • 3. Matt Shotwell  |  2010-08-20 at 7:18 pm

    Nice work! You ought to submit this to R-devel with a discussion of your findings. Don’t send those .doc files though… Create a real patch with the diff program.

    -Matt

    Reply
  • 4. Radford Neal  |  2010-08-20 at 9:12 pm

    Thanks.

    The code I posted is in .doc files because wordpress doesn’t accept .txt files. Rather annoying…

    Reply
  • 5. mpiktas  |  2010-08-23 at 2:07 am

    Hm, what about parsing? One of the features of R that I love is that you can easily convert code to strings, do some string replacements, and convert them back to code. Does this still work with changed code?

    Reply
  • 6. Radford Neal  |  2010-08-23 at 2:40 am

    The modification I implemented that I described above is purely an internal optimization, with no user-visible effects, apart from the speedup. My suggestion to “get rid of” parentheses is also a purely internal strategy. As I say, one would keep around counts of how many parens enclose an expression so that deparsing would reproduced the parentheses as originally written. Again, there would be no user-visible effects, except perhaps for users picking apart the R expression tree. (I haven’t thought out the details of this suggestion. I don’t even know whether R users are able to look at the expression tree;; it’s certainly not something that’s normallly done.)

    Reply
    • 7. mpiktas  |  2010-08-23 at 2:53 am

      Here is the example of what I am calling accessing expression tree:
      aa=expression(a+(b+c))
      > aa[[1]]
      a + (b + c)
      > aa[[1]][[1]]
      `+`
      > aa[[1]][[2]]
      a
      > aa[[1]][[3]]
      (b + c)
      > aa[[1]][[3]]=as.name(“c”)
      > aa
      expression(a + c)

      I checked the code with the curly brackets it still works. Will it still work with your changes?

      Though for everyday users this type of code is practically never used, when programming I find it very useful. Looking at the code from some packages I see that it is used quite extensively, for example in formula parsing.

      Reply
      • 8. Radford Neal  |  2010-08-23 at 8:10 am

        The change I’ve actually programmed, for eliminating an unnecessary allocation of a CONS cell, would have no effect on this.

        The change I proposed, but haven’t implemented, for getting rid of parentheses in the expression tree, might or might not have a visible effect in code like the above. It would depend on whether the operators involved were re-written to look at the paren count field, and mimic the effect of extra paren nodes even if they aren’t really there any more. There are lots of other possibilities other than having a paren count field, which I haven’t fully explored, like having two expression trees, one that the user can see, and an “optimized” one, without parens, and perhaps with other optimizations, that’s created on the fly the first time an expression is evaluated.

        It’s also possible that eliminating parentheses from user-visible expression trees is just what you would want. They would be just an annoyance for most applications I can think of.

        I’ve also since modified the code for parentheses to be more like the code for curly brackets (this is a two-line change to the code). With this change, parentheses become slightly faster than curly brackets. Using redundant parentheses will still slow down your R program slightly, however.

  • 9. maja  |  2010-08-26 at 12:52 pm

    Funny, I usually get the curly brackets taking longer than the normal parantheses? I did 20 runs of each and get this:

    > mean(curly)
    [1] 1.9265

    > mean(straight)
    [1] 1.9155

    This is with 2.11.1. on ubuntu.

    Reply
  • 10. Radford Neal  |  2010-08-26 at 1:07 pm

    There can be strange variations from one system to another due to arbitrary things like exact addresses of things changing caching behaviour.

    How did you do the 20 runs? All 20 for one, then all 20 for the other? Or interleaved? One effect of parens rather than curlys is more allocation, and hence more garbage collection, but the garbage collection time might be deferred. So better to do all 20 runs of one, then all 20 of the other. Of course, you can then do it all over again just to see if it’s consistent…

    Reply
  • 11. maja  |  2010-08-26 at 1:36 pm

    Well when I did individual 1-1 comparisons curlies came out slower 4 out of 5 times. So I did 20 of each, first one, then the other to produce the above result. I did it again now with 100 and got :

    > mean(curly)
    [1] 1.9115

    > mean(straight)
    [1] 1.9195

    So either way – on this machine at least – I don’t have to worry about changing all my code!

    Reply
  • 12. David Winsemius  |  2010-09-16 at 10:40 am

    I wonder if the testing methods are sufficient for the task of characterizing performance across the range of hardware to be optimized. I get the opposite in R 2.11.1 with x86_64-apple-darwin9.8.0:

    > a <- 5; b <- 1; c f <- function (n) for (i in 1:n) d g <- function (n) for (i in 1:n) d system.time(f(1000000))
    user system elapsed
    5.549 0.075 5.629
    > # user system elapsed
    > # 3.92 0.00 3.94
    > system.time(g(1000000))
    user system elapsed
    5.241 0.021 5.248


    David.

    Reply
  • [...] I replaced all parentheses ( ) by curly brackets { }. I was inspired to do so by this post (and this, via Xi’Ans Og) over at Radford Neal’s blog. As he pointed out, code that uses [...]

    Reply
  • [...] Speeding up parentheses (and lots more) in R: gives some very useful, and sometimes curious tips to speed up your code. [...]

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Calendar

August 2010
M T W T F S S
« Mar   Sep »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Most Recent Posts


Follow

Get every new post delivered to your Inbox.

Join 117 other followers