Re: [eigen] about JacobiSVD's options

[Gael Guennebaud <gael.guennebaud@xxxxxxxxx>]

wow I did not know FullPivotingHouseholderQR was so heavy to compile !

So I tried to find the compilation bottleneck and fyi the most
expensive lines are clearly the 2 calls to applyHouseholderOnTheLeft
in compute() and matrixQ().

Actually, we can speedup a bit the compilation of applyHouseholder* if
we temporarily overwrite the first coeff of the vector by 1. This
strategy requires that the essential part is preceded by a valid
scalar value, that is currently always the case.

Then applyHouseholder boils down to a matrix-vector product. Since the
latter is currently instantiated for each different type of the result
(Matrix / Block / VectorBlock), one possibility to further amortize
the compilation of applyHouseholder is to make the matrix-vector
product routine depends only on the scalar type (and storage order).

gael.

On Tue, Sep 15, 2009 at 5:38 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:
> my paste was missing the last line, here it is complete:
>
> === 23:23:18 ~$ g++ a.cpp -o a -I eigen2 -O2 && time g++ a.cpp -o a -I
> eigen2 -O2 -DSVDOPTIONS=Square && ls -l a
>
> real    0m2.460s
> user    0m2.348s
> sys     0m0.108s
> -rwxr-xr-x 1 bjacob users 51007 sept. 15 23:23 a
> === 23:23:29 ~$ g++ a.cpp -o a -I eigen2 -O2 && time g++ a.cpp -o a -I
> eigen2 -O2 && ls -l a
>
> real    0m6.530s
> user    0m6.372s
> sys     0m0.152s
> -rwxr-xr-x 1 bjacob users 142180 sept. 15 23:23 a
>
> Benoit
>
> 2009/9/15 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>:
>> Hi,
>>
>> 2009/9/15 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:
>>> hi,
>>>
>>> the "Options" template parameter of JacobiSVD seems to be over-complicated.
>>>
>>> What about removing the Square/MoreColsThanRows/etc. stuff from the
>>> Option template parameter ? For small fixed sizes they can be
>>> automatically extracted at compile time, and for dynamic sizes .. well
>>> who care ? Moreover in the worst case, if the user use various matrix
>>> shapes he can generate 3 instances of JacobiSVD for the same matrix
>>> type...
>>
>> The reason for making these template parametes is to avoid compiling
>> useless code: so it allows to compile much faster, and produce much
>> smaller code.
>>
>> When you give JacobiSVD a rectangular matrix, it does a full-pivoting
>> QR to reduce to the case of a square matrix. This step has to be done
>> differently depending on whether m>=n or m<=n. I already have made
>> sure that these 2 paths use the same instantiation of
>> FullPivotingHouseholderQR, so it is only instantiated once. Still,
>> that instantiation is relatively expensive (as is any householder QR
>> --- the full pivoting version is only marginally more expensive to
>> compile).
>>
>> That's why I provided the user a way to avoid compiling this code if
>> it's not going to be used. By default the code is compiled and the
>> user doesn't need to care about anything, just use
>> JacobiSVD<MatrixXf>, but an advanced user may be interested in that.
>>
>> Here is a benchmark for compilation times and code size. (attached a.cpp)
>>
>> Result:
>> === 23:23:18 ~$ g++ a.cpp -o a -I eigen2 -O2 && time g++ a.cpp -o a -I
>> eigen2 -O2 -DSVDOPTIONS=Square && ls -l a
>>
>> real    0m2.460s
>> user    0m2.348s
>> sys     0m0.108s
>> -rwxr-xr-x 1 bjacob users 51007 sept. 15 23:23 a
>>
>> === 23:23:29 ~$ g++ a.cpp -o a -I eigen2 -O2 && time g++ a.cpp -o a -I
>> eigen2 -O2 && ls -l a
>>
>> real    0m6.530s
>> user    0m6.372s
>> sys     0m0.152s
>>
>> So, passing the Square template parameter almost divides compilation
>> times and code size by 3.
>>
>> (g++ 4.4.1 x86)
>>
>>>
>>> Also, I'm wondering whether the ComputeU and ComputeV parameters could
>>> be runtime parameters ? I doubt there is any performance difference,
>>> but of course to be sure we should bench it. If I have time I'll do
>>> it.
>>
>> Hm, that makes more sense indeed, we need to bench, not only
>> performance but code size and compilation times.
>> At the same time, making them runtime params is good in itself as it
>> can mean fewer template instantiations, precisely.
>>
>> Benoit
>>
>
>
>