Re: [eigen] Dynamic allocations in SelfAdjointEigenSolver and HouseholderQR

[Ricard Marxer <ricardmp@xxxxxxxxx>]

Hi,

First of all, sorry for the late answer.  Thanks Adolfo for the insights.
Gael, I will try to add it to the tracker you said in the coming days,
to not forget about it.  If I find some time I will try to have a look
at it myself.

ricard



On Mon, Jan 23, 2012 at 5:46 PM, Gael Guennebaud
<gael.guennebaud@xxxxxxxxx> wrote:
> Feel free to fill an entry there http://eigen.tuxfamily.org/bz such
> that we don't forget about it. If you want to have a look at it by
> yourself, that will sure speed up the fixing process.
>
>
> gael
>
> 2012/1/20 Adolfo Rodríguez Tsouroukdissian <adolfo.rodriguez@xxxxxxxxxxxxxxxx>:
>>
>>
>> On Fri, Jan 20, 2012 at 12:42 AM, Ricard Marxer <ricardmp@xxxxxxxxx> wrote:
>>>
>>> Is it possible to avoid dynamic allocations in
>>> SelfAdjointEigenSolver.compute() and HouseholderQR.solve(), when using
>>> dynamic size matrices?
>>
>>
>> Inspecting the code of HouseholderQR, there are indeed allocations performed
>> by solve(), as it creates temporaries. To avoid such allocations, a patch
>> must be submitted. It's doable, though. I know for sure that Eigen 3.1 alpha
>> prevents allocations from HouseholderQR.compute(), and for householderQ(),
>> the latter only if you invoke with the alternate syntax
>> householderQ().evalTo(result, preallocated_temporary). When I sent the
>> patches I didn't look into solve(), as I had no use case for it :(
>>
>> SelfAdjointEigenSolver.compute() is probably subject to similar
>> considerations. Some time ago [1], I tried to remove as much allocations as
>> I could from most decompositions, but issues remained. Anyway, that was a
>> long time ago and the eigenvalues module has received much love since then.
>>
>> HTH,
>>
>> Adolfo.
>>
>> [1]
>> http://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2010/04/msg00101.html
>>
>>
>>> In the examples the matrices are small and their size is known at
>>> compile time.  But in my use case they are dynamic and their size is
>>> only known at runtime.
>>>
>>> To try the attachment tests simply run:
>>> g++ -I../eigen dynalloc_selfadjoint.cpp -o dynalloc_selfadjoint
>>> &&./dynalloc_selfadjointg++ -I../eigen dynalloc_qr.cpp -o dynalloc_qr
>>> &&  ./dynalloc_qr
>>> The backtraces show the following:
>>> (gdb) bt#0  0x00007ffff72ef405 in *__GI_raise (sig=<optimized out>)
>>> at../nptl/sysdeps/unix/sysv/linux/raise.c:64#1  0x00007ffff72f2680 in
>>> *__GI_abort () at abort.c:92#2  0x00007ffff72e85b1 in
>>> *__GI___assert_fail (   assertion=0x4247c8 "is_malloc_allowed() &&
>>> \"heap allocation isforbidden (EIGEN_RUNTIME_NO_MALLOC is defined and
>>> g_is_malloc_allowedis false)\"", file=<optimized out>, line=197,
>>> function=0x425500
>>> "voidEigen::internal::check_that_malloc_is_allowed()") at
>>> assert.c:81#3  0x0000000000402b7c in
>>> Eigen::internal::check_that_malloc_is_allowed() ()#4
>>> 0x0000000000402b8f in Eigen::internal::aligned_malloc(unsigned long)
>>> ()#5  0x0000000000409092 in
>>> void*Eigen::internal::conditional_aligned_malloc<true>(unsigned long)
>>> ()#6  0x0000000000406b0b in
>>> float*Eigen::internal::conditional_aligned_new_auto<float,
>>> true>(unsignedlong) ()#7  0x00000000004069e8 in
>>> Eigen::DenseStorage<float, -1, -1, 1,0>::DenseStorage(long, long,
>>> long) ()#8  0x0000000000405796 in
>>> Eigen::PlainObjectBase<Eigen::Matrix<float,-1, 1, 0, -1, 1>
>>> >::PlainObjectBase(long, long, long) ()#9  0x0000000000404415 in
>>> Eigen::Matrix<float, -1, 1, 0, -1, 1>::Matrix(long) ()#10
>>> 0x0000000000405e3d in
>>>
>>> voidEigen::internal::tridiagonalization_inplace_selector<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1>, -1, false>::run<Eigen::Matrix<float, -1, 1, 0, -1,1>,
>>> Eigen::Matrix<float, -1, 1, 0, -1, 1> >(Eigen::Matrix<float, -1,-1, 0,
>>> -1, -1>&, Eigen::Matrix<float, -1, 1, 0, -1, 1>&,Eigen::Matrix<float,
>>> -1, 1, 0, -1, 1>&, bool) ()#11 0x0000000000404b1e in
>>> voidEigen::internal::tridiagonalization_inplace<Eigen::Matrix<float,
>>> -1,-1, 0, -1, -1>, Eigen::Matrix<float, -1, 1, 0, -1,
>>> 1>,Eigen::Matrix<float, -1, 1, 0, -1, 1> >(Eigen::Matrix<float, -1,
>>> -1,0, -1, -1>&, Eigen::Matrix<float, -1, 1, 0, -1,
>>> 1>&,Eigen::Matrix<float, -1, 1, 0, -1, 1>&, bool) ()#12
>>> 0x0000000000403926
>>> inEigen::SelfAdjointEigenSolver<Eigen::Matrix<float, -1, -1, 0, -1,
>>> -1>>::compute(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, int)
>>> ()#13 0x000000000040142a in main ()
>>> and
>>> (gdb) bt#0  0x00007ffff72ef405 in *__GI_raise (sig=<optimized out>)
>>> at../nptl/sysdeps/unix/sysv/linux/raise.c:64#1  0x00007ffff72f2680 in
>>> *__GI_abort () at abort.c:92#2  0x00007ffff72e85b1 in
>>> *__GI___assert_fail (   assertion=0x42dcc8 "is_malloc_allowed() &&
>>> \"heap allocation isforbidden (EIGEN_RUNTIME_NO_MALLOC is defined and
>>> g_is_malloc_allowedis false)\"", file=<optimized out>, line=197,
>>> function=0x42ecc0
>>> "voidEigen::internal::check_that_malloc_is_allowed()") at
>>> assert.c:81#3  0x000000000040180a in
>>> Eigen::internal::check_that_malloc_is_allowed() ()#4
>>> 0x000000000040181d in Eigen::internal::aligned_malloc(unsigned long)
>>> ()#5  0x0000000000406576 in
>>> void*Eigen::internal::conditional_aligned_malloc<true>(unsigned long)
>>> ()#6  0x00000000004050ed in
>>> float*Eigen::internal::conditional_aligned_new_auto<float,
>>> true>(unsignedlong) ()#7  0x00000000004043b0 in
>>> Eigen::DenseStorage<float, -1, -1, 1,0>::DenseStorage(long, long,
>>> long) ()#8  0x0000000000403564 in
>>> Eigen::PlainObjectBase<Eigen::Matrix<float,-1, 1, 0, -1, 1>
>>> >::PlainObjectBase(long, long, long) ()#9  0x0000000000402c51 in
>>> Eigen::Matrix<float, -1, 1, 0, -1,1>::Matrix(Eigen::Matrix<float, -1,
>>> 1, 0, -1, 1> const&) ()#10 0x000000000040a775 in
>>>
>>> voidEigen::internal::solve_retval<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1,
>>> 1>>::evalTo<Eigen::Matrix<float, -1, 1, 0, -1, 1>
>>> >(Eigen::Matrix<float,-1, 1, 0, -1, 1>&) const ()#11
>>> 0x0000000000408505 in
>>>
>>> voidEigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1,
>>> 1>>::evalTo<Eigen::Matrix<float, -1, 1, 0, -1, 1>
>>> >(Eigen::Matrix<float,-1, 1, 0, -1, 1>&) const ()#12
>>> 0x00000000004063e1 in
>>>
>>> voidEigen::ReturnByValue<Eigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1, 1>
>>> >>::evalTo<Eigen::Matrix<float, -1, 1, 0, -1, 1>
>>> >(Eigen::Matrix<float,-1, 1, 0, -1, 1>&) const ()#13
>>> 0x0000000000404d9e in Eigen::Matrix<float, -1, 1, 0, -1,
>>> 1>&Eigen::MatrixBase<Eigen::Matrix<float, -1, 1, 0, -1,
>>>
>>> 1>>::operator=<Eigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1, 1>
>>>
>>> >> >>(Eigen::ReturnByValue<Eigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1, 1> > >const&)
>>> ()#14 0x0000000000403a8c in Eigen::Matrix<float, -1, 1, 0, -1,
>>> 1>&Eigen::PlainObjectBase<Eigen::Matrix<float, -1, 1, 0, -1,
>>>
>>> 1>>::operator=<Eigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1, 1>
>>>
>>> >> >>(Eigen::ReturnByValue<Eigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1, 1> > >const&)
>>> ()#15 0x0000000000402e3d in Eigen::Matrix<float, -1, 1, 0, -1,
>>> 1>&Eigen::Matrix<float, -1, 1, 0,
>>>
>>> -1,1>::operator=<Eigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1, 1>
>>>
>>> >> >>(Eigen::ReturnByValue<Eigen::internal::solve_retval_base<Eigen::HouseholderQR<Eigen::Matrix<float,-1,
>>> -1, 0, -1, -1> >, Eigen::Matrix<float, -1, 1, 0, -1, 1> > >const&)
>>> ()#16 0x000000000040148d in main ()
>>>
>>> Thanks
>>> --
>>> ricard
>>> http://twitter.com/ricardmp
>>> http://www.ricardmarxer.com
>>> http://www.caligraft.com
>>
>>
>>
>>
>> --
>> Adolfo Rodríguez Tsouroukdissian
>> Robotics engineer
>> adolfo.rodriguez@xxxxxxxxxxxxxxxx
>> http://www.pal-robotics.com
>>
>> PAL ROBOTICS S.L
>> c/ Pujades 77-79, 4º4ª
>> 08005 Barcelona, Spain.
>> Tel. +34.93.414.53.47
>> Fax.+34.93.209.11.09
>>
>> AVISO DE CONFIDENCIALIDAD: Este mensaje y sus documentos adjuntos, pueden
>> contener información privilegiada y/o confidencial que está dirigida
>> exclusivamente a su destinatario. Si usted recibe este mensaje y no es el
>> destinatario indicado, o el empleado encargado de su entrega a dicha
>> persona, por favor, notifíquelo inmediatamente y remita el mensaje original
>> a la dirección de correo electrónico indicada. Cualquier copia, uso o
>> distribución no autorizados de esta comunicación queda estrictamente
>> prohibida.
>>
>> CONFIDENTIALITY NOTICE: This e-mail and the accompanying document(s) may
>> contain confidential information which is privileged and intended only for
>> the individual or entity to whom they are addressed.  If you are not the
>> intended recipient, you are hereby notified that any disclosure, copying,
>> distribution or use of this e-mail and/or accompanying document(s) is
>> strictly prohibited.  If you have received this e-mail in error, please
>> immediately notify the sender at the above e-mail address.
>
>



-- 
ricard
http://twitter.com/ricardmp
http://www.ricardmarxer.com
http://www.caligraft.com