bugGNU Octave - Bugs: bug #45890, Sparse A*x and A+B are a bit slow

 
 

bug #45890: Sparse A*x and A+B are a bit slow

Submitted by:  Ceral Paquet <octavebugs>
Submitted on:  Sun 06 Sep 2015 08:39:55 PM UTC  
 
Category: LibrariesSeverity: 3 - Normal
Priority: 3 - LowItem Group: Performance
Status: Need InfoAssigned to: None
Originator Name: Open/Closed: Open
Release: devOperating 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 Jump to the original submission)

Fri 11 Sep 2015 02:55:08 PM UTC, comment #10:

In the example, a_nr is very large compared to a_nc, but still A*x takes less than a second. I think it is an accetable time to wait for before interruption. Anyway, if you modify x into

then I see, for A*x, 9 seconds for Matlab and 40 seconds for Octave 4.0.0. With the original vector x, 0.25 vs. 0.36.

Marco

Marco Caliari <caliari>
Project Member
Fri 11 Sep 2015 02:12:04 PM UTC, comment #9:

It would probably work OK in many cases, but what if a_nr is very large compared to a_nc? In that case, interrupting would be less responsive.

It would be easy enough to do some tests just to see whether removing it completely actually makes a significant difference.

Note that octave_quit is an inline function that just does

so it should just be checking a variable value and not performing an actual function call. Given the other things that happen in the inner loop in SPARSE_FULL_MUL, I'd be surprised if that makes a significant difference, but I suppose it could.

John W. Eaton <jwe>
Project Administrator
Fri 11 Sep 2015 01:51:28 PM UTC, comment #8:

Looking at SPARSE_FULL_MUL, the only thing I notice is

inside the loop over the number of rows of the second term of the multiplication (a vector in the test we are considering). I guess it allows to interrupt the calculation with a Ctrl+C. How much does it take? Wouldn't it enough to move it in the previous loop?

Marco

Marco Caliari <caliari>
Project Member
Tue 08 Sep 2015 10:30:55 AM UTC, comment #7:

FYI here is a comparison of your benchmark using octave's sparse and sparsersb:

In order to run these tests I modified your
benchmark code as follows:

Carlo de Falco <cdf>
Project Member
Tue 08 Sep 2015 09:41:08 AM UTC, comment #6:

Hi,

Not sure whether you are interested but,
if you really care about the speed of
sparse matrix * vector operations, you may want
to try the sparsersb package (which links to librsb):

http://librsb.sourceforge.net

the speedup is usually very impressive and worth the time spent
in installing the library if you use sparse matrix * vector a lot.

Carlo de Falco <cdf>
Project Member
Tue 08 Sep 2015 09:09:41 AM UTC, comment #5:

The originators of the code are David Bateman, Andy Adler, and Jaroslav Hajek. Maybe you can get in contact with them regarding code improvements or feel encouraged to get your hands on the free code yourself.

I worked myself on sparse matrix functions (ILU, ICHOL) within Octave, thus I have a basic knowledge of the sparse matrix code. But anyway, Octave consists of thousands of lines of code, there is no point in first knowing all functions by heart to work on them, or to answer at the bug tracker.

Kai Torben Ohlhus <siko1056>
Project Member
Tue 08 Sep 2015 08:32:28 AM UTC, comment #4:

So... you misread and closed my bug report, and don't even know the code?

Ceral Paquet <octavebugs>
Tue 08 Sep 2015 08:14:32 AM UTC, comment #3:

The Octave core code is for my taste very ugly and hardly maintainable, if you want to change something regarding maintainability even commenting stuff would be very helpful!

I figured out two promising macros SPARSE_FULL_MUL and SPARSE_SPARSE_MUL in

liboctave/operators/Sparse-op-defs.h

If you want to get into the code, I recommend you in Linux the grep command

to get ideas where something could be implemented.

Kai Torben Ohlhus <siko1056>
Project Member
Tue 08 Sep 2015 07:13:58 AM UTC, comment #2:

Hi Kai,

I compiled Octave using ./configure on 64-bit Xubuntu (sadly, I still can't get --enable-64 to work). I left out all non-essential components such as SuiteSparse, so presumably octave is using this code?

~/octave-4.0.0/liboctave/array/Sparse*
~/octave-4.0.0/liboctave/array/MSparse*

I scanned them but can't really figure out what's going on. Are there 2 separate implementations of sparse array? E.g. where is A*x implemented? If you could start me off, I'd be happy to delve into it more - thanks.

(By the way I think you read the benchmarks wrong - Octave is much faster then Matlab at sparse creation but twice as slow at A+B and 50% slower at A*x.)

Ceral Paquet <octavebugs>
Mon 07 Sep 2015 05:31:14 AM UTC, comment #1:

Your benchmark looks good to me! Octave's sparse matrix operations are not by factor 2 slower than MATLAB, and even outperform MATLAB in A'. Only the sparse matrix creation looks improvable to me.

But to really understand your benchmarks you need to tell more about your system, e.g. which SuiteSparse (https://packages.debian.org/source/jessie/suitesparse) you have installed, the MATLAB/Octave version, did you do any performance tweaks to MATLAB/Octave?

If you was interested in sparse matrix computations within Octave you might consider contributing to Octave and find out the potential bottle necks in your performed computation.

http://wiki.octave.org/Projects#Sparse_Matrices

Anyway, don't be shy to publish results like them!

Best,
Kai

Kai Torben Ohlhus <siko1056>
Project Member
Sun 06 Sep 2015 08:39:55 PM UTC, original submission:

I just was doing some comparisons of sparse matrix operations and noticed some seem a bit slower than Matlab. Not serious but kind of odd considering they are probably using very similar C++ code.

Octave results

N=1000000 NNZ=20000000 NRUNS=5
sparse: 2.709228 (0.011811)
2*A : 0.222145 (0.000448)
A' : 1.776688 (0.044113)
A+B : 1.081774 (0.007834)
A*x : 0.652453 (0.002009)
A'*x : 0.292271 (0.000704)

Matlab results

N=1000000 NNZ=20000000 NRUNS=5
sparse: 8.625574 (0.008490)
2*A : 0.169647 (0.002336)
A' : 2.126985 (0.025129)
A+B : 0.543265 (0.001062)
A*x : 0.426534 (0.002292)
A'*x : 0.290045 (0.001137)

Code
Ceral Paquet <octavebugs>

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by mtmiller (Updated the item)
  • -unavailable- added by jwe (Posted a comment)
  • -unavailable- added by caliari (Posted a comment)
  • -unavailable- added by cdf (Posted a comment)
  • -unavailable- added by siko1056 (Posted a comment)
  • -unavailable- added by octavebugs (Submitted the item)
  •  

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

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 8 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 22 Dec 2015 02:58:03 PM UTCmtmillerCategoryNone=>Libraries
    Tue 08 Sep 2015 09:09:41 AM UTCsiko1056StatusWont Fix=>Need Info
      Open/ClosedClosed=>Open
      Release4.0.0=>dev
    Mon 07 Sep 2015 05:31:14 AM UTCsiko1056Priority5 - Normal=>3 - Low
      Item GroupNone=>Performance
      StatusNone=>Wont Fix
      Open/ClosedOpen=>Closed

    Back to the top


    Powered by Savane 3.1-cleanup1