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