[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Octave-bug-tracker] [bug #58105] isfield needs time proportional to num
From: |
Francesco Potortì |
Subject: |
[Octave-bug-tracker] [bug #58105] isfield needs time proportional to number of fields |
Date: |
Thu, 2 Apr 2020 19:57:46 -0400 (EDT) |
User-agent: |
Mozilla/5.0 (X11; Linux i686; rv:45.0) Gecko/20100101 Firefox/45.0 |
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/
- [Octave-bug-tracker] [bug #58105] isfield needs time proportional to number of fields,
Francesco Potortì <=