Fourteen patches to speed up R
2010-09-03 at 4:12 pm 19 comments
Following my discovery of two surprising inefficiencies in R, I’ve been inspired to spend much of the last two weeks looking for ways to speed it up. I’ve had quite a bit of success, both at finding ways to speed up particular functions, and at finding ways to reduce general interpretive overhead.
You can get my fourteen patches to the R source code here. I’d be interested in hearing how much it speeds up typical applications, on various machines. Of course, you need to be comfortable with installing R from source code to use these patches. For meaningful speed comparisons, you also need to be sure to compile the modified and unmodified versions of R with the same compiler, same options, etc.
There look to be some more places in the R source code where speed improvements are possible, but for now, I had better switch to preparing for the coming teaching term…
UPDATE: I discovered a bug in the vec-subset patch. The version you can get from here now has this fixed. I also split the vec-subset patch into patch-vec-subset and patch-subscript, since these two parts are really independent. So there are now fifteen patches.
Entry filed under: Computing, R Programming, Statistics, Statistics - Computing.
19 Comments Add your own
Leave a reply to Readability vs speed in R Cancel reply
Trackback this post | Subscribe to the comments via RSS Feed
Radford Neal's blog 
1. M. Edward (Ed) Borasky | 2010-09-04 at 3:15 am
A few years back I put together some infrastructure for profiling the Ruby interpreter using gprof and later oprofile on Linux. I’ve been thinking about digging up the oprofile version and running it against R. What sort of “inner interpreter” benchmarks do you have?
There’s a full test suite built into the R source distribution – it wouldn’t take much to validate these patches except some spare hardware. In fact, maybe the test suite could be the benchmark. ;-)
If you want, I’ll resurrect the framework (it’s in Ruby) and port it to openSUSE (I was on Gentoo when I built it).
2. Radford Neal | 2010-09-04 at 12:33 pm
The mods pass “make check” with R 2.11.1. With development revision 52822 “make check” doesn’t work even without the mods, so I can’t use it.
I doubt that “make check” would be suitable as a timing test. They presumably do everything on small matrices, etc. to make the check faster, but that doesn’t test time on big matrices. It may be dominated by the time to print the results. Of course, it’s very hard to tell what a good timing benchmark is, since R can be (and is) used in so many different ways.
I haven’t actually tried profiling the R intepreter – there are so many places that are obviously time-critical where speed improvements seem possible. But at some point that could indeed be very useful.
3. stewart | 2010-09-04 at 9:21 am
Taking about timing, I just built a fresh Ubuntu box(10.04) for R…I tried to apply your patches but got a lot of complaints from ‘patch’ which is 2.6. I am sending you the log file from running your shell script. Oh my R is a fresh download 2.11.1.
4. Radford Neal | 2010-09-04 at 12:37 pm
I emailed with Stewart about this, and he now reports that the problem was running apply-patches in the “src” directory. My instructions maybe weren’t too clear on this – it should actually be run in the top-level directory created from the tar file downloaded from r-project.org.
To help anyone else with problems, the web page with the patches now also has the output when I apply them to 2.11.1, which may help identitying problems with “patch”.
5. stewart | 2010-09-04 at 1:48 pm
My testing results with your test suite are in line with yours: there are significant speed gains with your patches. With my own program which is a gibbs sampler for a DP mixture model, I see around 3% improvement in time, which is sort of expected since most of the time are spent in looping(C code) and matrix operation. Thanks for all your excellent work!
6. Radford Neal | 2010-09-04 at 1:55 pm
Thanks for sending me the results. From the output files you emailed me, it seems the gains are a bit larger (proportionately) than with the machine/compiler I used.
Do you have a prototype version of your Gibbs sampler program written entirely in R? If so, I’d be interested in how much the patches speed that up. One reason to try to speed up R is to make it fast enough that people don’t feel compelled to rewrite crucial bits in C.
7. stewart | 2010-09-04 at 6:57 pm
Yes the GS is written in R. I will redo my tests without calling the C functions and report the results here.
8. stewart | 2010-09-04 at 7:53 pm
I redid my tests without calling C code: I see around 10% improvement in overall time for my GS. The gains are pretty much across the board, but I do notice that for matrix operator “%*%” the gain is big: it cuts the time by 1/3,that looks like a huge deal to me! I am sending you the Rprof results FYI.
9. ROW | 2010-09-04 at 9:31 am
Will these patches be included in the next R release?
10. Radford Neal | 2010-09-04 at 10:31 am
I’ve posted them on the R-devel mailing list. It will be up to the R developers whether to put them in. They’d obviously want to look at them and test them before deciding.
11. In{s}a(ne)!! « Xi'an's Og | 2010-09-05 at 6:08 pm
[…] the latest of his posts, Radford lists a series of 14 patches that speed up R up to 25%… That R can face […]
12. Mike Lawrence | 2010-09-08 at 9:09 pm
Interesting. I tested my machine (unibody macbook, 2.4 GHz Intel C2D, 4GB RAM, OS 10.6.3) on R 11.1 binary provided by CRAN, then downloaded 11.1’s source, patched, and built (annoyingly had to upgrade my gfortran to 2.4.4 in order to build, but this was the case with the unpatched source too [I checked]). The speed tests all seemed better for the patched version *except* the matprod tests:
CRAN binary:
2.916, 1.488, 1.12, 1.497, 2.491, 3.752, 4.111
Patched:
1.309, 1.42, 1.592, 1.271, 3.997, 6.303, 8.777
I actually ran the test on the CRAN binary twice (once before and after shutting down other apps), so even though the timings look weird (non-monotonic), they came out roughly the same across both runs.
13. Mike Lawrence | 2010-09-08 at 9:16 pm
oops, make that OS 10.6.4, and gfortran-42-5664
14. Radford Neal | 2010-09-08 at 11:45 pm
The patch to matrix product is the one with the most peculiar effects. On SPARC machines it makes thinkgs much slower, because when the matrix product is done in the R matprod procedure, it accumulates sums in “long double” form, which is extraordinarily slow on our SPARC machine. Maybe something like that is happening on your machine. But are you sure the CRAN version used the same compiler (and options) as you did for the patched version? If not, the comparision would be less informative.
The matrix product patch can also potentially change the answer, since roundoff error is not necessarily the same as for the BLAS routine. This makes checking the results of the R test suite difficult.
The matrix product patch’s motivation is that R doesn’t trust NA treatment by the BLAS routines, and so spends time checking for them, which can be avoided if it instead just does the product itself. It’s not clear to me that this check is desirable, and if its not, the patch would instead be to just delete this check.
15. Filip | 2010-10-03 at 1:20 pm
Dear, thank You for the patches, I have observed a speed-ups of up to 50% on my Intel Core 2 Duo, 2 Ghz, 4GiB RAM machine. I think I have found a bug though, as this code (and similar ones, everything including geom_bar in ggplot2 package) :
library(ggplot2)
a = 3
b = 7
s = 10
f = 11
ps = rbeta(1000, a + s, b + f)
qplot(ps,..density.., geom=”histogram”, binwidth = 0.01)
Returns:
“Error in if (empty(data)) return(data.frame()) : missing value where TRUE/FALSE needed”
While running smoothly on vanilla R.
16. Radford Neal | 2010-10-05 at 4:03 pm
Hi. I’ve just gotten time to look at this now. I can reproduce the problem you report, so there’s presumably a bug somewhere in one of my patches. I’ll investigate further…
17. Radford Neal | 2010-10-05 at 5:18 pm
I’ve narrowed the bug Filip found down to something in patch-dollar. More once I find what it actually is…
18. Radford Neal | 2010-10-15 at 12:19 am
I’ve now found out what causes the bug. It’s a problem with the internal DispatchOrEval function, which I didn’t modify, but which my patch-dollar code uses in a different way than the $ operator did previously. This problem with DispatchOrEval causes other (rather obscure) bugs in other R primitives (eg, xtfrm). I’ll soon report the bug, with a fix.
R version 2.12.0 is due to be released shortly. I’ll be putting out versions of my patches (except the ones that have been incorporated into 2.12.0) for it. I think it isn’t worth while putting out a fixed patch-dollar for R 2.11.1.
The symptom that arises in ggplot2 is that, with my patch-dollar, a method for $ that deparses the first argument will not work correctly.
19. Readability vs speed in R | 2011-02-19 at 8:12 am
[…] why you are referred to his article. He also found a interesting observation about squares. In a further article he presents some patches to speed up […]