Performance improvement for spline class

[hol430]

Hi all, we've adapted your approach for using splines to interpolate water potential from transpiration and vice versa in the lpj-guess dave model. This has been an excellent optimisation for us, so thanks for sharing the approach! One thing that we noticed however, was that a lot of time was spent in std::lower_bound() as called from spline::operator (). This is called a lot in our model, and 20% of the total runtime was spent inside this particular call to std::lower_bound().

What's happening here is we're searching through the x-values to find a start point for the interpolation. std::lower_bound() is doing a binary search internally, so it's reasonably efficient, but what we did to try and speed things up was to do a one-time check (when we initialise the spline object) to check if the x-values are equally-spaced. If they are, then we can eliminate the call to std::lower_bound() at time-of-interpolation by looking at our x value relative to the full range of x values (ie (x - xmin) / (xmax - xmin)). We then multiply that by the number of x-values and floor() the result, and end up with something comparable to the output of std::lower_bound() in significantly less time than it would have otherwise taken.

After doing that (and ensuring we chose equidistant x-values), we managed to speed up our simulations by 18%, so I thought I'd share our findings here in case it's of use to you guys. I get that your model works differently, so if this is not really an issue for you guys (e.g. if this code is not called so often), then feel free to close this issue :).

Edit: didn't mean to label this as a bug, but I couldn't see a better category.