[lmi] overview of C++ expression template libraries

[Vadim Zeitlin]

 Hello,

 Below is my overview of the existing C++ expression template libraries
suitable for use in lmi to perform vector computations (and, in some
cases, much more). I won't explain what the expression templates are nor
why do we want to use them because I think that everybody here already
knows it but to refresh one's memory here is an easy to read but
informative article by one of the pioneers of expression templates in C++:

 http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html

In particular the article claims that:

        This technique can also be used to evaluate vector and matrix
        expressions in a single pass without temporaries. In preliminary
        benchmark results, one compiler evaluates vector expressions at
        95-99.5% efficiency of hand-coded C using this technique (for long
        vectors). The speed is 2-15 times that of a conventional C++ vector
        class.

to which I'd like to add that using this technique also results in concice
and clear source code which is another important advantage. To finish this
introduction, a historical note: I was surprized to learn from this article
that apparently this idea appeared 40 years ago as something similar was
known as "Jensen's Device" in ALGOL 60 (1967).



 Web search found the following candidate libraries (in no particular
order):

1. Blitz++
2. MET (Matrix Expression Templates)
3. PETE (Portable Expression Template Engine)
4. POOMA (Parallel Object-Oriented Methods and Applications)
5. GET (Generic expression templates)
6. FC++ (Functional Programming in C++)
7. uBLAS (? Basic Linear Algebra Subprograms)
8. boost::mpl (Meta Programming Library)
9. MTL (Matrix Template Library)


 General information:

        Docs    Licence URL
----------------------------------------------------------------------------
Blitz++ good+   GPL     http://oonumerics.org/blitz/
MET     poor    GPL     http://met.sourceforge.net/
PETE    poor    ???     http://acts.nersc.gov/pete/
POOMA   good-   GPL     http://www.nongnu.org/freepooma/
GET     poor    PD      http://www.codeproject.com/cpp/expressiontemplates.asp
FC++    good    BSD(?)  http://www.cc.gatech.edu/%7Eyannis/fc++/
uBLAS   good+   Boost   http://www.boost.org/libs/numeric/ublas/doc/
mpl     good    Boost   http://www.boost.org/libs/mpl/doc/
MTL     good+   Art.    http://www.osl.iu.edu/research/mtl/


 Activity/popularity:

        Last release    Web update      ML activity     Google  Debian
----------------------------------------------------------------------------
Blitz++ Nov 2004        Jun 2005        medium low      33000   Y
MET     Feb 2001                        none                ?   N
PETE    ?                               none              500   N
POOMA   Dec 2004        Feb 2005        very low         6300   N       
GET     Jan 2005                        none                1   N
FC++    Aug 2003        Sep 2003        unaccessible      700   N
uBLAS   Jul 2005            2002(?)                     25000   Y
mpl     Nov 2004                                        90000   Y
MTL     Jul 2005        Jul 2005        unaccessible     9260   N


We can forget "GET" which is just an example of the code which could be
used as a base for our own implementation, nothing more. We can also
discard MET (unmaintained, doesn't compile under Windows) and PETE (doesn't
exist on its own any more, part of POOMA). Next I excluded POOMA because it
seems to be much, much more than what we need and is not particularly easy
to use. I also have concerns about its activity. Further, both FC++ and
boost::mpl do many interesting things but nothing directly relevant to the
problem at hand. Finally, all of Blitz++, uBLAS and MTL are clearly geared
towards scientific computing exclusively. On its own this is not a problem,
of course, but I'd expect them to be optimized for working with huge
matrices and not (relatively) small vectors as is the goal here. In
addition, it turned out finally that MTL doesn't use expression templates
yet and so would have poor performance. So the choice is ultimately between
Blitz++ and uBLAS and between them I think I prefer the latter because it's
more recent and, well, being part of boost doesn't hurt.


 So our possibilities are:

- use uBLAS (or Blitz++ if this is preferable for some reason)
- write a simple ET library ourselves (possible using GET code)
- just keep the current code but simplify it by using boost::lambda, e.g.

        transform(v1.begin(), v1.end(), v2.begin(), output.begin(),
                  min(1., max(0., _1 + _2))


 I honestly don't know what to recommend. uBLAS is nice but it's a big and
rather complicated library (but it's fully template and hence inline). OTOH
redoing the work ourselves is not particularly appealing neither and while
it wouldn't take that long it still feels like time lost. So probably I'd
just use boost::lambda to make using std algorithms less painful. It should
have decent performance (I could test it...) but wouldn't result in the
clearest possible code.

 Regards,
VZ