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

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

2010/3/5 Adolfo Rodríguez Tsouroukdissian <adolfo.rodriguez@xxxxxxxxxxxxxxxx>:
>
>
> On Fri, Mar 5, 2010 at 4:18 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
> wrote:
>>
>> 2010/3/5 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
>> >
>> >
>> > On Fri, Mar 5, 2010 at 3:36 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
>> > wrote:
>> >>
>> >> 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?
>> >
>> > yes it is. for not too big matrices we have alloca. yes I know currently
>> > only for linux... If that's really a pb, there are many solutions:
>> >
>> > 1- we can still allocate on the stack the required blocks *outside* the
>> > matrix product function and pass them to the matrix product function.
>> > That
>> > must be done outside because the underlying heavy matrix product
>> > function
>> > should be instanciated only once per scalar type.
>> >
>> > 2- another solution: in the matrix product function we declare a (only
>> > when
>> > alloca is disabled):
>> >
>> > Scalar stackmemory[16*16*2];  // no heap alloc for matrices up to 16x16
>> > if the required memory for the blocks is bigger than 16*16*2 then do
>> > heap
>> > allocation...
>>
>> Solution 2 sounds great to me. You could even implement that in the
>> ei_aligned_stack_alloc macro, no? (in the non-linux case). So
>> ei_aligned_stack_alloc would guarantee on all platforms to never cause
>> heap alloc below a certain threshold.
>>
>> What I really care about is that we can say something simple and clear
>> along the lines of "small enough fixed size matrices never cause heap
>> allocation".
>>
>
> And what about small enough dynamic sized matrices?

i don't really see what we can do there. what some libraries
(armadillo, i think) do is add a static array of, say, 256 scalars to
their dynamic matrix class so that small enough matrices don't need a
malloc. But if you're really serious about avoiding mallocs, that
means you have to make sure that you do stay under that
compile-time-fixed size threshold... in which case the MaxRows /
MaxCols approach is actually a better way of achieving the same thing!

To summarize, after the little change we're discussing here with Gael,
Eigen should actually guarantee that small enough MaxRows / MaxCols
values do guarantee that no malloc occurs. I don't see how to do
anything better with our API. As you note, any attempt to put the user
more in control of that ends up being very ugly API wise as he has to
take care of allocating all the temporaries...

Benoit


>
>
>>
>> Benoit
>>
>> >
>> > 3- the user can still define EIGEN_CACHEFRIENDLY_PRODUCT_THRESHOLD to a
>> > big
>> > value to disable the use of the efficient product for matrices of medium
>> > sizes with a lost of performance...
>> >
>> >
>> > btw, I have a bench program which instanciates and compares the
>> > coeff-based
>> > product to the optimized one for all triplet of fixed size matrices, for
>> > sizes between 1 and 9 => 2*9^3 product instanciations !!! The goal is to
>> > find the ideal threshold for each platform. hm... I should also add the
>> > transposed versions => x4 more instanciations, and versions for
>> > double...
>> > ouch!  that will take a day to compile :)
>> >
>> > gael
>> >
>> >
>> >
>> >>
>> >> 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.
>> >> >>> >>
>> >> >>> >
>> >> >>>
>> >> >>>
>> >> >
>> >> >
>> >>
>> >>
>> >
>> >
>>
>>
>