Array vs std::vector + free operators

[DU VIGNAUD DE VILLEFORT FRANCOIS GASAPRD PHI]

Hi all,

 

 

I have tried to removing the dependency on Array class from the optimization framework. One change leading to another it turns out that Arrray dependencies could be removed in the whole QL ! The only change I had to do was to provide missing operators an independent header file and all worked fine. As a result I’m wondering if using plain std::vector instead of Arrray wouldn’t be more efficient in terms of compilation efficiency and flexibility of use. (if one want to use linear algebra he has just to include a file defining new operators…). I haven’t done serious tests but I don’t think that it would cause any performance loss since std::vector is a sequential container and is “swapable” in constant time. On the other hand it would make the array implementation more transparent to the user thus much more difficult to replace if one want to provide another implementation (but is it likely to happen ?)

Any thought ?

François

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

[Luigi Ballabio]

On Thu, 2007-04-19 at 15:47 +0200, DU VIGNAUD DE VILLEFORT FRANCOIS
GASAPRD PHI wrote:
> I have tried to removing the dependency on Array class from the
> optimization framework. One change leading to another it turns out
> that Arrray dependencies could be removed in the whole QL !
> The only change I had to do was to provide missing operators an
> independent header file and all worked fine. As a result I’m wondering
> if using plain std::vector instead of Arrray wouldn’t be more
> efficient in terms of compilation efficiency and flexibility of use.
> (if one want to use linear algebra he has just to include a file
> defining new operators…).

François,
        it doesn't sound right to me, for a couple of reasons:

- you're changing the std::vector interface by adding operators. I'm not
sure that it is legal C++.  Moreover, this might be done without the
user knowing it if he happens to include a file which in turn includes
your new operators. Thus, code which according to the C++ standard is
not valid (such as w = u+v if u,v,and w are std::vectors) would silently
become legal. I'm not comfortable with this.

- there's a conceptual difference between the two classes, and using
std::vector for both would confuse the issue. std::vector is a
container; Array is the linear-algebra concept of an array. I, too, had
been thinking of replacing Array with an STL class, but the right one
would be std::valarray---which models the right concept and already
defines the required operators.

Later,
        Luigi


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

If you can't convince them, confuse them.
-- Harry S. Truman



-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

[DU VIGNAUD DE VILLEFORT FRANCOIS GASAPRD PHI]

François,
        it doesn't sound right to me, for a couple of reasons:

>- you're changing the std::vector interface by adding operators. I'm not
>sure that it is legal C++.  Moreover, this might be done without the
>user knowing it if he happens to include a file which in turn includes
>your new operators. Thus, code which according to the C++ standard is
>not valid (such as w = u+v if u,v,and w are std::vectors) would silently
>become legal. I'm not comfortable with this.

We could provide only specialized templates implementation. (for double, even if it some of them might also make sense with other data like Date,...) Anyway I'm pretty sure that any decent compiler would squeal if the corresponding elementwise operation doesn't exist.

>- there's a conceptual difference between the two classes, and using
>std::vector for both would confuse the issue. std::vector is a
>container; Array is the linear-algebra concept of an array. I, too, had
>been thinking of replacing Array with an STL class, but the right one
>would be std::valarray---which models the right concept and already
>defines the required operators.

I agree with you that a general purpose container and an Array are two different beasts. About the valarray Josuttis doesn't seem to be a great fan:
"At the time of this writing, no such implementation is known, and standard valarrays are, generally speaking, quite inefficient at performing the operations for which they were designed." (C++ templates: The complete guide)

Maybe they have improved it since ... :-)

Rgds,
François

PS: here is an example of the operators I have defined:

inline const Disposable<std::vector<Real> > operator+(const std::vector<Real>& v1, const std::vector<Real>& v2) {
        QL_REQUIRE(v1.size() == v2.size(),
                   " vectors with different sizes (" << v1.size() << ", "
                   << v2.size() << ") cannot be added");
        std::vector<Real> result(v1.size());
        std::transform(v1.begin(),v1.end(),v2.begin(),result.begin(),
                       std::plus<Real>());
        return result;
    }

PPS: I don't want to be pushy about this. It is just an idea I'm playing with.

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

[Luigi Ballabio]

On Thu, 2007-04-19 at 17:11 +0200, DU VIGNAUD DE VILLEFORT FRANCOIS
GASAPRD PHI wrote:
> >- you're changing the std::vector interface by adding operators. I'm not
> >sure that it is legal C++.  Moreover, this might be done without the
> >user knowing it if he happens to include a file which in turn includes
> >your new operators. Thus, code which according to the C++ standard is
> >not valid (such as w = u+v if u,v,and w are std::vectors) would silently
> >become legal. I'm not comfortable with this.
>
> We could provide only specialized templates implementation. (for double, even if it some of them might also make sense with other data like Date,...) Anyway I'm pretty sure that any decent compiler would squeal if the corresponding elementwise operation doesn't exist.

You would still be changing the interface of that particular
specialization of std::vector. The problem remains. I'm not referring to
the possibility of adding vectors of non-numeric types; the compiler
would reject that. I'm saying that the C++ standard states that w = u+v
doesn't work with std::vector, and you're making it work.


> I agree with you that a general purpose container and an Array are two different beasts. About the valarray Josuttis doesn't seem to be a great fan:
> "At the time of this writing, no such implementation is known, and standard valarrays are, generally speaking, quite inefficient at performing the operations for which they were designed." (C++ templates: The complete guide)
>
> Maybe they have improved it since ... :-)

Maybe. Or maybe we could implement Array _in terms of_ std::vector. But
there should be no conceptual confusion between the two.

> PS: here is an example of the operators I have defined:
>
> inline const Disposable<std::vector<Real> > operator+(const std::vector<Real>& v1, const std::vector<Real>& v2) {
>         QL_REQUIRE(v1.size() == v2.size(),
>                    " vectors with different sizes (" << v1.size() << ", "
>                    << v2.size() << ") cannot be added");
>         std::vector<Real> result(v1.size());
>         std::transform(v1.begin(),v1.end(),v2.begin(),result.begin(),
>                        std::plus<Real>());
>         return result;
>     }

Apart from adding operations to std::vector, the above is not as
efficient as Array:operator+. if you write

std::vector<Real> w = u+w;

the addition returns a Disposable, but the std::vector constructor
doesn't know what to do with it, so it copies its contents instead of
swapping. If you want full efficiency, you have to write:

std::vector<Real> w;
w.swap(u+v);

which is more awkward. On the other hand, Array defines a constructor
taking a Disposable, so there's no moving in

Array w = u+v;


> PPS: I don't want to be pushy about this. It is just an idea I'm playing with.

Same here.

Later,
        Luigi


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

Quote me as saying I was misquoted.
-- Groucho Marx



-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

[DU VIGNAUD DE VILLEFORT FRANCOIS GASAPRD PHI]

>Apart from adding operations to std::vector, the above is not as
>efficient as Array:operator+. if you write

>std::vector<Real> w = u+w;

>the addition returns a Disposable, but the std::vector constructor
>doesn't know what to do with it, so it copies its contents instead of
>swapping. If you want full efficiency, you have to write:

>std::vector<Real> w;
>w.swap(u+v);

>which is more awkward. On the other hand, Array defines a constructor
>taking a Disposable, so there's no moving in

>Array w = u+v;

I badly missed this point, I will slap myself with bjarne's book ;-)

François

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

[Luigi Ballabio]

On Thu, 2007-04-19 at 18:52 +0200, DU VIGNAUD DE VILLEFORT FRANCOIS
GASAPRD PHI wrote:
> I badly missed this point, I will slap myself with bjarne's book ;-)

I doubt it's an effective way to transfer its contents to one's brain :)

Luigi


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

fix, n.,v.
What one does when a problem has been reported too many times
to be ignored.
-- the Jargon file



-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev