http://d.puremagic.com/issues/show_bug.cgi?id=4412
Summary: Array capacity growth spikey and the ratio approaches
1.0
Product: D
Version: 2.032
Platform: Other
OS/Version: Linux
Status: NEW
Severity: normal
Priority: P3
Component: druntime
AssignedTo: s...@invisibleduck.org
ReportedBy: acehr...@yahoo.com
--- Comment #0 from Ali Cehreli <acehr...@yahoo.com> 2010-07-01 10:33:06 PDT ---
There are spikes in the array capacity growth. Additionally, the
capacity/length ratio approaches 1.0; as a result, the complexity of the append
operation would not be 'amortized constant' for large length.
import std.stdio;
import std.array;
void main()
{
int[] a;
size_t oldCapacity;
foreach (i; 0 .. 100_000_000) {
a ~= i;
if (a.capacity != oldCapacity) {
writeln("length: ", a.length,
" capacity: ", capacity(a),
" ratio: ", cast(double)capacity(a) / oldCapacity);
oldCapacity = capacity(a);
}
}
}
Produces:
length: 1 capacity: 3 ratio: inf please ignore this one ;)
length: 4 capacity: 7 ratio: 2.33333
length: 8 capacity: 15 ratio: 2.14286
length: 16 capacity: 31 ratio: 2.06667
length: 32 capacity: 63 ratio: 2.03226
length: 64 capacity: 127 ratio: 2.01587
length: 128 capacity: 255 ratio: 2.00787
length: 256 capacity: 509 ratio: 1.99608
length: 512 capacity: 1021 ratio: 2.00589
length: 1022 capacity: 2045 ratio: 2.00294
length: 2046 capacity: 3069 ratio: 1.50073
length: 3070 capacity: 4093 ratio: 1.33366
length: 4094 capacity: 5117 ratio: 1.25018
...
length: 1153022 capacity: 1154045 ratio: 1.00089
length: 1154046 capacity: 1155069 ratio: 1.00089
length: 1155070 capacity: 3153917 ratio: 2.7305 <-- spike
length: 3153918 capacity: 3154941 ratio: 1.00032
length: 3154942 capacity: 3155965 ratio: 1.00032
...
length: 4741118 capacity: 4742141 ratio: 1.00022
length: 4742142 capacity: 4743165 ratio: 1.00022
length: 4743166 capacity: 12333053 ratio: 2.60017 <-- spike
length: 12333054 capacity: 12334077 ratio: 1.00008
length: 12334078 capacity: 12335101 ratio: 1.00008
... (there are more spikes later on)
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
