Re: [eigen] nesting

On Sun, Feb 7, 2010 at 3:55 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:

2010/2/7 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:

>
> sorry I did thought about that case. So basically, just to be sure that
> everybody understand what's going:
>
> Let"s consider (a*b).adjoint() with complexes. adjoint() is implemented as:
>
> template<Derived> Transpose<Conjugate<Derived> >
> MatrixBase<Derived>::adjoint() const
> {
> return this->conjugate().transpose();
> }
>
> The problem is that here Derived is a Product which has to be evaluated. So
> Conjugate<Derived> stores a full Matrix (by value and the product is
> directly evaluated into this Matrix in the ctor of Conjugate). Since it has
> the NestParentByReference bit, the Transpose _expression_ stores a reference
> to the *temporary* Conjugate<Derived> object. Since this temporary object is
> deleted at the exit of the adjoint() function, the returned Transpose
> _expression_ stores a reference to a deleted object. Hence the crash.
>
>
> On Sat, Feb 6, 2010 at 6:57 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
> wrote:
>>
>> But your nest-by-reference changes have been such a great improvement,
>> we don't want to give that up.
>>
>> Now it's looking like Gael's _expression_ evaluator approach is the way
>> forward!
>
> Unfortunately I'm thinking that we would have the exact same issue..

Well, the way I thought I understood your idea, it wouldn't have this
issue. Here is how I thought I understood your idea:

At the time of the construction of the _expression_, we don't evaluate
any temporary. We give up the idea that that might allow to cut the
complexity of expressions.

Thus, when doing (a*b).adjoint(), the a*b Product object is not
evaluated. We don't honor the EvalBeforeNestingBit at that level, we
will honor it at evaluation time (when the whole _expression_ gets
evaluated).

Eventually, the whole _expression_ gets evaluated:

c = (a*b).adjoint();

We must then write a template metaprogram that walks up the RHS tree,
finds all the places where we must evaluate into temporaries, and
stores these temporaries. The key here is that these temporaries are
stored at the "global" scope of that template metaprogram, so they
don't die until the end of that line of code (the next semicolon).

I agree that writing such a metaprogram is not easy, but it has got to
be possible. We could do that together at the meeting.

yes, this was my idea too, but I thought about how to write the metaprogram which walk trough the _expression_, and I don't see how to instantiate the temporary at the toplevel. (The piece of code I wrote in my email is exactly such a metaprogram).

gael

Benoit

> Again
> let's consider the same example (a*b).adjoint() of type
> Transpose<Conjugate<Product<Matrix,Matrix>>>. I still don't know how to
> write a generic evaluator which would be able to evaluated the nested
> product and return it to build a Tranpose<Conjugate<Matrix>> _expression_....
>
> FYI here are the respective instantiations and function calls with what I
> had in mind:
>
> struct Evaluator< Transpose<Conjugate<Product<Matrix,Matrix>>> > {
> typedef Transpose<Evaluator<Conjugate<Product<Matrix,Matrix>>
>>::ReturnedExpr> ReturnedExpr;
> static ReturnedExpr run(const Transpose<Conjugate<Product<Matrix,Matrix>>>&
> expr)
> {
>    return Evaluator< Conjugate<Product<Matrix,Matrix>>
>>::run(expr.nestedExpression());
> }
> };
>
> struct Evaluator< Conjugate<Product<Matrix,Matrix>> > {
> typedef Transpose<Evaluator<Product<Matrix,Matrix> >::ReturnedExpr>
> ReturnedExpr;
> static ReturnedExpr run(const Conjugate<Product<Matrix,Matrix>>& expr)
> {
>    return ReturnedExpr( Evaluator< Product<Matrix,Matrix>
>>::run(expr.nestedExpression()) );
>    // here Evaluator< Product<Matrix,Matrix> >::run(expr.nestedExpression())
> is evaluated to a temporary which is deleted at the exit of this
> function....
> }
> };
>
> struct Evaluator< Product<Matrix,Matrix> > {
> typedef Matrix ReturnedExpr;
> static const Product<Matrix,Matrix>& run(const Product<Matrix,Matrix>& prod)
> {
> return prod;
> }
> };
>
>
> So the problem is still widely open for ideas!
>
> gael
>
>>
>> Benoit
>>
>> 2010/2/6 Hauke Heibel <hauke.heibel@xxxxxxxxxxxxxx>:
>> > The only persistent bug is adjoint_4 and this one is really
>> > unfortunate. We are back to the need of NestByValue() or .eval().
>> > Removing
>> >
>> > | NestParentByRefBit
>> > | EIGEN_PROPAGATE_NESTING_BIT(Lhs::Flags|Rhs::Flags)
>> >
>> > from the ProductBase::Flags fixes the issue.
>> >
>> > This line
>> >
>> > VERIFY_IS_APPROX((m1.adjoint() * m2).adjoint(), m2.adjoint() *
>> > m1);
>> >
>> > and in particular this _expression_
>> >
>> > (m1.adjoint() * m2).adjoint()
>> >
>> > causes the crash. Adding .eval() solves the issue as well - of course,
>> > since nothing will be nested by reference anymore. Ultimately I think
>> > we need the _expression_ analyzer. Crashes like this are really nasty
>> > and one of the core reasons we wanted to have copy by value. Or am I
>> > wrong?
>> >
>> > - Hauke
>> >
>> > On Sat, Feb 6, 2010 at 5:15 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
>> > wrote:
>> >> 2010/2/6 Hauke Heibel <hauke.heibel@xxxxxxxxxxxxxx>:
>> >>> I am ready to push. These tests are currently failing (GCC 4.4.1)
>> >>>
>> >>> 98% tests passed, 8 tests failed out of 380
>> >>> 84 - adjoint_4 (Failed)
>> >>> 182 - stable_norm_1 (Failed)
>> >>> 183 - stable_norm_2 (Failed)
>> >>> 184 - stable_norm_3 (Failed)
>> >>> 185 - stable_norm_4 (Failed)
>> >>> 197 - lu_2 (Failed)
>> >>> 375 - nullary_7 (Failed)
>> >>> 376 - nullary_8 (Failed)
>> >>>
>> >>> Stable norm is always failing over here for the others I am not sure.
>> >>> I don't want to look into the failing tests right now but I'ld like to
>> >>> push what is there so far. Any concerns regarding pushing?
>> >>
>> >> I'm not so concerned about stable_norm as it is a non central feature,
>> >> but the assortment of other test failures suggests that something
>> >> really central is still not right.
>> >>
>> >> Could you, for now, rather push to a fork?
>> >> Just create a fork on bitbucket and do
>> >> cd eigen
>> >> hg push https://clone/url/of/new/fork
>> >>
>> >> Thanks
>> >> Benoit
>> >>
>> >>
>> >>>
>> >>> TODO:
>> >>> - long term we still might need Gael's full _expression_ processor
>> >>> approach
>> >>> - regression tests for product related expressions and the number of
>> >>> temporaries
>> >>> - maybe a new unit test, checking the nesting type
>> >>> - verify that the failing tests have nothing to do with the applied
>> >>> changes
>> >>>
>> >>> - Hauke
>> >>>
>> >>> On Sat, Feb 6, 2010 at 3:48 PM, Benoit Jacob
>> >>> <jacob..benoit.1@xxxxxxxxx> wrote:
>> >>>> Wow, this is a great test!
>> >>>> I haven't tried to think if it is enough or if you should add
>> >>>> something, but at least it's a great piece of testing code.
>> >>>>
>> >>>> Benoit
>> >>>>
>> >>>> 2010/2/6 Hauke Heibel <hauke.heibel@xxxxxxxxxxxxxx>:
>> >>>>> It is working. Now I just have to double check all Flag definitions
>> >>>>> within Eigen, something around ~53, since potentially I need to add
>> >>>>> the EIGEN_PROPAGATE_NESTING_BIT define.
>> >>>>>
>> >>>>> I could also do a lot of testing - what do you think how much is
>> >>>>> sane?
>> >>>>> See the attached file which basically tests Replicate, Reverse,
>> >>>>> Select
>> >>>>> in combination with and without different kinds of products. I think
>> >>>>> testing every single combination is a little bit overkill - what do
>> >>>>> you think?
>> >>>>>
>> >>>>> - Hauke
>> >>>>>
>> >>>>> On Sat, Feb 6, 2010 at 12:38 PM, Hauke Heibel
>> >>>>> <hauke.heibel@xxxxxxxxxxxxxx> wrote:
>> >>>>>> It should have been "toggle only the storage order."
>> >>>>>>
>> >>>>>> Since we now have bit which are not inherited, we might rename
>> >>>>>> HereditaryBits bits and introduce a new set. How about
>> >>>>>>
>> >>>>>> DominantBits /* always inherited */
>> >>>>>> RecessiveBits /* only in rare cases inherited */
>> >>>>>>
>> >>>>>> Then, in the future one could do
>> >>>>>>
>> >>>>>> Flags = OtherType::Flags & ~RecessiveBits
>> >>>>>>
>> >>>>>> to disable only those we don't want to inherit. This will of course
>> >>>>>> only then make sense, when there is the possibility for new
>> >>>>>> recessive
>> >>>>>> bits in the future or just because we like it...
>> >>>>>>
>> >>>>>> - Hauke
>> >>>>>>
>> >>>>>
>> >>>>
>> >>>>
>> >>>>
>> >>>
>> >>>
>> >>>
>> >>
>> >>
>> >>
>> >
>> >
>> >
>>
>>
>
>
>