Templates

Posted by Luigi Ballabio-3 on Dec 19, 2000; 3:50pm
URL: http://quantlib.414.s1.nabble.com/Re-Quantlib-dev-Linux-Port-tp1617p1618.html

At 07:18 PM 12/18/00 +0100, Ferdinando Ametrano wrote:
>>Initial impressions:
>>
>>         I am unhappy about the heavy use of templates and the stl. Its
>> going to bite you on many platforms (guys there is a whole world out
>> there apart from Macs and Windows machines...) and the bloat is going to
>> be considerable.
>Luigi will reply to this one.

Here I am. Of course you're right about compiler support (we already had
quite a few headaches because of this) and about the bloat. I am also aware
that, as Peter Schmitteckert wrote,

>for a library, I prefer virtual classes/functions to achieve conveniency
>and flexibility. You can extend classes with virtual function, withouot
>recompiling or changing the interface. With templates you can't (normally) not.
>...and remember, virtual fuctions are just a pointer-derefencation, and
>that's cheap on microprocessors.

Well, I'll try and explain the reasoning behind the current template
implementation, of which-I think-the finite difference package is the most
blatant example. (P.S. Sorry - it turned out to be a long e-mail, but I
wanted to put all my cards on the table so that we can continue discussing
the issue with the complete picture in mind)

First and foremost, the virtual classes approach is one that we definitely
want to pursue - expecially as we are exporting the library towards Python
(and hopefully other languages) where we cannot exploit the C++ template
mechanism.
In short, I surely want to be able to use dynamic polymorphism to switch
between FiniteDifferenceModel<CrankNicolson<TridiagonalOperator> >,
FiniteDifferenceModel<BackwardEuler<MultigridOperator> >,
FiniteDifferenceModel<MyVerySpecificPadeApproximation>,
FiniteDifferenceModel<WhateverYouLike>, and even TreeModel<WhateverItNeeds>.
This can be (more or less) easily accomplished by inheriting template<class
Evolver> FiniteDifferenceModel<Evolver> from some more generic interface
class. However, this is a part of the global design that didn't make into
the library yet. We just uploaded the inner part of it.

At the same time, while very flexible with respect to usability by the
final user, dynamic polymorphism is somehow less flexible with respect to
developing new classes - because it forces such classes to belong to a
particular hierarchy. I see two main disadvantages of this approach:
1) multiple inheritance rears its ugly head, which I would avoid if
possible. This is very likely to be a only a prejudice of mine - so feel
free to ignore it - but it is getting much too close to virtual base
classes for my liking.
2) if you decide that, e.g., some sparse array class you found in another
library would be just right for your particular problem, you'll have to either:
   a) modify that class so that it inherits from the base class for arrays
in our brand new polymorhpic framework, which is not always possible, or
   b) write a wrapper class which contains the sparse array and inherit
from the base one.
In a template framework, you can just go ahead and write your differential
operator using the sparse array class as it is, and its full compatibility
with the framework is just a trait specialization away.

Furthermore, if different array classes - possibly including sparse ones -
or different operator classes  - tridiagonal, band diagonal, sparse, you
name it - are to be derived from base classes, then it is very likely that
we will have to declare as virtual even very basic functionalities (i.e.,
operator[]) which tend to get in the innermost loops of the code and get
called humongous number of times. Now, while it is true that virtual calls
are cheap nowadays, it is also true that precious few optimizers inline
them. A simple algorithm for multiplying a matrix and a vector would either:
a) be written in a generic way, in which case it would jump in and out the
respective operator[] for most of the time, which will add up to quite a
loss in efficiency, or
b) be specialized for the concrete operators and array - however, this
would need double dispatching, which is not easier to write and maintain
than templates.

Finally, there's still one thing that static polymorphism can do and
dynamic polymorphism can't, and that's generic algorithms on iterators. You
simply can't derive all iterators from a single class as Java does, because
you can't add a parent class to C pointers. But I don't think you need to
hear this from me :)

Well, I'm open to suggestions. In short, my point was: I'd like to be able
to use templates in the inner parts of the models - arrays, operators... -
for the kind of flexibility I explained above. I'd also like to use dynamic
polymorphism in the outer parts - the complete models and their interface -
for the kind of flexibility users, including myself, want.
Once the design is refined, we could have the best of both worlds - and of
course a bit of the worst of both, compiler support included :) But it is a
trade-off that I would personally accept.

Thanks for listening (man, was this long!)

                 Luigi