From: Jeremy Graham Siek (jsiek_at_[hidden])
Date: 2004-07-05 19:51:04
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
> 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
> > > 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
> 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
> 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
> 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
> 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 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 (http://www.boost.org)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk