bugGNU Octave - Bugs: bug #50796, calling find on diagonal matrix is...

 
 

bug #50796: calling find on diagonal matrix is slower than full matrix

Submitter:  Carnë Draug <carandraug>
Submitted:  Thu 13 Apr 2017 01:19:14 PM UTC
 
Category:  Performance Severity:  3 - Normal
Priority:  5 - Normal Item Group:  None
Status:  Patch Submitted Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Thu 27 Apr 2017 07:39:09 PM UTC, comment #7: 

What do you think of the included patch? I modified find_nonzero_elem_idx in find.cc in order to manage the DiagArray2 case. Please, revise carefully since these are my first experiments with C++.

(file #40522)

Marco Caliari <caliari>
Project Member
Thu 27 Apr 2017 12:24:55 AM UTC, comment #6: 

The script shows that that is not always true, it depends on the types of elements of the matrix (compared bool vs double).

Also the complexities do not seem to differ that much.

What I meant is that finding on a diagonal matrices is just finding on the vector of its diagonal, so the "overload" is just calling find on the diag vector, i.e. find (diag(A),...)

Juan Pablo Carbajal <juanpi>
Project Member
Wed 26 Apr 2017 11:01:48 PM UTC, comment #5: 

I don't think so.  Since there is no overload it appears that find converts the matrix to full, and then calls find on that.  However, there is something else going on since

find (full (diag))

is a relatively quick operation.

Rik <rik5>
Project Administrator
Wed 26 Apr 2017 10:12:16 PM UTC, comment #4: 

Isn't the find of diagMatrix A just find(diag(A),...)?

Juan Pablo Carbajal <juanpi>
Project Member
Wed 26 Apr 2017 08:57:57 PM UTC, comment #3: 

Confirmed.  The trouble seems to be that there is no overload of the find function for DiagMatrix.  I think any change needs to start in liboctave/array/.  But it might also require changes to libinterp/corefcn/find.cc.

Rik <rik5>
Project Administrator
Sat 15 Apr 2017 02:02:14 PM UTC, comment #2: 

I forgot to mention that this was identified on this

stackoverflow question http://stackoverflow.com/a/43393446/1609556

where I mention that find has special cases for several data types and it is missing diagonal matrices. It's just weird that it takes so much more time so maybe there is something else going on.

Carnë Draug <carandraug>
Project Member
Thu 13 Apr 2017 02:14:23 PM UTC, comment #1: 

The attached script produces (using function speed)

> find_timeit
Order, time per operation (ones)
Full: 1.7, 3.2e-08
Diag: 2.1, 1.4e-09
Opt: 0.28, 2.4e-06

Order, time per operation (bool)
Full: -0.0084, 1.4e-05
Diag: 0.056, 8.6e-06
Opt: 0.4, 9.8e-07

So it seems the problem is with doubles, as booleans are close to the optimal. I am puzzled by the negative order of the boolean full case.

(file #40391)

Juan Pablo Carbajal <juanpi>
Project Member
Thu 13 Apr 2017 01:19:14 PM UTC, original submission:  

I though this was because find converts a diagonal to a full matrix internally, but even if calling full ourselves before find, it's still much faster so I am no longer sure:

octave> d = eye (10000);
octave> f = full (eye (10000));
octave> for i=1:10, find (d); endfor, t = cputime (); for i=1:100, find (d); endfor, cputime () -t
ans =  104.37
octave> for i=1:10, find (f); endfor, t = cputime (); for i=1:100, find (f); endfor, cputime () -t
ans =  57.920
octave> for i=1:10, find (full (d)); endfor, t = cputime (); for i=1:100, find (full (d)); endfor, cputime () -t
ans =  58.280

Carnë Draug <carandraug>
Project Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #40522:  find.patch added by caliari (4KiB - text/x-patch)
file #40391:  find_timeit.m added by juanpi (829B - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by caliari (Updated the item)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by juanpi (Updated the item)
  • -email is unavailable- added by carandraug (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 project members can vote.

     

     

     

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-05-01 caliari StatusConfirmed Patch Submitted
    2017-04-27 caliari Attached File- Added find.patch, #40522
    2017-04-26 rik5 StatusNone Confirmed
    2017-04-13 juanpi Attached File- Added find_timeit.m, #40391

    Back to the top

    Powered by Savane 3.10