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 FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: NoneAssigned to: None
Originator Name: GuillaumeOpen/Closed: Open
Release: devOperating 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 Jump to the original submission)

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 File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by gyom (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):

     

     

    No Changes Have Been Made to This Item

    Back to the top


    Powered by Savane 3.1-cleanup1