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

 
 

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

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

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 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>
Project 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 #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 rik5 (Posted a comment)
  • -email is unavailable- added by pot (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.

     

     

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    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.7