bugGNU Octave - Bugs: bug #58105, isfield needs time proportional to...

 
 

bug #58105: isfield needs time proportional to number of fields

Submitter:  Francesco Potortì <pot>
Submitted:  Thu 02 Apr 2020 11:57:44 PM UTC
   
 
Category:  Performance Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 07 Oct 2022 11:25:30 AM UTC, comment #16: 

No errors from CI. Closing as Fixed. Thank you to Anon for the analysis and the patch.

Arun Giridhar <arungiridhar>
Group Member
Wed 05 Oct 2022 03:54:03 PM UTC, comment #15: 

I've pushed it to default here for wider testing: https://hg.savannah.gnu.org/hgweb/octave/rev/c5c8bf50449c

I credited Anonymous in comment #7 as the patch author.

Arun Giridhar <arungiridhar>
Group Member
Tue 04 Oct 2022 10:05:32 AM UTC, comment #14: 

Oops. Turns out the earlier updated.patch I attached was the wrong one. I deleted that. Now I am attaching the correct version.

The test script and the timing results are the same as from comment #13.

(file #53787)

Arun Giridhar <arungiridhar>
Group Member
Tue 04 Oct 2022 01:31:23 AM UTC, comment #13: 

Finally got a chance this evening to update the patch and the tests.

Updated patch attached. This is a modern version of comment #7, using m_foo instead of foo as member variable names in various places.

Updated benchmark code attached. This simplifies and accelerates the code from comment #0.

Unpatched code scales linearly for each trial, so quadratically overall. Patched code is constant for each trial, so linear overall. The speedup for N = 2000 reduces 46 seconds to 0.2 seconds, so some 230X faster for this test alone. Longer tests would make an even bigger difference. More important is the scaling itself though.

Please review and test.

@Anon: If you want credit for this patch please list your name and email as you would like it to appear.

(file #53783, file #53784,

Arun Giridhar <arungiridhar>
Group Member
Mon 03 Oct 2022 03:37:16 PM UTC, comment #12: 

A more wide ranging solution is given by anon in comment #7. I found the approach in comment #8 easier to update to the current source.

This can wait until Octave 8 instead of 7.3. Do you prefer comment #7 over comment #8 / comment #10?

The try-catch thing is a low-hanging hack to get constant-time lookups from a struct instead of linear time or logarithmic time lookup, allowing it to be used as a hashmap data structure.

Arun Giridhar <arungiridhar>
Group Member
Mon 03 Oct 2022 02:05:28 PM UTC, comment #11: 

Normally we try to limit changes in the stable release series to documentation and fixes for regressions or serious incorrect results.  Performance improvements wouldn't usually be included in a bug fix release.

As for the current proposed patch, we don't normally use C-style casts, and I can't think of any other places in Octave where we bother with "(void)" casts on return types.

Also, I think a "catch (...)" block to ignore all possible exceptions is bad form unless there is a very good reason for using it.  Why is it needed here?

If the performance of octave_map::isfield is bad, we should fix that problem rather than using the method proposed in this patch.

John W. Eaton <jwe>
Group administrator
Sat 01 Oct 2022 02:59:57 PM UTC, comment #10: 

I came to this bug report from https://octave.discourse.group/t/adding-hashmaps-to-octave/3306/8

I've turned the code in comment #8 into an updated patch (attached). It passes make check for me.

Marking as Ready For Test for wider testing.

Are there objections to bringing this into Octave 7.3?

(file #53779)

Arun Giridhar <arungiridhar>
Group Member
Tue 11 May 2021 08:49:10 AM UTC, comment #9: 

Thanks!

Francesco Potortì <pot>
Mon 10 May 2021 02:13:22 PM UTC, comment #8: 

A re-implementation of builtin "ov-struct.cc/isfield" is attached that ,as .m workaround, uses try/catch trick. It doesn't require API change.
is_field.cc

(file #51413)

Anonymous
Sun 09 May 2021 02:19:03 PM UTC, comment #7: 

Oops! The patch in the last comment in wrong. Please use bug58105-2.patch .

(file #51404)

Anonymous
Sun 09 May 2021 02:07:21 PM UTC, comment #6: 

I attached a patch bug58105-1.patch that adds member "isfield" to "octave_value", "octave_base_value", "octave_struct" and "octave_scalar_struct" that efficiently redirects the call to "octave_map" / "octave_scalar_map" member of "octave_struct" / "octave_scalar_struct".
It is minimal but it results in API change.

(file #51403)

Anonymous
Sun 09 May 2021 11:09:40 AM UTC, comment #5: 

The point is that isfield as implemented in the "workaround" is vastly superior in terms of performance to the builtin, so the general preference to builtin functions to user defined ones in this case should be put aside.

My code uses a struct with 15000 fields, using it as a hash table (a new field is inserted and populated unless it already exists).  In practice, after inserting about 400 fields the time becomes unbearably slow, and increases linearly with number of fields.

The code using the workaround uses 28.5s, the one using the try-catch uses 26.6s, the code with the builtin uses 660s

I think that with these differences any doubt about using the workaround should go away.

Francesco Potortì <pot>
Sun 09 May 2021 10:19:27 AM UTC, comment #4: 

@pot What I mentioned as workaround is just a workaround and I think it probably will not be accepted as a fix to this bug because:

  • isfield is a builtin function that is implemented in c++ and it is less probable to be replaced by a user defined function.
  • Usually bugs that are related to performance have lower preference over other type of bugs like correctness or implememtation of new features. Specially for struct that I think has less uses over for example array data type.
  • Consider lack of resources and active volunteer developers to implement such features.
  • Technical reasons: Octave data structures usually follow copy on write COW semantics and the proposed c++ fix, i.e. exposing internal structures by reference, may lead to some mis-uses

by developers and further bugs may be produced. Because of that most of the Octave API functions return value instead of reference. And since Octave values are cheep COW objects there is usuall no consdiderable performance penalty in returning value.
The main problem here is that Octave currently lacks a performant COW dynamic array data structure. Current Octave Array class is a COW array but appending an element to the end of array always leads to reallocation. Because of that In the implementation of Octave struct a performant dynamic array(std::vector) is used. But the problem is that std::vector isn't a COW data type and every time octave_map is returned by value the internal vector is also copied. So std containers in Octave structures should be used with caution.

I sometimes think that we can implement such COW dynamic array based on implementations like fbstring (a thread safe COW string implementation) but it may require much of work.
It seems that returning octave map by const reference can be a reasonable option.
Note that in the mentioned workaround b.iscell() should be changed to iscell(b). Sorry for typo.

Anonymous
Sun 09 May 2021 08:40:58 AM UTC, comment #3: 

Unfortunately, as of Octave 6.2.0, nothing has changed. Just shipping Octave with the isfield function mentioned by anonymous as a "more complete workaround" would require practically no work and improve the situation dramatically.  Please do that in the next release, whether major or minor

Francesco Potortì <pot>
Sun 14 Mar 2021 01:26:16 AM UTC, comment #2: 

Confirmed.  I meant to acknowledge this earlier.  The points in comment #1 are entirely correct.  Probably a deep overhaul of the internal API around structs would be best.  Changing the release to "dev" since work of this magnitude will need to happen there.

Rik <rik5>
Group administrator
Thu 09 Apr 2020 06:46:37 PM UTC, comment #1: 

The "map_value" member of classes "octave_struct" and "octave_scalar_struct" is very inefficient because it copies all the objects in the container. A fix would be adding member  "isfield" in the classes "octave_value" , "octave_base_value" , "octave_struct" and "octave_scalar_struct" that redirects call to "isfield" member in classes "octave_map" and "octave_scalar_map" and changing "/libinterp/octave-value/ov-struct.cc line:1920"
from

      octave_map m = args(0).map_value ();

to

      const octave_value& m = args(0);


However extensive use of "map_value" in the internal API has the effect of overall reduction in the performance. A more general fix would be adding members "map_ref" and "scalar_map_ref" in "octave_value" and the related classes


const map_ref& () const;

const scalar_map_ref& () const;


Users should be encouraged to use them instead of "map_value" if they need a read only view to map object.

As a workaround you can define "isfield" as:


function c = isfield (a, b)
  try
    a.(b);
    c = 1;
  catch
    c = 0;
  end
endfunction


Or a more  complete workaround:

function c = isfield (a, b)
  if b.iscell ()
    c = ismember (b, fieldnames (a));
  else
    try
      a.(b);
      c = 1;
    catch
      c = 0;
    end
  end
end



Anonymous
Thu 02 Apr 2020 11:57:44 PM UTC, original submission:  

I assumed that structs could be used as associative arrays with performance constant in the number of fields. However, it appears that isfield has complexity linear with number of fields, rather than constant. The following code shows the effect


e1 = 7;                                        # run 10e7 times without isfield
e2 = 5;                                        # run 10e5 times with isfield
for e = [e1 e2]
  e
  a = struct;
  t = zeros(1,10);

  profile off; profile clear; profile on
  for i = 1:10
    for j = 1:10^(e-1)
    f=sprintf("%.11f",rand);
    if (e == e1) || !isfield(a,f)
      a.(f) = [];
    endif
    end
    t(i) = cputime;
  end
  profile off; profshow(4)

  numfields(a)
  [t(2:end)'-t(1), diff(t')]
endfor

return

################################################################
results
################################################################
octave> isfield_bench
e =  7
   #  Function Attr     Time (s)   Time (%)        Calls
--------------------------------------------------------
   4   sprintf            77.539      62.98     10000000
   3      rand            41.345      33.58     10000000
   5 binary ==             4.241       3.44     10000000
   6   cputime             0.000       0.00           10
ans =  9999509
ans =
    36.980    36.980
    74.084    37.104
   111.206    37.123
   148.402    37.195
   185.410    37.008
   222.497    37.087
   259.587    37.090
   297.279    37.693
   334.527    37.248

e =  5
   # Function Attr     Time (s)   Time (%)        Calls
-------------------------------------------------------
   6  isfield          3324.564      98.11       100000
   3     rand            59.608       1.76       100000
   4  sprintf             3.717       0.11       100000
   7 prefix !             0.487       0.01       100000
ans =  100000
ans =
     77.198     77.198
    218.910    141.712
    443.970    225.060
    747.381    303.411
   1129.118    381.737
   1592.993    463.875
   2137.738    544.745
   2762.434    624.696
   3466.373    703.940

## second difference about constant: quadratic time
octave> diff(ans(:,2)
ans =
   64.514
   83.348
   78.351
   78.326
   82.138
   80.870
   79.951
   79.244


Francesco Potortì <pot>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #53787:  updated.patch added by arungiridhar (3KiB - text/x-patch)
file #53784:  bench_isfield.m added by arungiridhar (782B - text/x-objcsrc)
file #53785:  unpatched.png added by arungiridhar (38KiB - image/png)
file #53786:  patched.png added by arungiridhar (37KiB - image/png)
file #53779:  isfield.patch added by arungiridhar (2KiB - text/x-patch)
file #51413:  is_field.cc added by None (2KiB - application/octet-stream)
file #51404:  bug58105-2.patch added by None (2KiB - application/octet-stream)
file #51403:  bug58105-1.patch added by None (2KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by arungiridhar (Updated the item)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by pot (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 15 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-10-07 arungiridhar StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2022-10-04 arungiridhar Attached File- Added updated.patch, #53787
    2022-10-04 arungiridhar Attached File#53783 Removed
    2022-10-04 arungiridhar Attached File- Added updated.patch, #53783
        Attached File- Added bench_isfield.m, #53784
        Attached File- Added unpatched.png, #53785
        Attached File- Added patched.png, #53786
    2022-10-01 arungiridhar Attached File- Added isfield.patch, #53779
        StatusConfirmed Ready For Test
    2021-05-10 None Attached File- Added is_field.cc, #51413
    2021-05-09 None Attached File- Added bug58105-2.patch, #51404
    2021-05-09 None Attached File- Added bug58105-1.patch, #51403
    2021-03-14 rik5 StatusNone Confirmed
        Release5.2.0 dev

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code