Re: [boost] Re: uBLAS and expression templates

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-07-01 07:07:45

----- Original Message -----
From: "Michael Stevens" <support-1_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, July 01, 2002 2:57 AM
Subject: [boost] Re: uBLAS and expression templates

> >
> >
> >From: "David Abrahams" <david.abrahams_at_[hidden]>
> >
> >
> >>> I say this for four reasons:
> >>>     a) The semantics of expression evaluation need to be clear and
well
> >>> defined. This is important to me, as I need to know the complexity
and
> >>
> >>
> >---------------------------------------------------------^
> >"worst-case"?
> >
> >IOW, I presume you won't mind if an operation goes faster than expected.
> >
> >
> Sounds good!
>
> >>> likely numerical accuracy of the result. Certainly uBLAS with ET
> >>> certainly has very different semantics (and syntax) then without ET.
> >>
> >>
> >
> >Really, the syntax is different? Can you give an example? That really
> >surprises me, considering they're turning ETs on and off with NDEBUG. If
> >that were the case, most programs would stop compiling in release mode.
> >
> >>
> >>> Benidict's points and David's worries regarding changes to template
> >>> matching are relvant here.
> >>
> >>
> >
> >How are changes to template matching relevant?
> >
> By "(and syntax)" I was simply refereing to template matching changes
> between ET on and off. As you pointed out previously, programs may stop
> compiling depending on NDEBUG (or the uBLAS config header ET macro).

I never said that. I just said "IF it were true that the syntax changed
THEN code would stop compiling". But I don't believe client syntax changes.

> The syntax of client template code changes between the two modes.

I'm still looking for examples where the syntax of client code must change
when ETs are enabled.

> However,
> the semantic differences are mostly what I am interested in ;-)
>
> >>> I believe uBLAS's ET semantics are that the expression is evaluated
as a
> >>> WHOLE. That is each element of the result is computed using a
complete
> >>> expression formed from all the element on which it depends. Correct
me
> >>> if I am wrong here!
> >>
> >>
> >
> >It's pretty hard to correct such a vague statement. Can you be specific
> >about what you mean?
> >
> Certainly this wasn't ment to be vague! It was a two sentance attempt at
> a concise definition of what uBLAS's ET semenatics are. Something I
> believe should be clearly defined in uBLAS's documentation. Let me try
> again:
>
> An expression evalutation takes place when an assign(), operator=() or
> constructor from an expression is executed. Each element of the result
> is computed individually from all the elements of the expression on
> which it depends.

As long as you allow the implmenetation to choose a semantically equivalent
but faster implmentation which uses temporaries, I have no objection.

> Semanticaly, the linear alegbra expression is first
> expanded into an equivilent set of element expression. These element
> expressions are individually evaluted with the normal expression
> evaluation order.

OK, but if we make the allowance I am asking for, the setatement has no
value other than to say when the result is computed and that its value is
the same as without ETs.

> >>>     b) There is no "Best" solution to introducing temporaris. They
vary
> >>> in complexity and numerical accuracy.
> >>
> >>
> >
> >I think automatically introduced temporaries should never affect
accuracy.
> >
> Certainly given a normal left to right association of the expression,
> then the temporaries that could be introduced will have no effect on the
> accurary.
> If we allowed associative expression reordering for minimum compexity
> then we can effect the accuracy. I guess the point is irrelevent in this
> case as matrix size is not known at compile time so such a stratergy is
> not possible!

I don't think so: you can generate both versions and inspect the sizes at
runtime.

> Still we have to be a very careful with the semantics of automatic
> temporaries. uBLAS expression may mix many types of storage. For example
> evaluating S*D*v where S is sparse and D is dense. What storage do we
> use for the automatic temporary that will containt S*D?

I think for that case you don't get any benefit from temporary storage.

> >>>     d) The temporaries would inevitably be allocated from the heap.
My
> >>> experience with embedded programming makes we object to anything
using
> >>> the heap without my explict consent!
> >>
> >>
> >
> >Sometimes a little heap-allocated storage results in a huge speedup. See
> >scatter/gather for sparse matrices, for example (or the adaptive
algorithms
> >in the standard library). I would not want to make operations much less
> >efficient just to avoid the objections of an anti-heap embedded
programmer.
> >
> I hope you didn't think I meant "explict consent" regarding this
> discussion, that would be very rude!

No, I didn't.

> I was refering to the need to
> sometime have explict control of when heap operations occurs are
runtime..

I understand, but I think the need for that kind of control (e.g. to
prevent a temporary heap allocation which would result in a speedup) must
be rare in high-performance numerical applications, and I wouldn't want
Joerg and Matthias to cripple the library to accomodate it.

> Let rephrase this. The present definition of uBLAS expression evaluation
> gives the programmer complete control over complexity and temporaries.
> Temporaries may be sparse or dense. They may be allocated on the heap or
> stored offline! I think this is a good thing.

This is the case currently? That surprises me. Having to specify what's
going to happen with temporaries at each step of my calculation seems more
burdensome than useful to me.

-Dave