[boost] RE: Operation representation in boost::etl

From: Markus Werle (numerical.simulation_at_[hidden])
Date: 2003-11-25 08:45:01

Matthew Hurd wrote:

>> On Behalf Of Markus Werle
>> Sent: Tuesday, 25 November 2003 10:02 PM
>> Subject: [boost] Operation representation in boost::etl
>> 
> <snip>
>> Please comment and tell me what you think.
> 
> A boost::etl would be a lovely thing to see.  Such technology is beyond me
> so I wish you well, but I would like to offer some comment.  (A lack of
> understanding rarely stops me opening my mouth)

Fine.

> More than two operands would be a very good thing.  Representing such
> common operations that you might put such a library to use with respect
> to, such as:
> 
>   *  DGEMM  performs one of the matrix-matrix operations
>   *
>   *     C := alpha*op( A )*op( B ) + beta*C,

Daixtrose handles this with nested recursion through the tree.
The special case of a sum of matrices (or virtual matrices)
might or might not profit from a special representation.
 
>   *
>   *  where  op( X ) is one of
>   *
>   *     op( X ) = X   or   op( X ) = X',

What is X' ?

>   *
>   *  alpha and beta are scalars, and A, B and C are matrices, with op( A )
>   *  an m by k matrix,  op( B )  a  k by n matrix and  C an m by n matrix.
> 
> would be good.  I can imagine such a library being extended to refactoring
> and rewriting expression trees with such multi operand targets in mind
> directly or perhaps just indirectly.

Note that Daixtrose already allows specialization for things like
the expresion above.

> I worry that the simple elegance of recursing down the expr children might
> be a little more complicated if it is both children and a type list... but
> I hardly understand it...

simple traits save you here. The arity of a template can be determined
at compile time, I guess, so a dispatch is easy ...
The idea of flattening expressions came up again when I saw
mpl::for_each and mpl::transform , they offer some nice tools 
to express a long story in short form.

> OTOH, whilst adding another level of indirection cures many a problem, in
> my mind I want to go to the trouble of using a boost::etl because
> performance matters dearly to me.  
> I suspect the cost might vary, for such an extra
> level of indirection, quite a bit from compiler to compiler as many
> compilers already struggle with optimizing simpler ETL structures, but you
> may know better.

I know better: neither compilation time nor runtime performance are
predictable.
There is one rule of thumb, though:
I encountered the KISS paradigm (Keep It Simple Stupid) as crucial.
Classes or structs with less than 2 members provoke compilers
to "rethink" their optimization. I once had the case where 
making  the memfun Name() of 
template <char [256]> class Variable { double Value; /* ... */ };
a free function increased performance by 5%. This is why nested
complicated structures must be avoided. OTOH the cute design of mpl
may outweigh this cost.
 

> So it may not be pragmatic...  only some benchmarks on a few platforms
> might yield the true answer, but to do that you have to write it and then
> you might as well leave in it to push vendors and for the niceties it may
> bring
> as you might always use binary ops anyway.  Strikes me as worth doing as
> some other boost libs have also gone down the track of including
> alternative interfaces to see what real world use brings to table...

Daixtrose is customizeable in may ways. The question is: are there
other buttons you miss?
Of course I am able to provide 5 ways to represent your structures,
(e.g. binop<Add, ...> or binop<..., Add>?)
but I'd prefer to concentrate on one of these.
Offering alternativbes here might not be fruitful ... or do they?

template <> struct etl_customization<MyClass>
{
  enum { no_flat_expr_optimization = true };
};

> Also, it might be nice to build with something specific in mind to direct
> the goals. 

Of course the numerics people are the one to profit.
In general you can say: Expression Templates are good for 
cases where you need to really avoid temporary objects for 
the sake of runtime performance. 

> Perhaps there is some benefit boost::etl might bring to
> boost::ublas.

Maybe boost::ublas might bring benefit to boost::etl::linalg ...

The interesting part is: boost::etl alias Daixtrose is pluggable.
I just wrote a draft extension to my Linalg package called 
VirtualMatrix, which allows every script kid to plug and handle
a ublas::matrix and a boost::array in the same expression without pain.
I use it to create read-only objects which behave like matrices, while not
storing any values, but generating the requested entries on the fly,
depending on some other data. This works with boost::functions.

The linalg demo's redesign is planned to introduce a more
generic concept of a matrix, customizeable via traits, which
removes some of the pain for users of current Daixtrose.

>  It would be an interesting non-trivial proving ground,
> thought you might be better off picking on something less large.
> 
> Any thoughts about how Daixtrose is different to POOMAs PETE?

I answered this before in one of the boost-MLs, but the most
important issues are

non-diff: 

- Daixtrose's concept of separation between expression representation
  and evaluation is a true reinvention of what PETE offered.
  I was proud of my invention, but soon found out I was too late
  (and too stupid to read source code available in my home directory)

diffs (thinsg that Daixtrsoe offers):

- the fine-grained disambiguation mechanism (compiler firewalls
  against incompatible combinations), which allows building rules where 
  (A + B + C) + D compiles, while (A + B) + (C + D) or A + B + C*D fail.

- user's ability to decide on copy or reference semantics for the leaves
  on a per-class _and_ per-situation basis.

- glueable polymorphic behaviour, which makes expressions storable
  in std::containers

- Daixtrose is non-intrusive. It has its own namespace, it requires
  nothing from the types used in an expression - well, except that
  they must be constructible ...

> I see your manual is pretty much oriented to the math side of the
> equation. I would be interested to see how a simple non numeric thing,
> like the string concatenation I tried out a while ago, would lend itself
> you your lib.

I lack the time to write some demo, but I think a good starting
point is the SimpleGetValue example.
Also I lack some information about the requirements of such a lib.
Please point me to older messages about this, so I get an idea.

String concatenation with Daixtrose makes only sense to me when
the length of each string is fixed and known at compile time.
Otherwise you may encounter that std::string has a long history 
and people with skills we dream of programmed it.

thanks for your comments,

Markus

-- 
Build your own Expression Template Library with Daixtrose!
Visit http://daixtrose.sourceforge.net/