Re: [eigen] Propagating Max*AtCompileTime template parameters to decompositions

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

2010/3/5 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
>
>
> 2010/3/5 Adolfo Rodríguez Tsouroukdissian <dofo79@xxxxxxxxx>
>>
>>
>> On Thu, Mar 4, 2010 at 8:00 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
>> wrote:
>>>
>>> One more thought.
>>>
>>> The "fixed sizes are guaranteed to not cause malloc's" principle only
>>> applies for not-too-large sizes. Let me explain. For large enough
>>> sizes (typically, above 200x200, but that is highly variable), the
>>> matrix-matrix product implementation works on blocks that fit in the
>>> CPU cache. These blocks are allocated with ei_aligned_stack_alloc
>>> which on non-Linux translates to a malloc (or friends).
>>>
>>> So in such unit tests, you should set the MaxSizes to some values that
>>> are significantly smaller than at least the default cache size
>>> (256x256 for float, but that could vary in the future). Just to be
>>> safe and since that only makes the test run faster, stay within very
>>> small sizes like 16x16...
>>
>> My use case requires matrices smaller than 50x50, usually half that size,
>> so we're good here :). For the unit test I'll make them 16x16 floats, no
>> problem.
>
> FYI, the optimized matrix product which requires dynamic allocation starts
> to be used for 8x8 matrices (even 4x4 on AltiVec).

What?! How then can we guarantee our users that at least for
not-too-big fixed size matrices, no malloc occurs?

Is this really a performance improvement even for such small sizes?

Benoit

>
> So in your case, if you are running linux then alloca is used and you are
> fine. Otherwise, heap allocation occurs. If that's really an issue we can
> think about solutions...
>
> gael
>
>>
>> Adolfo
>>
>>>
>>> Benoit
>>>
>>> 2010/3/4 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>:
>>> > 2010/3/4 Adolfo Rodríguez Tsouroukdissian <dofo79@xxxxxxxxx>:
>>> >>
>>> >>
>>> >> On Thu, Mar 4, 2010 at 6:00 PM, Benoit Jacob
>>> >> <jacob.benoit.1@xxxxxxxxx>
>>> >> wrote:
>>> >>>
>>> >>> Supreme refinement is to add a unit test for that. We already have
>>> >>> the
>>> >>> skeleton in the nomalloc test (test/nomalloc.cpp). Indeed, when
>>> >>> EIGEN_NO_MALLOC is defined, any heap allocation will cause an assert
>>> >>> failure, which in the context of unit tests we convert into an
>>> >>> exception.
>>> >>>
>>> >>> So don't hesitate to expand the nomalloc.cpp test, just with new
>>> >>> executable targets (CALL_SUBTEST_x for a new value of x up to 16) so
>>> >>> that no single executable gets too big. Testing only 'float' is good
>>> >>> enough.
>>> >>
>>> >>
>>> >> I was just thinking of that. I'll try to squeeze some time for that,
>>> >> too ;).
>>> >> Thanks for pointing me to the skeleton, that will speed up things.
>>> >> Should
>>> >> EIGEN_STACK_ALLOCATION_LIMIT 0 be defined as well, or am I good to go
>>> >> with
>>> >> only EIGEN_NO_MALLOC?.
>>> >
>>> > #define EIGEN_STACK_ALLOCATION_LIMIT 0 is really important. Indeed, on
>>> > Linux, this is really a stack allocation hence bypasses malloc
>>> > completely. So if you don't define this to 0, you could have a unit
>>> > test that passes on Linux but fails (because a heap allocation
>>> > happens) on other platforms.
>>> >
>>> > Benoit
>>> >
>>> >> The tests I've been playing with were triggering
>>> >> assertions made by EIGEN_NO_MALLOC only.
>>> >>
>>> >>>
>>> >>> Benoit
>>> >>>
>>> >>> 2010/3/4 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>:
>>> >>> > 2010/3/4 Adolfo Rodríguez Tsouroukdissian <dofo79@xxxxxxxxx>:
>>> >>> >>
>>> >>> >>
>>> >>> >> On Thu, Mar 4, 2010 at 5:25 PM, Benoit Jacob
>>> >>> >> <jacob.benoit.1@xxxxxxxxx>
>>> >>> >> wrote:
>>> >>> >>>
>>> >>> >>> Hi Adolfo,
>>> >>> >>>
>>> >>> >>> Many thanks for this patch. It's been sitting in the back of my
>>> >>> >>> mind
>>> >>> >>> nagging me for a while :) These fixes are definitely wanted.
>>> >>> >>>
>>> >>> >>> Just 2 things:
>>> >>> >>>
>>> >>> >>> 1. All the MatrixType:: is a bit heavy so could you please
>>> >>> >>> introduce
>>> >>> >>> enums like is being done in ColPivHouseholderQR.h, in other
>>> >>> >>> decompositions? So MatrixType::MaxBlabla becomes just MaxBlaBla..
>>> >>> >>
>>> >>> >> OK, no problem. The enum approach is definitely much cleaner. I
>>> >>> >> just
>>> >>> >> didn't
>>> >>> >> want to impose it if it was not used in some files :)
>>> >>> >>
>>> >>> >> One more thing, now that I'm on it, are there any other files that
>>> >>> >> I
>>> >>> >> might
>>> >>> >> have overlooked that could benefit from similar changes?
>>> >>> >
>>> >>> > Any decomposition is affected in the same way. Have you had a look
>>> >>> > at
>>> >>> > the Eigenvalues directory?
>>> >>> >
>>> >>> >
>>> >>> >>
>>> >>> >>>
>>> >>> >>> 2. You generated this patch with "diff" so it doesn't credit you,
>>> >>> >>> and
>>> >>> >>> you haven't written your commit msg. Could you please follow the
>>> >>> >>> instructions given there:
>>> >>> >>>
>>> >>> >>>
>>> >>> >>>
>>> >>> >>> http://eigen.tuxfamily.org/index.php?title=Developer%27s_Corner#Generating_a_patch
>>> >>> >>>
>>> >>> >>
>>> >>> >> Ack.
>>> >>> >>
>>> >>> >> Adolfo
>>> >>> >>
>>> >>> >>>
>>> >>> >>> Yes, this mailing list is the right place for such patches... the
>>> >>> >>> issue tracker is useful to report bugs without being immediately
>>> >>> >>> able
>>> >>> >>> to fix them.
>>> >>> >>>
>>> >>> >>> Benoit
>>> >>> >>>
>>> >>> >>>
>>> >>> >>> 2010/3/4 Adolfo Rodríguez Tsouroukdissian <dofo79@xxxxxxxxx>:
>>> >>> >>> > Hi all,
>>> >>> >>> >
>>> >>> >>> > I've been performing some tests with dynamic matrices that have
>>> >>> >>> > a
>>> >>> >>> > compile-time max size, and found out that for most matrix
>>> >>> >>> > decompositions,
>>> >>> >>> > the MaxRowsAtCompileTime and MaxColsAtCompileTime template
>>> >>> >>> > parameters of
>>> >>> >>> > the
>>> >>> >>> > input matrix are not propagated to the decomposition's members
>>> >>> >>> > and
>>> >>> >>> > temporaries. This leads to undesired and preventable heap
>>> >>> >>> > allocations.
>>> >>> >>> > The
>>> >>> >>> > following is a minimal example of what I mean:
>>> >>> >>> >
>>> >>> >>> > typedef Matrix<double, dynamic, dynamic, 0, 10, 10> Mat;
>>> >>> >>> > Mat A(Mat::Random(5, 5));
>>> >>> >>> >
>>> >>> >>> > FullPivLU<Mat> ldlt(A); // Allocates 4 temps
>>> >>> >>> > LDLT<Mat> ldlt(A);      // Allocates 3 temps
>>> >>> >>> >
>>> >>> >>> > I'm attaching a patch against the devel branch (commit
>>> >>> >>> > 2589:8a8f4e9e04bf)
>>> >>> >>> > that deals with this issue for the Cholesky, LU, QR and SVD
>>> >>> >>> > modules.
>>> >>> >>> > Since
>>> >>> >>> > most of these modules are experimental and undergoing heavy
>>> >>> >>> > work,
>>> >>> >>> > the
>>> >>> >>> > style
>>> >>> >>> > of the modifications changes form file to file (some use
>>> >>> >>> > convenience
>>> >>> >>> > enums,
>>> >>> >>> > some not). However, I tried to stay consistent within the
>>> >>> >>> > context of
>>> >>> >>> > each
>>> >>> >>> > file. Please let me know your thoughts on the matter.
>>> >>> >>>
>>> >>> >>> Yes so actually, please introduce enums everywhere :)
>>> >>> >>>
>>> >>> >>> > One very specific
>>> >>> >>> > note: in line 65 of HouseHolderQR.h I left the Options template
>>> >>> >>> > parameter
>>> >>> >>> > as-is, but don't know if it should be changed to that of
>>> >>> >>> > MatrixType.
>>> >>> >>>
>>> >>> >>> Great catch! Please change that to Options (as defined on line
>>> >>> >>> 57).
>>> >>> >>>
>>> >>> >>> Thanks
>>> >>> >>> Benoit
>>> >>> >>>
>>> >>> >>> >
>>> >>> >>> > Cheers,
>>> >>> >>> >
>>> >>> >>> > Adolfo.
>>> >>> >>> >
>>> >>> >>> > P.S. Is there a better way to submit small patches, something
>>> >>> >>> > like a
>>> >>> >>> > bugtracker, or is this the currently recommended way?
>>> >>> >>> >
>>> >>> >>> > --
>>> >>> >>> > Adolfo Rodríguez Tsouroukdissian, Ph. D.
>>> >>> >>> >
>>> >>> >>> > Robotics engineer
>>> >>> >>> > PAL ROBOTICS S.L
>>> >>> >>> > http://www.pal-robotics.com
>>> >>> >>> > 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.
>>> >>> >>> >
>>> >>> >>>
>>> >>> >>>
>>> >>> >>
>>> >>> >>
>>> >>> >
>>> >>>
>>> >>>
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> Adolfo Rodríguez Tsouroukdissian, Ph. D.
>>> >>
>>> >> Robotics engineer
>>> >> PAL ROBOTICS S.L
>>> >> http://www.pal-robotics.com
>>> >> 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.
>>> >>
>>> >
>>>
>>>
>
>