Re: [eigen] nesting

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

2010/2/7 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
> also note that the nest everything by reference approach we have in Eigen
> 2.0 also leads to unnecessary copies:
>
> Indeed since (a*b).adjoint() is compiled as:
>
> (a*b).conjugate().nesteByValue().transpose()
>
> the result of a*b gets copied once from the Conjugate to the Transpose
> expression.

Oh yes, sure, the discussion in this thread also made me consider
this. So it's not like things were perfect in 2.0 (plus, the
nesting-by-reference made it hard for compilers to generate good code,
as Hauke found).

The approach of an expression evaluator that stores all temporaries at
a "global" scope (that is, in the scope that calls the operator= )
seems to have all the advantages, and the only inconvenient of extra
complexity, hence i'm afraid extra compilation times. But since all
other approaches have bigger downsides, it seems reasonable...

Benoit

>
> Finaly, let emphasize again that with either the current devel approach or
> the evaluator I described in the previous email, dynamic sized matrices can
> be easily worked-around using kind of shared pointers or a list of
> temporaries respectively. So the discussion might be focused on fixed size
> objects.
>
> gael
>
> On Sun, Feb 7, 2010 at 10:16 AM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
> wrote:
>>
>> 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. 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
>>> >>>>>>
>>> >>>>>
>>> >>>>
>>> >>>>
>>> >>>>
>>> >>>
>>> >>>
>>> >>>
>>> >>
>>> >>
>>> >>
>>> >
>>> >
>>> >
>>>
>>>
>>
>>
>
>
>
>