bugGNU Octave - Bugs: bug #36656, deleting rows from sparse matrices...

 
 

bug #36656: deleting rows from sparse matrices leads to failed assertion sometimes

Submitted by:  None
Submitted on:  Thu 14 Jun 2012 01:26:09 PM UTC  
 
Category: InterpreterSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Segfault, Bus Error, etc.
Status: FixedAssigned to: Jordi Gutiérrez Hermoso <jordigh>
Originator Name: LevOriginator Email: -unavailable-
Open/Closed: ClosedRelease: 3.6.2
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 Jump to the original submission)

Thu 21 Jun 2012 06:48:09 PM UTC, comment #12:

Okay, I just applied all the patches, hopefully properly separated between stable and default. The last six patches here do all this:

http://hg.savannah.gnu.org/hgweb/octave/graph/41dcb2c5bb1a

Lev, Octave 3.6.3, if it's released, will have this fixed, or else, it will appear in 3.8.0.

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Tue 19 Jun 2012 01:19:51 PM UTC, comment #11:

I agree that the bug fixes can go on stable.

The optimization that I posted can go on devel provided that the problem that it fixed is also addressed by the other changes.

John W. Eaton <jwe>
Project Administrator
Mon 18 Jun 2012 07:34:47 AM UTC, comment #10:

John's patch is an optimization and so should probably go into the devel tree. The other patches are for bugs and should be applied to the stable tree as well

D;

David Bateman <dbateman>
Project Member
Fri 15 Jun 2012 09:12:10 PM UTC, comment #9:

I think I have a fix:

The column index was getting set wrong in cases such as these:

but it looks like while hunting for this bug, we found a host of associated things to patch elsewhere. How should we handle all of this? Some for stable, some for devel?

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Fri 15 Jun 2012 04:30:42 PM UTC, comment #8:

Jordi, I think it would still make sense to apply the additional optimization I suggested for deleting elements from empty arrays. I'm attaching it here so hopefully it won't be forgotten.

(file #26043)

John W. Eaton <jwe>
Project Administrator
Fri 15 Jun 2012 02:48:45 PM UTC, comment #7:

It turns out that my distilled example actually is exhibiting a different problem than Lev's original example. Your second patch does fix my example, but not Lev's.

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Thu 14 Jun 2012 10:42:45 PM UTC, comment #6:

Jordi,

Deep or not I think I understand the code. Yes my comment was a throw away that I wrote rapidly and I misread cidx as ridx. So taking your comment as a challenge, here is my analysis of the situation

In Sparse<T>::delete_elements when idx_j is a colon then the creation of both tmpl and tmpu will first call index(idx_i,idx_j) before first falling back to index(idx_i) as nc==1 and j is a colon. This calls the code

to create the index vector. As idx_i (as for all index vectors) is a column vector, then the index that is returned to create tmpu and tmpl in delete_elements is also a column vector and we were expecting it to be a row vector.

The basic problem is that when nr=nc==1 then index(idx_j) can't know the shape of the desired return vector and so guessing its a column vector is reasonable. Whereas index(idx_i,idx_j) knows what shape it should be. The fix is in index(idx_i,idx_j) to transpose retval if nc=nr==1 and j is a colon.

I still think its a good idea to make the change I suggested previously in any case to avoid issues if the vectors data and ridx are not defined. So my proposed fix if

D.

David Bateman <dbateman>
Project Member
Thu 14 Jun 2012 05:10:59 PM UTC, comment #5:

The failed assertion turns out to be just one case of UB. The second example I posted distilled from the first exhibits UB in other ways.

At any rate, I attempted your suggested fix:

but even with this change, the UB and valgrind's unhappiness persists.

I am very suspicious of cset fdccd69d26bd. There have been some pretty deep modifications to the sparse code since your initial implementation, David.

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Thu 14 Jun 2012 04:11:13 PM UTC, comment #4:

Given the assertion that is failing this is the same issues as for the bug #36104. With the same fix

http://hg.savannah.gnu.org/hgweb/octave/rev/8d2ce821e38a

That is somewhere the constructor

rep = new SparseRep (nr, nc);

and it needs to be replaced with

rep = new SparseRep (nr, nc, 0);

to ensure that the values in ridx are valid. In fact given this issue the constructor SparseRep(nr,nc) probably shouldn't be used. So the easiest fix would be just to rewrite this to use SparseRep(nr,nv, 0) instead.

D.

David Bateman <dbateman>
Project Member
Thu 14 Jun 2012 03:45:58 PM UTC, comment #3:

After trying to pinpoint the problem, the trouble seems to be with deleting rows of a sparse matrix for which nnz is 0:

I get the following valgrind output:

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Thu 14 Jun 2012 02:25:12 PM UTC, comment #2:

And the failed assertion I see is:

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Thu 14 Jun 2012 02:22:46 PM UTC, comment #1:

Confirmed.

Note that the problem I experience is not a segfault but a failed assertion, which Lev confirms via private communication. It's also intermittent, as I have to run the script a few times before I can reproduce it.

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Thu 14 Jun 2012 01:26:09 PM UTC, original submission:

I have a code (using octave 3.6.1) by which one can debug it in depth.

call it as

supportThreshold( 3,10, sparse(rand(1000,1000)>0.99) );

it will segfault.
If you have doubt, you may load a constellation by uncommenting the load function call
and download aa.dat from http://justpaste.it/octaveSegfault
or find it attached.

Here is the function:

function uis = supportThreshold( userMinSupport , itemMinSupport , uis )
% load aa.dat
for i=1:10
s=size(uis)

user_event_count = sum(uis,2);
inx=find(user_event_count<userMinSupport);
length(inx)
uis(inx,:)=[];

item_event_count = sum(uis);
inx = find(item_event_count&lt;itemMinSupport);
length(inx)
uis(:,inx)=[];

if all(s==size(uis))
break;
endif
end
end

What I see is that.
Octave is trying to delete all lines from the sparse matrix at
uis(inx,:)=[]; which works perfectly when executed interactively however doesn't work in a cycle above.

And idea?
Cheers,
Lev

Anonymous

 

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

Attach File(s):
   
   
Comment:
   

Attached Files
file #26043:  diffs.txt added by jwe (4KiB - text/plain)
file #26028:  aa.dat added by None (97KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by jwe (Updated the item)
  • -unavailable- added by dbateman (Posted a comment)
  • -unavailable- added by jordigh (Posted a comment)
  • -unavailable- added by None (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 10 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Thu 21 Jun 2012 06:48:08 PM UTCjordighStatusConfirmed=>Fixed
      Open/ClosedOpen=>Closed
    Fri 15 Jun 2012 04:30:42 PM UTCjweAttached File-=>Added diffs.txt, #26043
    Thu 14 Jun 2012 05:14:38 PM UTCjordighRelease3.6.1=>3.6.2
    Thu 14 Jun 2012 05:10:59 PM UTCjordighRelease3.6.2=>3.6.1
    Thu 14 Jun 2012 02:25:12 PM UTCjordighRelease3.6.1=>3.6.2
    Thu 14 Jun 2012 02:22:46 PM UTCjordighStatusNone=>Confirmed
      Assigned toNone=>jordigh
      Summarydeleting rows from sparse matrices leads to seg fault sometimes=>deleting rows from sparse matrices leads to failed assertion sometimes
    Thu 14 Jun 2012 01:26:09 PM UTCNoneAttached File-=>Added aa.dat, #26028

    Back to the top


    Powered by Savane 3.1-cleanup1