bugGNU Octave - Bugs: bug #40341, Logical indexing into sparse...

 
 

bug #40341: Logical indexing into sparse matrices causes OOM

Submitter:  David Spies <dspyz>
Submitted:  Mon 21 Oct 2013 11:08:04 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Wont Fix 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
   

Jump to the original submission

Thu 11 Nov 2021 09:36:52 PM UTC, comment #12: 

just noting that in 6.4.0, the comment #0 code now produces no issues. likely as rik said simply because it no longer overflows the indexing.  I suspect a proper choice in array size would produce the issue again, but as Rik says, that's very large. since no one voiced an objection to his 2018 comment that the point is moot, but since it doesn't appear that the underlying issue was changed, closing as won't fix until it rears its head again.

Nicholas Jankowski <nrjank>
Group Member
Wed 01 Aug 2018 10:29:40 PM UTC, comment #11: 

This bug still exists, but in practical terms things have gotten better.  Octave is now built by default with 63-bit indexing vectors rather than 31-bit vectors.  For sparse matrices, this leads to square matrices with 3 billion elements on a side versus just 46,000.


octave:18> format short e
octave:19> sqrt (2^63)
ans =    3.0370e+09
octave:20> sqrt (2^31)
ans =    4.6341e+04


The original code (logical indexing) now works as well.  Or you can use linear indexing as the following code also demonstrates.


octave:22> a = sprand(100000,100000,0.0001);
octave:23> b = logical(sprand(100000,100000,0.0001));
octave:24> a2 = a;
octave:25> a3 = a;
octave:26> a(b) = 0;
octave:27> isequal (a, a2)
ans = 0
octave:28> idx = find (b);
octave:29> a2(idx) = 0;
octave:30> isequal (a2, a3)
ans = 0
octave:31> isequal (a, a2)
ans = 1
octave:32> diary off



Rik <rik5>
Group administrator
Tue 22 Nov 2016 10:33:33 PM UTC, comment #10: 

This issue is still present in Octave 4.2.0.

Hartmut <hardy>
Fri 07 Feb 2014 09:47:30 PM UTC, comment #9: 

Oh no,
v = nonzeros(A .* B);
doesn't quite mean the same thing as
v = A(B)
since it ignores the zeros

David Spies <dspyz>
Fri 07 Feb 2014 06:26:18 PM UTC, comment #8: 

Well, that's definitely a clever work around. Good stuff.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Fri 07 Feb 2014 06:16:39 PM UTC, comment #7: 

That is an entirely valid and reasonable request, however I'm afraid I can't ask my supervisor for money for this right now.

I do think I've found a workaround though (at least for numeric matrices).

To say A(B) = 0
I can instead use A = A - A .* B;

And to mean A(B) = C(B);

I can instead use A = A - A .* B + C .* B;

And for v = A(B), I can say v = nonzeros(A .* B);

And for A(B) = v, I can say
[i,j] = find(B);
[m,n] = size(B);
A = A - A .* B + sparse(i,j,v,m,n);

David Spies <dspyz>
Fri 07 Feb 2014 05:05:46 PM UTC, comment #6: 

Oh, right, stupid me.

There is no workaround other than looping through the i and j vectors.

You seem to really want this. Would you be able to tip me a little bit of money or ask your employer to do so if I spent a few hours or days trying to fix this about Octave? This problem doesn't affect me, and it doesn't affect most Octave users, and it would take a lot of effort to fix. Since you're the only person I know who is affected but you're apparently unable to fix Octave yourself, it would got a long way to motivate me to fix this if there was a little bit of money involved.

If not, you might wait until David Bateman tries to fix this. He might have other motivations to do so. Or perhaps another champion will arise from the shadows to squash this bug.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Fri 07 Feb 2014 04:21:04 PM UTC, comment #5: 

That's not the same thing.

a(i,j) refers to all elements whose row is in the set i and whose column is in the set j.

But I only want the set of things whose (row,column) are among the set of pairs (i,j)

David Spies <dspyz>
Fri 07 Feb 2014 02:31:46 PM UTC, comment #4: 

A simple workaround is to use find:


a = sprand(100000,100000,0.0001);
b = logical(sprand(100000,100000,0.0001));
[i,j] = find(b);
a(i,j) = 0;


Jordi Gutiérrez Hermoso <jordigh>
Group Member
Fri 07 Feb 2014 08:44:09 AM UTC, comment #3: 

Can someone take another look at this?  It's really driving me nuts.  Is there a workaround I can use?

David Spies <dspyz>
Tue 22 Oct 2013 06:27:27 PM UTC, comment #2: 

This one is documented in the projects file

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


Sparse logical indexing in idx_vector class so that something like 'a=sprandn(1e6,1e6,1e-6); a(a<1) = 0' won't cause a memory overflow.


What is happening now in your case is that the logical "b" is being converted to a single argument numeric index for the "true" values of the sparse logical matrix. This is identical to what happens for normal logical matrix indexing, but in the case of sparse matrices the values of the numerically index can depasse intmax().

The solution is the create a new idx_vector class particularly for sparse logical indexing that stores (row,column) pairs. If used in its default form it would act identically to idx_vector::idx_vector_rep, but the Sparse indexed assignment could then special case it.

There is no call to numel() anywhere here

David Bateman <dbateman>
Group Member
Tue 22 Oct 2013 12:50:46 AM UTC, comment #1: 

Ah, this is one that you won't be able to fix by avoiding calls to numel, Mr Bateman...

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Mon 21 Oct 2013 11:08:04 PM UTC, original submission:  


>> a = sprand(100000,100000,0.0001);
>> b = logical(sprand(100000,100000,0.0001));
>> a(b) = 0;

error: out of memory or dimension too large for Octave's index type

Note:
This bug also occurs in 3.6.4

David Spies <dspyz>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    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 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-11-11 nrjank StatusConfirmed Wont Fix
        Open/ClosedOpen Closed
    2013-10-22 jordigh StatusNone Confirmed

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code