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:  None Assigned to:  None
Originator Name:  Open/Closed:  Open
Release:  5.2.0 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.

 

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:
   

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

     

     

     

    No changes have been made to this item

    Back to the top


    Powered by Savane 3.5