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

 
 

bug #51403: isequal is slow

Submitter:  Guillaume <gyom>
Submitted:  Thu 06 Jul 2017 02:44:58 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Guillaume Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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>
Group administrator
Tue 28 Nov 2017 12:22:23 PM UTC, comment #14: 

I found a regression with struct arrays:


>> a = struct ("a", {1,2});
>> isequal (a, a)
ans = 0


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. 


parent: 24313:7ba994876f3a tip
 isequal.m: Fix typo in BIST test (bug #51403).



Rik <rik5>
Group 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>
Group 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>
Group 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:


NUMERIC

x = pi;
tic; for i=1:1e4, isequal (x,x); end; toc
OLD: 2.91767 seconds
NEW: 1.27365 seconds
%change : -56%

x = rand (15,15);
tic; for i=1:1e4, isequal (x,x); end; toc
OLD: 3.08964 seconds
NEW: 1.35772 seconds
%change : -56%



STRING

x = "Hello World";
tic; for i=1:1e4, isequal (x,x); end; toc
OLD: 2.90298 seconds
NEW: 1.17137 seconds
%change: -60%

x = char ("Hello World", "String2", "String3");
tic; for i=1:1e4, isequal (x,x); end; toc
OLD: 2.79572 seconds
NEW: 1.17914 seconds
%change: -58%



CELLSTR

x = { ["ab"; "cd"] ; ["ef"; "gh"] }
tic; for i=1:1e4, isequal (x,x); end; toc
OLD: 2.65822 seconds
NEW: 1.53199 seconds
%change: -42%


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


Rik <rik5>
Group 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>
Group 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().


--- a/scripts/general/private/__isequal__.m     Fri Jul 07 08:17:32 2017 -0400
+++ b/scripts/general/private/__isequal__.m     Mon Jul 10 10:27:33 2017 +0100
@@ -117,14 +117,22 @@
         t = __isequal__ (args{:});
       endwhile

+    elseif (iscellstr (x) && all (cellfun (@iscellstr, varargin)))
+      idx = 0;
+      while (t && idx < numel (x))
+        idx += 1;
+        t = all (strcmp (x{idx}, [cellindexmat(varargin, idx){:}]));
+      endwhile
+
     elseif (iscell (x))
       ## Check that each element of a cell is equal.
       l_x = numel (x);
       idx = 0;
+      args = cell (1, 2+l_v);
+      args{1} = nans_compare_equal;
       while (t && idx < l_x)
         idx += 1;
-        args = cell (1, 2+l_v);
-        args(1:2) = {nans_compare_equal, x{idx}};
+        args{2} = x{idx};
         args(3:end) = [cellindexmat(varargin, idx){:}];

         t = __isequal__ (args{:});


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>
Group 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:


>> x = [];
>> y = x;
>> profile on
>> tic; for i=1:10000; strcmp (class (x), class (y)); endfor; toc
Elapsed time is 0.180546 seconds.
>> profile off
>> profshow
   #            Function Attr     Time (s)   Time (%)        Calls
------------------------------------------------------------------
   2               class             0.015      75.92        20000
   3              strcmp             0.005      23.51        10000
   5             profile             0.000       0.40            1
   4                 toc             0.000       0.07            1
   1                 tic             0.000       0.02            1
   6              nargin             0.000       0.02            1
   8               false             0.000       0.02            1
   7           binary !=             0.000       0.02            1
   9 __profiler_enable__             0.000       0.00            1
>> profile clear
>> arg_list = {y};
>> profile on
>> tic; for i=1:10000; strcmp (class (x), cellfun ("class", arg_list, "uniformoutput", false)); endfor; toc
Elapsed time is 0.330531 seconds.
>> profile off
>> profshow
   #            Function Attr     Time (s)   Time (%)        Calls
------------------------------------------------------------------
   4             cellfun             0.063      58.65        10000
   5              strcmp             0.019      17.48        10000
   2               class             0.016      15.16        20000
   3               false             0.009       8.63        10001
   7             profile             0.000       0.05            1
   6                 toc             0.000       0.01            1
   1                 tic             0.000       0.00            1
   8              nargin             0.000       0.00            1
   9           binary !=             0.000       0.00            1
  10 __profiler_enable__             0.000       0.00            1


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>
Group Member
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:


>> tic; for i=1:100; isequal (A.field1, A.field1); endfor; toc
Elapsed time is 2.16991 seconds.
>> tic; for i=1:100; isequal (A.field2, A.field2); endfor; toc
Elapsed time is 2.18113 seconds.
>> tic; for i=1:100; isequal (A.field3, A.field3); endfor; toc
Elapsed time is 0.0350201 seconds.
>> tic; for i=1:100; isequal (A.field4, A.field4); endfor; toc
Elapsed time is 2.17106 seconds.
>> tic; for i=1:100; isequal (A.field5, A.field5); endfor; toc
Elapsed time is 0.0386372 seconds.


Mike Miller <mtmiller>
Group Member
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.


clear A
[A.field1{1:64}] = deal('string');
[A.field2{1:64}] = deal('string');
A.field3 = rand(128,4);
[A.field4{1:64}] = deal('string');
A.field5 = rand(128,4);


In Matlab:


>> tic;for i=1:100, isequal(A,A);end;toc
Elapsed time is 0.007132 seconds.


In Octave:


octave> tic;for i=1:100, isequal(A,A);end;toc
Elapsed time is 7.8635 seconds.


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 gyom (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 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-12-13 rik5 StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2018-10-02 mtmiller Carbon-CopyRemoved 80942 -
    2017-11-26 rik5 StatusIn Progress Ready For Test
    2017-11-26 rik5 StatusNone In Progress

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code