# bug #51403: isequal is slow

 Submitted by: Guillaume Submitted on: 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

Add a New Comment

You are not logged in

Please log in, so followups can be emailed to you.

## Discussion

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>
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>
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>
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>
Sun 26 Nov 2017 06:42:37 AM UTC, comment #8:

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

• 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>
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>
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>
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>
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>
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>

## Attached Files

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

Attach Files:

Comment:

No files currently attached

## Dependencies

Depends on the following items: None found

Items that depend on this one: None found

## Mail Notification Carbon-Copy List

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)
•

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.

## History

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