why does array appending add a page size instead of doubling ?
timotheecour
thelastmammoth at gmail.com
Sun Feb 3 02:32:09 PST 2013
> One more: Did you try using std.container.Array?
>
> Even if appender is more optimized than naked array appending,
> it still has to work with the underlying system.
> std.container.Array should be able to do just as well as
> vector, or better (D move semnantics).
it's a bit better (see below for timings), with T=22.628 sec
total vs 14s for C++'s std::vector.
Note, I'm not sure how to get address of 1st element in an
std.container.Array (is it even possible??? seems like an
overreaching limitation for the sake of safety in a system
language) so I don't know how to tell the reallocations. But I
guess the scheme is clear (reserve(1+3/2*capacity)). In any case,
there's still a noticable gap with C++. Also, I'm curious whether
you have a reference explaining why 3/2 works better than 2x (as
in std::vector) in resizing?
Elements[0]: 1, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[1]: 2, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[2]: 4, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[3]: 8, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[4]: 16, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[5]: 32, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[6]: 64, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[7]: 128, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[8]: 256, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[9]: 512, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[10]: 1024, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[11]: 2048, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[12]: 4096, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[13]: 8192, Allocations: 0, Moved: 0; Moved/Elements = 0;
time/Elements=0
Elements[14]: 16384, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=0
Elements[15]: 32768, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=0
Elements[16]: 65536, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=0
Elements[17]: 131072, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=0
Elements[18]: 262144, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=3.8147e-06
Elements[19]: 524288, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=5.72205e-06
Elements[20]: 1048576, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=4.76837e-06
Elements[21]: 2097152, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=4.76837e-06
Elements[22]: 4194304, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=5.00679e-06
Elements[23]: 8388608, Allocations: 0, Moved: 0; Moved/Elements =
0; time/Elements=4.88758e-06
Elements[24]: 16777216, Allocations: 0, Moved: 0; Moved/Elements
= 0; time/Elements=4.88758e-06
Elements[25]: 33554432, Allocations: 0, Moved: 0; Moved/Elements
= 0; time/Elements=5.00679e-06
Elements[26]: 67108864, Allocations: 0, Moved: 0; Moved/Elements
= 0; time/Elements=4.97699e-06
Elements[27]: 134217728, Allocations: 0, Moved: 0; Moved/Elements
= 0; time/Elements=4.92483e-06
Elements[28]: 268435456, Allocations: 0, Moved: 0; Moved/Elements
= 0; time/Elements=4.97699e-06
Elements[29]: 536870912, Allocations: 0, Moved: 0; Moved/Elements
= 0; time/Elements=4.93042e-06
Elements[30]: 1073741824, Allocations: 0, Moved: 0;
Moved/Elements = 0; time/Elements=4.94439e-06
Elements[31]: 2147483648, Allocations: 0, Moved: 0;
Moved/Elements = 0; time/Elements=5.16605e-06
./test_010 20.71s user 1.89s system 99% cpu 22.628 total
----
auto s=Array!T();
foreach (i; 0 .. maxElements) {
auto oldPtr = &(s.front); //NOTE: incorrect, doesn't take
address of returned element but of the function...
s.insertBack(cast(T)0);
if (&(s.front) != oldPtr) {
totalElementsMoved += (s.length - 1);
++totalAllocations;
}
}
----
More information about the Digitalmars-d-learn
mailing list