QuantLib › quantlib-users

Performance question

Classic

List

Threaded

9 messages Options

Christopher Targett-Adams

Performance question

Dear Quantlib users/developers,

I have a question related to the performance of some of the QL classes. I am currently looking at developing a system using the QL framework and have been doing some feasibility studies using some of the yield curve and interpolation classes. I set the following test up:

1) I performed 130000 linear interpolations using the InterpolatedCurve<Linear> class. Basically, I define an x and y std::vector<double> which are 13 elements long and then I have a for loop which performs 130000 iterations and calls the relevant interpolation method on each iteration. It's very simple.
2) I then compare this to a classic procedural implementation of linear interpolation, ie a function that just takes in two double[13] arrays, does a bisection search and then does a linear interpolation between the located grid points. Again, very simple stuff.

I am by no means trying to claim I'm comparing like with like and I expect QL to be a bit slower than procedural c++, however, the QL interpolation is very slow: the 130000 interpolations takes about 4 seconds compared to 0.4 seconds for the procedural implementation.That's 100 times slower! What's more perplexing is even when I take out the error checking and hack the locate method so that it just returns 0 (thus elimating any time spent in the grid seach) it still takes the same order of magnitude to run. There's a lot going on in the code with smart pointer use, std::vectors, iterators, templates, inheritance, polymorphism and my under-the-bonnet knowledge of c++ isn't good enough to allow me to understand why it's taking so long.

Does anyone know what the cause of the poor performance is?

Chris

------------------------------------------------------------------------------
Got Input? Slashdot Needs You.
Take our quick survey online. Come on, we don't ask for help often.
Plus, you'll get a chance to win $100 to spend on ThinkGeek.
http://p.sf.net/sfu/slashdot-survey
_______________________________________________
QuantLib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Christopher Targett-Adams

Re: Performance question

Apolgies, I meant 4s vs 0.04s

Chris

From: [hidden email]
To: [hidden email]
Subject: Performance question
Date: Sun, 31 Jul 2011 22:05:08 +0100

Bojan Nikolic

Re: Performance question

In reply to this post by Christopher Targett-Adams

Are you sure you're not recreating the curve at every iteration? You
should be able to get 10s millions interpolations per second from
quantlib when you are correctly re-using the curve.

Best,
Bojan

--
Bojan Nikolic || http://www.bnikolic.co.uk

------------------------------------------------------------------------------
Got Input? Slashdot Needs You.
Take our quick survey online. Come on, we don't ask for help often.
Plus, you'll get a chance to win $100 to spend on ThinkGeek.
http://p.sf.net/sfu/slashdot-survey
_______________________________________________
QuantLib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Slava Mazur-2

Re: Performance question

In reply to this post by Christopher Targett-Adams

Perhaps this is because the interpolation implementation classes perform binary search to locate the position of every x argument. If you call it thousands of times there will be thousands binary searches. In my applications I use interpolation objects as temporal constructs to calculate all the required values once and store them in a container with a more efficient access.

Also, I’d like to take this opportunity to point out that there is a potential danger in the design of interpolation objects – they take iterators as input during construction. This is an additional argument in favor of use of interpolation object as a temporal one. Hope this helps.

Cheers,

Slava Mazur

From: Christopher Targett-Adams [mailto:[hidden email]]
Sent: Sunday, July 31, 2011 5:05 PM
To: [hidden email]
Subject: [Quantlib-users] Performance question

------------------------------------------------------------------------------
BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
The must-attend event for mobile developers. Connect with experts.
Get tools for creating Super Apps. See the latest technologies.
Sessions, hands-on labs, demos & much more. Register early & save!
http://p.sf.net/sfu/rim-blackberry-1
_______________________________________________
QuantLib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Ferdinando M. Ametrano-3

Re: Performance question

Hi all

On Tue, Aug 2, 2011 at 10:59 PM, Slava Mazur <[hidden email]> wrote:
> Perhaps this is because the interpolation implementation classes perform
> binary search to locate the position of every x argument. If you call it
> thousands of times there will be thousands binary searches.
for me it's hard to believe that bisection might be an efficiency
bottleneck in a real-world financial usage of linear interpolation...
It could be improved (e.g. caching the bracketing result as guess for
the next one)

> Also, I’d like to take this opportunity to point out that there is a
> potential danger in the design of interpolation objects – they take
> iterators as input during construction. This is an additional argument in
> favor of use of interpolation object as a temporal one.

you're right: interpolations are meant to be contained inside some
other object which guarantees persistence of the X and Y vectors to be
interpolated. An example of such a container is
QuantLibAddin::Interpolation, which also implement the (lazy)
observability of the QuantLib::Quote vector used as Y vector.
I personally advocate moving QuantLibAddin::Interpolation in QuantLib,
but if I'm not wrong Luigi is skeptical

ciao -- Nando

------------------------------------------------------------------------------
BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
The must-attend event for mobile developers. Connect with experts.
Get tools for creating Super Apps. See the latest technologies.
Sessions, hands-on labs, demos & much more. Register early & save!
http://p.sf.net/sfu/rim-blackberry-1
_______________________________________________
QuantLib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Ferdinando M. Ametrano-3

Re: Performance question

In reply to this post by Bojan Nikolic

Hi Christopher and all

On Mon, Aug 1, 2011 at 9:19 AM, Bojan Nikolic <[hidden email]> wrote:
> Are you sure you're not recreating the curve at every iteration? You
> should be able to get 10s millions interpolations per second from
> quantlib when you are correctly re-using the curve.

just to stress that I agree 200% with Bojan. If you experience such a
slowness you're probably uselessly recreating the interpolation
objects.

Please let us know if this is the case.

ciao -- Nando

------------------------------------------------------------------------------
BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
The must-attend event for mobile developers. Connect with experts.
Get tools for creating Super Apps. See the latest technologies.
Sessions, hands-on labs, demos & much more. Register early & save!
http://p.sf.net/sfu/rim-blackberry-1
_______________________________________________
QuantLib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Slava Mazur-2

Re: Performance question

In reply to this post by Ferdinando M. Ametrano-3

Hi Nando,

> for me it's hard to believe that bisection might be an efficiency bottleneck in a real-world financial usage of linear interpolation...
This is primarily because QuantLib is not meant to be used on intra-day time scales.
In my quite "real-world financial usage" I tried to use QuantLib for estimation of an intra-day volatility.
Originally I stored an intra-day volatility pattern in a LinearInterpolation object.
Soon, however, it's become apparent that querying it say every second for the whole universe of US stocks presents a real performance bottleneck for both real time and back-testing apps.

> It could be improved (e.g. caching the bracketing result as guess for the next one)
One of the pros of the current design is that the object is stateless. Introducing a state might present unnecessary complexity to deal with in multi-threading environment.
What I would suggest is to keep the stateless paradigm intact and introduce a new, an iterator-like object (e.g. LinearInterpolationItertor) on top of it.
Unfortunately at the moment I don't have time to code it.

Thanks,

Slava Mazur

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Ferdinando Ametrano
Sent: Thursday, August 04, 2011 5:30 AM
To: Slava Mazur
Cc: [hidden email]
Subject: Re: [Quantlib-users] Performance question

Hi all

On Tue, Aug 2, 2011 at 10:59 PM, Slava Mazur <[hidden email]> wrote:
> Perhaps this is because the interpolation implementation classes
> perform binary search to locate the position of every x argument. If
> you call it thousands of times there will be thousands binary searches.
for me it's hard to believe that bisection might be an efficiency bottleneck in a real-world financial usage of linear interpolation...
It could be improved (e.g. caching the bracketing result as guess for the next one)

> Also, I'd like to take this opportunity to point out that there is a
> potential danger in the design of interpolation objects - they take
> iterators as input during construction. This is an additional argument
> in favor of use of interpolation object as a temporal one.

you're right: interpolations are meant to be contained inside some other object which guarantees persistence of the X and Y vectors to be interpolated. An example of such a container is QuantLibAddin::Interpolation, which also implement the (lazy) observability of the QuantLib::Quote vector used as Y vector.
I personally advocate moving QuantLibAddin::Interpolation in QuantLib, but if I'm not wrong Luigi is skeptical

ciao -- Nando

------------------------------------------------------------------------------
BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
The must-attend event for mobile developers. Connect with experts.
Get tools for creating Super Apps. See the latest technologies.
Sessions, hands-on labs, demos & much more. Register early & save!
http://p.sf.net/sfu/rim-blackberry-1
_______________________________________________
QuantLib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Christopher Targett-Adams

Re: Performance question

In reply to this post by Ferdinando M. Ametrano-3

Dear all,

Thanks for your responses. It turns out that the root of my problem was actually compiling my .exe in debug mode (using VS). When I compiled in release mode it was x250 quicker and was doing the 13M interpolations in under a second. Which is good. I know there were some additional checks been done in debug mode but I thought I'd diabled them all manually.

I managed to add some of my own interpolation methods into the framework and was impressed with how easy and elegant it was. However, today I've been working on a problem that involves interpolating a curve that is growing by one tenor at a time during a bootstrapping process. For arguments sake lets say it starts of with 10 tenors, I then do a few cubic spline interpolations, add another point (11 in total now), do another few interpolations, add another point, etc etc I tried to incorporate it into the QuantLib interpolation framework but ran into trouble because I couldn't see a way to update the interators in the base interpolation class.

What are people's thoughts on the most elegant solution for this kind of problem?

Cheers,
Chris

> From: [hidden email]

> Date: Thu, 4 Aug 2011 11:34:48 +0200
> Subject: Re: [Quantlib-users] Performance question
> To: [hidden email]
> CC: [hidden email]; [hidden email]
>
> Hi Christopher and all
>
> On Mon, Aug 1, 2011 at 9:19 AM, Bojan Nikolic <[hidden email]> wrote:
> > Are you sure you're not recreating the curve at every iteration? You
> > should be able to get 10s millions interpolations per second from
> > quantlib when you are correctly re-using the curve.
>
> just to stress that I agree 200% with Bojan. If you experience such a
> slowness you're probably uselessly recreating the interpolation
> objects.
>
> Please let us know if this is the case.
>
> ciao -- Nando

Luigi Ballabio

Re: Performance question

On Thu, 2011-08-04 at 20:48 +0100, Christopher Targett-Adams wrote:
> today I've been working on a problem that involves interpolating a
> curve that is growing by one tenor at a time during a bootstrapping
> process. For arguments sake lets say it starts of with 10 tenors, I
> then do a few cubic spline interpolations, add another point (11 in
> total now), do another few interpolations, add another point, etc etc
> I tried to incorporate it into the QuantLib interpolation framework
> but ran into trouble because I couldn't see a way to update the
> interators in the base interpolation class.

In the bootstrapping algorithm in the library, we recreate the
interpolation. See <ql/termstructures/iterativebootstrap.hpp>.

Luigi

--

I hate quotations.
-- Ralph Waldo Emerson

------------------------------------------------------------------------------
BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
The must-attend event for mobile developers. Connect with experts.
Get tools for creating Super Apps. See the latest technologies.
Sessions, hands-on labs, demos & much more. Register early & save!
http://p.sf.net/sfu/rim-blackberry-1
_______________________________________________
QuantLib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users