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

From: Hurd, Matthew (hurdm_at_[hidden])
Date: 2003-11-25 22:07:50

> On Behalf Of Markus Werle
> Subject: [boost] RE: Operation representation in boost::etl
> 
> Matthew Hurd wrote:
> 
> >> On Behalf Of Markus Werle
> >> Sent: Tuesday, 25 November 2003 10:02 PM
> >> Subject: [boost] Operation representation in boost::etl
> >>
> > <snip>
<snip>

> >
> >   *  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' ?

It is just the DGEMM's way of saying that you may optionally transpose A or B but not C as part of the operation.
 
> >   *
> >   *  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.

Lovely.
 
> > 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.

Sounds good.

> > 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.

I'm glad you know better.  It does sound as confused as I imagined.  Perhaps a boost compiler support page similar to the regression tests could show the macro workarounds / shortcoming and performance factors for various constructs which would serve a dual purpose on keeping pressure on vendors and helping know acceptable and portable limits of implementation details.  The two member optimisation rule of thumb is very interesting and such a benchmark might live in such a page showing, say, the difference between 1,2,3,4,5... members.
 
> 
> > 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 };
> };

If you need a dumb user to stick needles into I'd be a willing subject ;-)  I might be in danger of learning something though ;-)

 
> > 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 ...

yep.

Ublas-dev has its own list... you should chat to those guys if you aren't already.

Instead of boost::etl::linalg perhaps it should be boost::ublas that uses boost::etl.  Or maybe a visitor pattern namespace or double dispatch namespace is needed ;-)

 
> 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.

Sounds very cool.

> 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.

I think Ublas matrix has some such traits already, if you're planning on a boost::etl then working with the ublas matrix representation might make things easier.  If it makes it harder it still would be worthwhile to leverage ublas work.

> >  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
> 

<snip>
Thanks for the heads up.  

> 
> > 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.

The "skills we dream of" part is certainly true from my perspective.  But you can still do better.  Elimination of temporary objects is still elimination of temporary objects.  Also pre-allocation / reserving based on information from the temporaries is a win.

I've copied the results I posted previously below

<paste>

GCC results still show some benefit with my naïve implementation but not as dramatic as VC7.1

                          VC7.1       GCC 3.2* 
                         ------       -------
Long    expr template     8.55s         8.89s 
        std::string      76.56s        30.38s 
        speedup           8.96          3.42 

Medium  expr template     1.38s         1.42s 
        std::string      27.66s         3.83s 
        speedup          20.11          2.69

_____________________________
Note, the GCC settings had a very aggressive inlining setting.  With the "factory default", (600 instead an aggressive 6000)  the medium string was 1.89s and 6.406s for a speed up of 3.4

</paste>

But this approach, w.r.t. std::string, is pretty useless outside of the std library implementation I think.  It did raise some thoughts in my mind about how std library implementations might be partially altered all extended, but that is another issue.  The only good might be if the std::string authors bite the bullet and do the expr template concat optimisations.

Perhaps boost::spirit and proposed static regex could all benefit from having an external expression template representation... There is much reinvention going on.

> 
> thanks for your comments,
> 
> Markus

Thanks for your patience with a naïve user.  I hope you get some better traction from someone who can actually help a bit ;-)

Regards,

Matt Hurd.

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments.  Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited.  Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument.  Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.