[Octave-bug-tracker] [bug #58105] isfield needs time proportional to number of fields

[Francesco Potortì]

URL:
  <https://savannah.gnu.org/bugs/?58105>

                 Summary: isfield needs time proportional to number of fields
                 Project: GNU Octave
            Submitted by: pot
            Submitted on: Fri 03 Apr 2020 01:57:44 AM CEST
                Category: Performance
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: 5.2.0
         Discussion Lock: Any
        Operating System: GNU/Linux

    _______________________________________________________

Details:

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





    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?58105>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/