Boost logo

Boost :

From: Jeremy Graham Siek (jsiek_at_[hidden])
Date: 2004-07-05 19:51:04

Hi Michael,

On Jul 5, 2004, at 4:52 PM, Michael Stevens wrote:
> Hi Jeremy,
> Thanks for chipping in on this. I don't think we have conversed
> before, apart
> from maybe a few patches I submitted for MTL. Although it would be
> great for
> everyone to work on uBLAS I think a revived MTL would also be a good
> thing.
> The design of MTL was very influential.


> I won't comment on the other issues as I have already posted a few
> thoughts on
> these matters.
> > >  Mmmh, this open pitfalls concerning A*B*C in performance issues
> for
> > >  non experts.
> >
> > No, the right way to handle this is to have the expression template
> > machinery
> > identify that a temporary is needed, and create one automatically.
> I wonder if you caught the discussion on this about 6 months ago. I
> would
> strongly argue that the automatic creation of temporaries in the
> subexpression context is a bad thing...
> The roles of the expressions we declare (as in declarative
> programming) is
> twofold. a) to express the mathematical context b) to express how
> this should
> be computed. That is, to be able to express how the expression is to
> be
> evaluated. This gives us control over its numerical properties and
> also of
> the time and space complexity.
> In principle, uBLAS has a one to one relationship between an
> expression and
> how it is evaluated. Simply stated this is based on an element by
> element
> evaluation of assignment. There are shortcuts in the case of sparse
> types but
> the principle holds.
> An expression A+B+C can be evaluated in this manner trivially.
> A*B*C can also be evaluated in this manner, although the element by
> element
> rule results in an O() that is not what many users expect.
> To get the O() that users expect we could automagically insert
> temporaries. I
> fear this is a tar pit however. What temporary should be chosen? Each
> of A B
> or C could be a either dense, sparse, compressed, banded, symmetric or
> combinations therefore. The type the user expects or is "the best" is
> not at
> all clear.

Although automagically inserting temporaries in non-trivial (especially
it must all be done with template meta-programming) I do not think it is
a tar pit. Here is the simply heuristic that I used for MTL 3
to decide where to put temporaries:

1. If an operation needs to read from an argument multiple times,
     evaluate the argument eagerly into a temporary. For example,
     a sparse matrix in compressed row format times the sum
    of two vectors:

    A * (x + y)

   In this case, the (x + y) would be evaluated into a temporary before
   evaluating the multiplication.

2. If an operation writes into its output in multiple passes, then
    the operation in an eager fashion. For example, the sum
    of a vector and the product of a sparse matrix in compressed column
    format and a vector.

   x + (A * y)

   In this case, the (A * y) would be evaluated into a temporary before
   evaluating the addition.

> I think the only correct solution is to force the user to specify
> this type.
> Incidently, the no temporary evaluation should also be an option as
> in some
> cases (small sizes) it is desirable. uBLAS currently disallows this
> to avoid
> confusing the user. I should be reinstated in some form however.
> All the best,
>       Michael
> --
> ___________________________________
> Michael Stevens Systems Engineering
> 34128 Kassel, Germany
> Phone/Fax: +49 561 5218038
> Navigation Systems, Estimation  and
>                  Bayesian Filtering
> ___________________________________
Jeremy Siek <jsiek_at_[hidden]>
Ph.D. Candidate, Indiana University Bloomington
C++ Booster (

Boost list run by bdawes at, gregod at, cpdaniel at, john at