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

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]



On Mon, Mar 8, 2010 at 10:55 PM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:


On Mon, Mar 8, 2010 at 10:45 PM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:


2010/3/8 Adolfo Rodríguez Tsouroukdissian <dofo79@xxxxxxxxx>



On Mon, Mar 8, 2010 at 3:13 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:
2010/3/8 Hauke Heibel <hauke.heibel@xxxxxxxxxxxxxx>:
> That may be because alloca is not yet implemented on all systems. Are
> you by chance on a windows system!? I will fix that soon for windows.
>
> Just take a look at ei_aligned_stack_new in Memory.h

I guess that the point that is surprising Adolfo is that any runtime
allocation (alloca or malloc) gets called at all, while the matrix has
a very small, known-at-compile-time, max size.

I'd agree that this should not happen, and I think that's exactly the
same problem that we discussed earlier: the low-level matrix-matrix
product function allocates a workspace without knowning the sizes at
compile time (since we don't want it to take any other template
parameters than just Scalar). We already discussed that the solution
would be to have this function take a 'workspace' parameter pointer,
letting the caller the responsibility to create the workspace.

It just needs Gael to find some time and implement that ;)

Then there might be a separate problem: if your problem only happens
when the sizes are Dynamic (keeping maxsize = 4) then that could be a
case of mis-using the sizes to create a temporary where the max-size
should be used instead. But a priori I expect your bug to happen also
with fully fixed size matrices, as we discussed earlier, with the
current Eigen, and we agreed it needed to be fixed :).

If I use a fully-fixed matrix type like Matrix3f no assertions are made. Maybe I should have said this in the previous post. I was expecting a similar behavior between a fully-fixed type and a similarly-sized matrix with compile-time max size.

indeed, that's a bug. The pb is that the MaxSizes are not taken into account. Should be easy to fix.

done.

I just pulled in the latest changes, but the issue still seems to be there. The attached patch uncomments the parts of the nomalloc test that were failing, so you can verify it. Anyway, thanks for the very fast reaction time.

Adolfo
 

gael
 

However, for fully dynamic sized matrices, e.g., MatrixXf, even if the matrix is 2x2, then it will take the path for large matrices and trigger a dynamic stack (or heap) allocation. This is because I don't want to add an extra runtime tests for almost improbable cases.

If the users knows its fully dynamic matrices will be such small, then he can still use a.lazyProduct(b) to enforce the use of the coeff based product.

gael
 

Right now one of the eigenvalues decompositions is failing the nomalloc test not because of the decomposition per se, but because it performs a product that allocates on the stack.

Adolfo
 

Benoit

>
> Regards,
> Hauke
>
> 2010/3/8 Adolfo Rodríguez Tsouroukdissian <adolfo.rodriguez@xxxxxxxxxxxxxxxx>:
>>
>>
>> On Fri, Mar 5, 2010 at 2:01 PM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
>> wrote:
>>>
>>>
>>> 2010/3/5 Adolfo Rodríguez Tsouroukdissian <dofo79@xxxxxxxxx>
>>>>
>>>>
>>>> On Thu, Mar 4, 2010 at 8:00 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxxx>
>>>> 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).
>>>
>>> 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...
>>
>>
>> I was just writing the unit test associated to the patch that I'm preparing,
>> and I stumbled upon something that I'd like to understand better.
>>
>> #define EIGEN_STACK_ALLOCATION_LIMIT 0
>> #define EIGEN_NO_MALLOC
>>
>> #include <Eigen/Core>
>>
>> int main( int argc, char** argv )
>> {
>>   const int maxSize = 4; // Very small matrices
>>   const int size    = 3;
>>
>>   typedef Eigen::Matrix<float,
>>                         Eigen::Dynamic, Eigen::Dynamic,
>>                         Eigen::ColMajor | Eigen::AutoAlign,
>>                         maxSize, maxSize> Matrix;
>>
>>   const Matrix A(Matrix::Random(size, size));
>>   const Matrix saA = A.adjoint() * A; // Asserts because of
>> EIGEN_STACK_ALLOCATION_LIMIT 0
>>
>>   return 0;
>> }
>>
>> Is this behavior expected?, and if so, can it be prevented?. The culprit is
>> somewhere deep within the general matrix matrix product implementation, but
>> I'm not (yet) familiar enough with eigen internals to quickly determine
>> what's going on.
>>
>> TIA,
>>
>> Adolfo
>>
>>>
>>> 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.
>>>>> >>
>>>>> >
>>>>>
>>>>>
>>>
>>
>
>
>






# HG changeset patch
# User Adolfo Rodriguez Tsouroukdissian <adolfo.rodriguez@xxxxxxxxxxxxxxxx>
# Date 1268128052 -3600
# Node ID 6d783d658d44a4ef284c1ac1ca4d453241e7bdb7
# Parent  5a397fe1e637aad6900c1faf94c8ca09aaf80d7a
Uncommented parts of nomalloc test that were failing because of stack allocations in the matrix-matrix product implementation

diff -r 5a397fe1e637 -r 6d783d658d44 test/nomalloc.cpp
--- a/test/nomalloc.cpp	Tue Mar 09 09:04:21 2010 +0100
+++ b/test/nomalloc.cpp	Tue Mar 09 10:47:32 2010 +0100
@@ -100,9 +100,7 @@
 
   const Matrix A(Matrix::Random(size, size));
   const ComplexMatrix complexA(ComplexMatrix::Random(size, size));
-//   const Matrix saA = A.adjoint() * A; // NOTE: This product allocates on the stack. The two following lines are a kludgy workaround
-  Matrix saA(Matrix::Constant(size, size, 1.0));
-  saA.diagonal().setConstant(2.0);
+  const Matrix saA = A.adjoint() * A;
 
   // Cholesky module
   Eigen::LLT<Matrix>  LLT;  LLT.compute(A);
@@ -111,7 +109,7 @@
   // Eigenvalues module
   Eigen::HessenbergDecomposition<ComplexMatrix> hessDecomp;        hessDecomp.compute(complexA);
   Eigen::ComplexSchur<ComplexMatrix>            cSchur(size);      cSchur.compute(complexA);
-  Eigen::ComplexEigenSolver<ComplexMatrix>      cEigSolver;        //cEigSolver.compute(complexA); // NOTE: Commented-out because makes test fail (L135 of ComplexEigenSolver.h has a product that allocates on the stack)
+  Eigen::ComplexEigenSolver<ComplexMatrix>      cEigSolver;        cEigSolver.compute(complexA);
   Eigen::EigenSolver<Matrix>                    eigSolver;         eigSolver.compute(A);
   Eigen::SelfAdjointEigenSolver<Matrix>         saEigSolver(size); saEigSolver.compute(saA);
   Eigen::Tridiagonalization<Matrix>             tridiag;           tridiag.compute(saA);

Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/