search

dkahle / mpoly

Symbolic computing with multivariate polynomials in R
https://dkahle.github.io/mpoly/
12 stars 12 forks source link

Speedup with c++ using Rcpp #11

Open Blaza opened 6 years ago

Blaza commented 6 years ago

Have you thought about implementing (the bulk of) the code using Rcpp (nice intro here)? As that's C++ code, it would be quite faster than the current implementation.

In my fork of the repo I rewrote the mpoly function, the main workhorse, and some mpoly arithmetic functions (* and ^) using Rcpp. The code basically follows your algorithm almost exactly, just in C++. It is relatively straightforward to implement the current code (at least the mpoly function and arithmetic) in Rcpp, and the speed gains are 4-5 fold.

I made a quick benchmark, which you can see here. The implementation is quite straightforward, so there may well be room for more optimization, as I'm not really an expert C++ coder.

I am making a package which would make use of (multivariate) Lagrange polynomial, so I'm using mpoly to generate the polynomial (the reduced polynomial that mpoly gives is easy to vectorize to give quick evaluation), and the number of collocation points, and thus the degree of the poly, can get quite high, so the speed of generation of the polynomial (the mpoly function being the main workhorse) is very important to me, so that brought me to try and implement it in Rcpp and the results have been satisfying for now.

I'd love to hear what you have to say and where we could go from here. Maybe the package could go the Rcpp route (I don't know if you'd like to add another dependency?). Or perhaps I may, in parallel, work on the, let's say, "Rcppmpoly" package which focuses a bit more on speed?

Sorry for the long post :)

dkahle commented 6 years ago

Have you thought about implementing (the bulk of) the code using Rcpp (nice intro here)?

Yes! I just haven't gotten around to it. But absolutely yes, mpoly badly needs it. I think it's the right way to go, in mpoly, and the dependency is no problem.

In my fork of the repo I rewrote the mpoly function, the main workhorse, and some mpoly arithmetic functions (* and ^) using Rcpp. The code basically follows your algorithm almost exactly, just in C++. It is relatively straightforward to implement the current code (at least the mpoly function and arithmetic) in Rcpp, and the speed gains are 4-5 fold.

This is great, please submit a PR and I'll look more.

As you've correctly identified, mpoly() and related arithmetic functions are bottlenecks that can be greatly improved with Rcpp. I think another important bottleneck is the parser, mp(), which is currently ridiculously slow. I think it'd be much better to program a parser based on a tokenizer at the C++ level. If you're interested in working on that, please let me know!

Blaza commented 6 years ago

Well, I haven't looked at mp as I didn't really need it, the current version was enough for me. I may look into it some time later, but I don't know when that would be, as I don't have plenty of time to look into it in detail. The mpoly and arithmetic part I needed for my work, so I thought I would contribute to the project, as I was already making the modifications.

I created the pull request with the Rcpp implementation. Again, there may be more room for enhancement of the C code itself, as I'm relatively new to cpp.

RobinHankin commented 6 years ago

hello guys, not sure of the etiquette here; I'm new to github. I've written a bare-bones R package, skimpy, which uses the the STL map class (actually it uses it twice, once for the variables in a single term, and once for the terms itself). It is at

https://github.com/RobinHankin/skimpy.git

and it's considerably faster than both multipol and spray. But I've not written a print method (mpoly's print method is wonderful) How to proceed? Robin