Dynamic Array reserve

Ali Çehreli acehreli at yahoo.com
Sun Dec 17 00:45:06 UTC 2017


On 12/16/2017 03:58 PM, Steven Schveighoffer wrote:

> I think you are fine to just use Array and not worry about the 
> reallocations, they are handled automatically.
> 
> -Steve

I was going to suggest the same to Vino and I was writing the following 
program to demonstrate how low the number of allocations is.

I don't remember whether this was discussed but I would additionally 
suggest staying with D's native arrays. I know Array does not use the GC 
for it's buffer but I don't know why it would matter in a program where 
one already calls byLineCopy, .array, etc.

Further, as the program below demonstrates, native arrays are better 
when it comes to memory allocation: For 1 million elements, Array!int 
made 33 allocations and int[] made 24 allocations. (Of course I know 33 
== 24 in this case. :) )

import std.stdio;
import std.container;

void main() {
     test!(Array!int)();
     test!(int[])();
}

void test(A)() {
     writefln("\n--- Testing %s ---", A.stringof);

     A arr;

     size_t allocations = 0;
     bool dotPrinted = false;
     enum N = 1_000_000;
     foreach (i; 0 .. N) {
         string mark = "    ";
         const oldCapacity = arr.capacity;
         arr ~= i;
         if (arr.capacity != oldCapacity) {
             ++allocations;
             mark = " <--";
         }
         if ((i < 10) || (i >= N - 10)) {
             writefln("length:%4s capacity:%4s %s allocations: %s 
alloc/item: %f",
                      arr.length, arr.capacity, mark, allocations, 
double(allocations)/(i + 1));
         } else if (!dotPrinted) {
             writefln("[... %s more lines here ... ]", N - 2 * 10);
             dotPrinted = true;
         }
     }
}

--- Testing Array!int ---
length:   1 capacity:   1  <-- allocations: 1 alloc/item: 1.000000
length:   2 capacity:   2  <-- allocations: 2 alloc/item: 1.000000
length:   3 capacity:   4  <-- allocations: 3 alloc/item: 1.000000
length:   4 capacity:   4      allocations: 3 alloc/item: 0.750000
length:   5 capacity:   7  <-- allocations: 4 alloc/item: 0.800000
length:   6 capacity:   7      allocations: 4 alloc/item: 0.666667
length:   7 capacity:   7      allocations: 4 alloc/item: 0.571429
length:   8 capacity:  11  <-- allocations: 5 alloc/item: 0.625000
length:   9 capacity:  11      allocations: 5 alloc/item: 0.555556
length:  10 capacity:  11      allocations: 5 alloc/item: 0.500000
[... 999980 more lines here ... ]
length:999991 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999992 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999993 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999994 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999995 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999996 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999997 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999998 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:999999 capacity:1049867      allocations: 33 alloc/item: 0.000033
length:1000000 capacity:1049867      allocations: 33 alloc/item: 0.000033

--- Testing int[] ---
length:   1 capacity:   3  <-- allocations: 1 alloc/item: 1.000000
length:   2 capacity:   3      allocations: 1 alloc/item: 0.500000
length:   3 capacity:   3      allocations: 1 alloc/item: 0.333333
length:   4 capacity:   7  <-- allocations: 2 alloc/item: 0.500000
length:   5 capacity:   7      allocations: 2 alloc/item: 0.400000
length:   6 capacity:   7      allocations: 2 alloc/item: 0.333333
length:   7 capacity:   7      allocations: 2 alloc/item: 0.285714
length:   8 capacity:  15  <-- allocations: 3 alloc/item: 0.375000
length:   9 capacity:  15      allocations: 3 alloc/item: 0.333333
length:  10 capacity:  15      allocations: 3 alloc/item: 0.300000
[... 999980 more lines here ... ]
length:999991 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999992 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999993 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999994 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999995 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999996 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999997 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999998 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:999999 capacity:1048571      allocations: 24 alloc/item: 0.000024
length:1000000 capacity:1048571      allocations: 24 alloc/item: 0.000024

Ali


More information about the Digitalmars-d-learn mailing list