new linear algebra library and memory management improvement

[François du Vignaud]

Hi all,

 

I have carried out some code profiling on the new LFM implementation. (ratchet cap pricing using 3 factors)  Results showed that about 38% of the computation time was spend for dynamic memory allocation (the disposable trick saves some of them but not all of them, because a time step computation requires 41 dynamic allocations !).  I have removed all these memory operations by passing a reference toward the result instead of returning it eg: 

 

Existing code:  Disposable<Array> LiborForwardModelProcess::drift(Time t, const Array& x)   

My code:     void LiborForwardModelProcess::drift(Time t, const ublas::vector<Real>& x, ublas::vector<Real>& result )

 

This had improved speed by the expected extent with VC++ 2003 but only by 22% with gcc.      The remaining time consuming operations being linear algebra operations, I have also replaced the existing Matrix/Vector implementation by the boost uBlas library. This gave pretty good results, indeed, all operations but matrix*scalar operation are greatly accelerated. I removed these operations by embedding them in procedures as follows:

 

Existing code:      lfmParam_->covariance(result, t, x);        result*=dt;   

My code:      lfmParam_->covariance(result, t, x, dt);  // dt product is done inside

 

Finally the overall gain of speed due to these changes is around 50% with both VC2003 and gcc.    I'm considering to implement these changes for the whole QuantLib, but before doing so I would like to know your opinion on the subject. I do not see any other way to improve memory management, but I'm hesitating between two solutions for the uBlas migration :

Embedding all uBlas code in the existing Array and Matrix classes. The main advantage is that no other file would be altered. However it seems really tedious to expose all the nice features of uBlas using this architecture.

Replacing completely all Array and Matrix in the QuantLib code.

I tend to prefer the second solution because it is much neater in my opinion even if it is not the simplest one in the short run. I'm aware that uBlas is not the most efficient linear algebra library available, however profiling shows that it is sufficient for the LFM case (sheer linera algebra operations accounts for a small part of the computation time). More complex operations can be performed using ATLAS through uBlas bindings.

Any suggestion/advice are more than  welcome.   

 Thanks for your attention,

best regards, 

François

[Luigi Ballabio]

On 06/22/2006 05:07:43 PM, François du Vignaud wrote:
> I'm hesitating between two solutions for the uBlas migration :
> Embedding all uBlas code in the existing Array and Matrix classes.  
> The main advantage is that no other file would be altered. However it
> seems really tedious to expose all the nice features of uBlas using
> this architecture.

Also, it would be hard to expose expression templates and such for the  
Array and Matrix classes if they embed the uBlas ones.


> Replacing completely all Array and Matrix in the QuantLib code.
> I tend to prefer the second solution.

I too prefer this one, but it would be quite a bit of work (especially  
if we want to maintain backward compatibility for one release.) We can  
try and coordinate the effort so that you're not the only one upon  
whose shoulders the task falls. I'll have a look at uBlas so that I can  
have an idea of how this can be accomplished---drop me a line if you  
have already though of this.

Later,
        Luigi


----------------------------------------

Steinbach's Guideline for Systems Programming:
        Never test for an error condition you don't know how to handle.

[Klaus Spanderen]

Hi

I've checked the second solution by defining

typedef boost::numeric::ublas::vector<double> Array;
typedef boost::numeric::ublas::matrix<double> Matrix;

and porting the rest of the QuantLib. (This breaks quite a lot interfaces
within the QL;-). The resulting performance is disappointing. Using normal
compiler switches the ublas version is 20% slower than the original
implementation. When using more aggressive compiler optimization switches the
ublas can only match the original performance but is not faster.

FYI: I got 10% more performance for the test-suite without changing interfaces
by using the slightly improved version of array.hpp and matrix.hpp enclosed
in the attachment (I haven't checked this version too much;-)

cheers
 Klaus

 

On Thursday 22 June 2006 5:07 pm, François du Vignaud wrote:

> Hi all,
>  I'm hesitating between two solutions for the uBlas migration : Embedding
> all uBlas code in the existing Array and Matrix classes. The main advantage
> is that no other file would be altered. However it seems really tedious to
> expose all the nice features of uBlas using this architecture. Replacing
> completely all Array and Matrix in the QuantLib code.
> I tend to prefer the second solution because it is much neater in my
> opinion even if it is not the simplest one in the short run. I'm aware that
> uBlas is not the most efficient linear algebra library available, however
> profiling shows that it is sufficient for the LFM case (sheer linera
> algebra operations accounts for a small part of the computation time). More
> complex operations can be performed using ATLAS through uBlas bindings. Any
> suggestion/advice are more than  welcome.
>  Thanks for your attention,
> best regards,
> François