bugGNU Octave - Bugs: bug #51403, isequal is slow

 
 

bug #51403: isequal is slow

Submitted by:  Guillaume <gyom>
Submitted on:  Thu 06 Jul 2017 02:44:58 PM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Ready For Test Assigned to:  None
Originator Name:  Guillaume Open/Closed:  Open
Release:  dev Operating System:  Any

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)

Tue 28 Nov 2017 09:08:55 PM UTC, comment #15:

I fixed the regression here (http://hg.savannah.gnu.org/hgweb/octave/rev/a35bceb4b519). I made an optimization for scalar structs as well as having a long form for struct arrays. I also added BIST tests for struct arrays which were missing.

Rik <rik5>
Project Administrator
Tue 28 Nov 2017 12:22:23 PM UTC, comment #14:

I found a regression with struct arrays:

Guillaume <gyom>
Mon 27 Nov 2017 09:55:09 AM UTC, comment #13:

Thanks for all your work, Rik.

Looking again at the piece of code of comment #1, it now runs in 0.14s!

Guillaume <gyom>
Mon 27 Nov 2017 05:00:36 AM UTC, comment #12:

Should be fixed now.

Rik <rik5>
Project Administrator
Mon 27 Nov 2017 03:28:20 AM UTC, comment #11:
          • assert (isequal (sparse (1), sparse (1)), sparse (1)), true)

!!!!! test failed
parse error:

syntax error

>>> function _test_( )

assert (isequal (sparse (1), sparse (1)), sparse (1)), true)
endfunction
^

Dmitri A. Sergatskov <dasergatskov>
Sun 26 Nov 2017 07:06:42 PM UTC, comment #10:

I think the next step would be to look at rewriting the recursive compare routines, for struct and cell objects, to stay within the current function. Or, possibly rewrite the function in C++ where for loops and recursion are not such a problem.

Rik <rik5>
Project Administrator
Sun 26 Nov 2017 05:03:19 PM UTC, comment #9:

I fixed the bug mentioned in comment #8 and promoted the algorithm from _isequal_ directly in to the files isequal.m and isequaln.m (http://hg.savannah.gnu.org/hgweb/octave/rev/1262d7c4712e). This shaves another 10% off the run time.

Rik <rik5>
Project Administrator
Sun 26 Nov 2017 06:42:37 AM UTC, comment #8:

It looks to me that this patch broke some tests in classes:

E.g.:
http://buildbot.octave.org:8010/builders/gcc-7-debian/builds/65/steps/test/logs/stdio

          • assert (isequal (st, st))

!!!!! test failed
numfields: argument must be a struct
shared variables scalar structure containing the fields:
st =
<class SizeTester>

Dmitri A. Sergatskov <dasergatskov>
Sun 26 Nov 2017 05:56:59 AM UTC, comment #7:

I was wrong. It turns out it was assert.m that Dan and I optimized. isequal() was definitely not optimal. I rewrote it most of the function in this cset (http://hg.savannah.gnu.org/hgweb/octave/rev/606f3866cdb7). On average it is now twice as fast.

Some sample timings:

The other classes don't improve much because they depend on recursion.

Rik <rik5>
Project Administrator
Mon 10 Jul 2017 05:37:08 PM UTC, comment #6:

I pushed your cset here (http://hg.savannah.gnu.org/hgweb/octave/rev/b85a46745298). I changed it to remove the call to numel() in the conditional of the while loop since Octave cannot optimize that function call out, and yet the value is a constant and doesn't need to be re-calculated. I also added a FIXME note to replace the while loop over every element of the cellstr with strcmp calls between each element of varargin once bug #51412 is fixed.

Rik <rik5>
Project Administrator
Mon 10 Jul 2017 09:41:17 AM UTC, comment #5:

First, sorry, the summary of the bug should have been that "isequal is not as fast than Matlab's version" (and indeed, it's a builtin in Matlab; exist('isequal','builtin') is 5).

I can indeed see that extra care was taken to optimize the function (thanks to both of you) and couldn't think of any change to make it faster myself. I would guess that most of the time, this function is called with two arguments: do you think it would be possible to modify the function to run iteratively over arguments such that it might be faster with two arguments but a bit slower with more than two?

I added a special handling for cellstr which makes things a bit faster for me - at a cost of an extra call to cellfun() if the inputs are not cellstr. It also assumes that the content of the cellstr can be tested with strcmp().

Guillaume <gyom>
Mon 10 Jul 2017 03:13:23 AM UTC, comment #4:

I (Rik) and Daniel Sebald spent a lot of time optimizing isequal. For an m-file, its pretty good and uses lots of different techniques. But if there is better code we could evaluate including it in Octave. I think Matlab may have promoted isequal to a compiled built-in function, rather than an m-file.

Also, I agree with Mike that part of the difficulty was that the function had to be general for any arguments A,B,C, ...

If you know something about your inputs, such as the fact that they are cellstr, then you may be able to take advantage of that to simplify the comparison.

Rik <rik5>
Project Administrator
Fri 07 Jul 2017 10:11:43 AM UTC, comment #3:

Thanks for looking into this, I agree with your comments.

What is particularly slow in the examples below is the comparison of cellstr arrays: when comparing A.field1, Matlab is more than 2500 faster than Octave. I tried to call strcmp directly without reshaping and copying char arrays but ran into other issues (see bug #51412).

Guillaume <gyom>
Thu 06 Jul 2017 09:49:46 PM UTC, comment #2:

Part of the slowness of _isequal_ may be that it is written to always support variable arguments, while the most common case is just two arguments being compared.

Compare the timings and the profiler output for these two ways of testing whether two objects have the same class:

For the most common case of `isequal(x,y)`, y is still represented as varargin and all comparisons are done using cellfun.

Mike Miller <mtmiller>
Project Administrator
Thu 06 Jul 2017 03:36:05 PM UTC, comment #1:

With the profiler and by recursively comparing each element of your struct, it doesn't look to me like there is one particular bottleneck, just the basic structure of _isequal_, multiplied because it is called recursively 197 times for each call on A.

I get a runtime of about 0.036 seconds for each 100 calls to isequal(x,x) where x is a scalar double or double matrix of relatively small dimensions. I get the same runtime for a small string.

If you multiply that out, 0.036 * 198 is about 7 seconds, which is the runtime I can confirm with the original example.

Same shown for each field of the A struct:

Mike Miller <mtmiller>
Project Administrator
Thu 06 Jul 2017 02:44:58 PM UTC, original submission:

I noticed that calls to isequal() were the origin of a performance bottleneck on a larger piece of code I'm working on, especially as compared to Matlab.

In Matlab:

In Octave:

Looking at the code in _isequal_, I'm not sure to understand the code to compare numeric arrays, especially the use of find(). It doesn't seem to be the only reason of the slowness though. Does anyone have any suggestion on how to make this function run faster?

Guillaume <gyom>

 

(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 dasergatskov (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by gyom (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can 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 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    Sun 26 Nov 2017 07:06:42 PM UTC rik5 StatusIn Progress => Ready For Test
    Sun 26 Nov 2017 05:56:59 AM UTC rik5 StatusNone => In Progress

    Back to the top


    Powered by Savane 3.3