bugGNU Octave - Bugs: bug #41426, OOM for issymmetric on sparse...

 
 

bug #41426: OOM for issymmetric on sparse matrices

Submitter:  David Spies <dspyz>
Submitted:  Sun 02 Feb 2014 04:24:41 AM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Mon 03 Feb 2014 05:12:17 PM UTC, comment #5: 

Thanks,

I'm a little confused though
How is that possible?  issparse(x) should just check a single bit or boolean or type or something, whereas the possibility of early termination as provided by 'any' can avoid examining nearly all the elements (if the matrix isn't symmetric).

Is the implicit copy operation associated with passing an argument to a function not being elided for issparse?
For that matter, does octave do copy ellision for functions which don't modify their inputs?  Is it something I should worry about?

Or is it just the case that in practice this method is generally only used inside an assert statement (in which case it's expected to always hold, so using 'any' doesn't provide any benefit)?

David Spies <dspyz>
Mon 03 Feb 2014 04:27:38 AM UTC, comment #4: 

I did some benchmarking and introducing the "issparse (x)" test actually slows things down more significantly than just using the proposed patch.  I also benchmarked the proposed patch against the existing code for full matrices and I find very little difference (< 2% and within the range of fluctuations that exist from run to run).  With that in mind I applied the patch here (http://hg.savannah.gnu.org/hgweb/octave/rev/7c0db9c4e454).

Rik <rik5>
Group administrator
Sun 02 Feb 2014 04:41:26 PM UTC, comment #3: 

Ok, thanks

How do you test the efficiency?

David Spies <dspyz>
Sun 02 Feb 2014 04:31:22 PM UTC, comment #2: 



retval = any ((x != x.')(:));


seems slightly faster for full matrices and about the same speed as the original code, but the "(:)" creates an out of memory error for large sparse matrices as well. The difference in speed for the two versions for full matrices only seems to be about 5% so maybe we should just take your patch as is otherwise something like


if (issparse (x))
  retval = nnz (x != x.') == 0;
else
  retval = all ((x == x.')(:));
endif


might be appropriate

D.

David Bateman <dbateman>
Group Member
Sun 02 Feb 2014 04:13:52 PM UTC, comment #1: 

I fixed it (yay, my first bugfix).  Can someone commit my patch?

(file #30439)

David Spies <dspyz>
Sun 02 Feb 2014 04:24:41 AM UTC, original submission:  

octave:1> issymmetric(speye(100000))
error: out of memory or dimension too large for Octave's index type
error: called from:
error:   /usr/local/share/octave/4.1.0+/m/linear-algebra/issymmetric.m at line 43, column 14

David Spies <dspyz>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #30439:  sparse_symmetric.diff added by dspyz (683B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by dbateman (Posted a comment)
  • -email is unavailable- added by dspyz (Submitted the item)
  • -email is unavailable- added by dspyz
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2014-02-03 rik5 StatusNone Fixed
        Open/ClosedOpen Closed
    2014-02-02 dspyz Attached File- Added sparse_symmetric.diff, #30439
    2014-02-02 dspyz Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code