bugGNU Octave - Bugs: bug #49940, The svd function takes very long...

 
 

bug #49940: The svd function takes very long time for big matrices

Submitted by:  Saleh <sabmab>
Submitted on:  Tue 27 Dec 2016 10:55:26 AM UTC  
 
Category:  Performance Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  saleh Open/Closed:  Open
Release:  dev Operating System:  GNU/Linux

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Fri 25 Jan 2019 10:12:22 PM UTC, comment #10: 

Okay, so can we shut this bug back down since the delay is all upstream?

Rik <rik5>
Project Administrator
Fri 25 Jan 2019 08:09:15 PM UTC, comment #9: 

I modified liboctave/numeric/svd.cc to print out the elapsed time directly around both calls to the DGESVD function, and ran the same benchmark script.

The extra output shows that virtually all of the elapsed time taken by each call to 'svd' at the Octave interpreter level is due to elapsed time in the DGESVD function itself and not any extra overhead that Octave is adding.

SVD_DRIVER: gesvd, Matrix Size: [2000 2000]
DGESVD[1]: elapsed time = 5.60284e-05
DGESVD[2]: elapsed time = 1.39169
bm1 =  1.4111
DGESVD[1]: elapsed time = 7.15256e-06
DGESVD[2]: elapsed time = 69.9751
bm2 =  70.040
SVD_DRIVER: gesdd, Matrix Size: [2000 2000]
bm21 =  1.6698
bm22 =  2.6572

Mike Miller <mtmiller>
Project Administrator
Fri 25 Jan 2019 07:11:52 PM UTC, comment #8: 

Re-running benchmark from Comment 3 on Xeon W3530  @ 2.80GHz 4c/8th with the latest multithreaded openblas I got:

LD_PRELOAD=~dima/src/OpenBLAS/libopenblas.so OPENBLAS_NUM_THREADS=4 ./run-octave -q -f
octave:1> a=randn(4000);
octave:2> tic; inv(a); toc
Elapsed time is 4.07135 seconds.
octave:3> x = rand (2e3);
octave:4>
octave:4> svd_driver ("gesvd");
octave:5> printf ("SVD_DRIVER: gesvd, Matrix Size: %s\n", mat2str (size (x)));
SVD_DRIVER: gesvd, Matrix Size: [2000 2000]
octave:6>
octave:6> tic; sv = svd (x); bm1 = toc
bm1 =  3.3586
octave:7> tic; [u,s,v] = svd (x); bm2 = toc
bm2 =  89.112
octave:8>
octave:8> svd_driver ("gesdd");
octave:9> printf ("SVD_DRIVER: gesdd, Matrix Size: %s\n", mat2str (size (x)));
SVD_DRIVER: gesdd, Matrix Size: [2000 2000]
octave:10>
octave:10> tic; sv2 = svd (x); bm21 = toc
bm21 =  3.3618
octave:11> tic; [u2,s2,v2] = svd (x); bm22 = toc
bm22 =  5.9142

3.3 sec / 89.112 sec seems to be much bigger difference than
what was reported in Comment 3. There are many things has
changed (newer blas/lapack, newer compiler, newer kernel,  etc..)
 and I just want to make sure it is not due to changes in octave code.

I also noticed that gesvd code runs essentially single-threaded.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Fri 25 Jan 2019 06:59:34 PM UTC, comment #7: 

Re-opening this bug report.  The 'gesdd' driver can occasionally produce utterly incorrect values. so switching to this driver for performance improvement is no longer a possibility.  See bug #55564 which is now linked to this report.

Until bug #55564 is resolved upstream in LAPACK, it would be worthwhile to benchmark/profile Octave to determine if there is anything on our side of the API that can be improved with respect to performance.

Rik <rik5>
Project Administrator
Thu 29 Dec 2016 12:13:35 AM UTC, comment #6: 

I changed the default driver in Octave to gesdd which is 5X faster in this cset (http://hg.savannah.gnu.org/hgweb/octave/rev/750c8b4b7164).  The original reporter can either build from the development sources, or just switch to "gesdd" using the svd_driver function with the current version of Octave (4.2.0).

Rik <rik5>
Project Administrator
Wed 28 Dec 2016 06:29:57 PM UTC, comment #5: 

See also bug #29487.

John W. Eaton <jwe>
Project Administrator
Wed 28 Dec 2016 05:34:15 PM UTC, comment #4: 

I'm going to ask on the Octave Maintainer's list about switching the core algorithm to gesdd.

Rik <rik5>
Project Administrator
Wed 28 Dec 2016 05:09:24 PM UTC, comment #3: 

I don't think the large slowdown is attributable to Octave.  Octave is an interpreter which relies on other solid linear algebra libraries like BLAS and LAPACK to do the real work.  The svd function is rather special in that there are at least two different library functions in LAPACK that could be used.  Octave allows you to switch which function is called with the svd_driver() function.  Try 'help svd_driver' to get the documentation.

I coded up a test to see if svd driver makes a difference and it definitely does for the test case used here.  The code is shown below and attached as tst_svd_driver.m

x = rand (2e3);

svd_driver ("gesvd");
printf ("SVD_DRIVER: gesvd, Matrix Size: %s\n", mat2str (size (x)));

tic; sv = svd (x); bm1 = toc
tic; [u,s,v] = svd (x); bm2 = toc

svd_driver ("gesdd");
printf ("SVD_DRIVER: gesdd, Matrix Size: %s\n", mat2str (size (x)));

tic; sv2 = svd (x); bm21 = toc
tic; [u2,s2,v2] = svd (x); bm22 = toc

The results are

tst_svd_driver
SVD_DRIVER: gesvd, Matrix Size: [2000 2000]
bm1 =  3.0383
bm2 =  28.750
SVD_DRIVER: gesdd, Matrix Size: [2000 2000]
bm21 =  3.1114
bm22 =  6.0188

Using gesdd the slowdown is only 2X which is probably acceptable.  This also seems to be roughly the slowdown that Matlab experiences for the 1e3 and 2e3 cases.

(file #39325)

Rik <rik5>
Project Administrator
Wed 28 Dec 2016 02:13:28 AM UTC, comment #2: 

results of octave compared to matlab

>> x = rand (1e3);
>> svd (x); % warmup
>> tic; sv      = svd (x); bm1 = toc
bm1 =  0.21399  %matlab 0.1721
>> tic; [u,s,v] = svd (x); bm2 = toc
bm2 =  11.840   %matlab 0.3880  approx 30x slowdown
>> tic; [s]     = svd (x); bm3 = toc
bm3 =  0.20974  %matlab 0.1556
>>
>> x = rand (2e3);
>> tic; sv      = svd (x); bm1 = toc
bm1 =  1.7601   %matlab 1.3173
>> tic; [u,s,v] = svd (x); bm2 = toc
bm2 =  96.207   %matlab 2.4857  approx 38x slowdown
>> tic; [s]     = svd (x); bm3 = toc
bm3 =  1.6928   %matlab 1.2874
>>
>> x = rand (3e3);
>> tic; sv      = svd (x); bm1 = toc
bm1 =  6.8742   %matlab 5.2722
>> tic; [u,s,v] = svd (x); bm2 = toc
bm2 =  353.66   %matlab 8.3250  approx 40x slowdown
>> tic; [s]     = svd (x); bm3 = toc
bm3 =  7.6766   %matlab 5.2956

I found in the svd.cc file at line 235 some relevant part (for real matrix)

if (nargout == 0 || nargout == 1) // if number of output arguments is one
    retval(0) = sigma.extract_diag ();
else
    retval = ovl (result.left_singular_matrix (),
        sigma,
    result.right_singular_matrix ());
// results is of type octave::math::svd<Matrix>

I belive the culprit is one of two things
a- ovl :it is copying the matrix, instead of copying its address
b- the algorithms  result.left_singular_matrix and right_singular_matrix are very expensive to evaluate in octave.

Saleh <sabmab>
Tue 27 Dec 2016 05:06:41 PM UTC, comment #1: 

I benchmarked using the script tst_svd.m below

x = rand (2e3);

tic; sv = svd (x); bm1 = toc
tic; [u,s,v] = svd (x); bm2 = toc

I tried 1e3, 2e3, and 3e3 for the size of the matrices.  With the developent version of Octave I get

octave:1> tst_svd
bm1 =  0.31309
bm2 =  3.2931
octave:2> tst_svd
bm1 =  2.8148
bm2 =  28.110
octave:3> tst_svd
bm1 =  9.4242
bm2 =  106.77

As you can see, requesting more than just the singular values is about 10X slower.  Could you try running the same script in Matlab to get an idea of the size of the performance hit there.

Rik <rik5>
Project Administrator
Tue 27 Dec 2016 10:55:26 AM UTC, original submission:  

When running the svd function without returning parameter it perform well (like Matlab).

tic;
svd(rand(3000));
toc;

When adding output parameters, the performance drops significantly(40x, in this case), which is not the case in Matlab.

tic;
[u,s,v]=svd(rand(3000));
toc;

I didn't see this behavior for other functions such as the "inv" function.

 
Saleh <sabmab>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #39325:  tst_svd_driver.m added by rik5 (337B - d2l/unknowntype)

 

Digest:
   bug dependencies.

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by sabmab (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-01-25 rik5 StatusFixed => Confirmed
        Open/ClosedClosed => Open
        Dependencies- => Depends on bugs #55564
    2016-12-29 rik5 StatusConfirmed => Fixed
        Open/ClosedOpen => Closed
    2016-12-28 rik5 Attached File- => Added tst_svd_driver.m, #39325
    2016-12-27 rik5 StatusNone => Confirmed

    Back to the top


    Powered by Savane 3.5