[boost] Re: uBLAS and expression templates

From: Michael Stevens (support-1_at_[hidden])
Date: 2002-07-01 01:57:19

>
>
>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). The 
syntax of client template code changes between the two modes. 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. 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.

>>> Certainly it is wrong to think about various left or
>>> right associative interpretations of prod in this context.
>>> I believe this matches my expectation for clear and well definied
>>> semantics. I cannot think of a way to automatically add temporaries that
>>> would not muddle this horribly.
>>    
>>
>
>I think I illustrated how you can evaluate A*(B*v) both with and without
>temporary vectors, giving identical results but with somewhat different
>efficiency trade-offs.
>
>  
>
>>>     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!

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?

>>>     c) There are simple ways to explicity define when you want a
>>> temporary. Either use more then one expression OR add explict
>>    
>>
>constructors.
>
>I think the library should ultimately be tuned to choose the most efficient
>strategy which doesn't affect accuracy.
>
>  
>
>>>     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! I was refering to the need to 
sometime have explict control of when heap operations occurs are runtime..
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.

Michael