www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Dynamic Array reserve

reply Vino <vino.bheeman hotmail.com> writes:
Hi All,

  Request your help on reserve an dynamic array when the capacity 
is reached to a point(eg: 80%) so the array to extend the reserve 
by next 20%

Example:
Array!string Test;
Test. reserve(100) - Initall
Test =(.........) - The number of entries are dynamic
if (array.capacity > 80%) { array.reserve(100+20%)


From,
Vino.B
Dec 16 2017
parent reply Jacob Carlborg <doob me.com> writes:
On 2017-12-16 15:11, Vino wrote:

 Hi All,
 
   Request your help on reserve an dynamic array when the capacity is 
 reached to a point(eg: 80%) so the array to extend the reserve by next 20%
 
 Example:
 Array!string Test;
 Test. reserve(100) - Initall
 Test =(.........) - The number of entries are dynamic
 if (array.capacity > 80%) { array.reserve(100+20%)


There's a "capacity" property which you can use. Compare that to the 
length of the array to know when it has reach 80%.

-- 
/Jacob Carlborg
Dec 16 2017
parent reply Vino <vino.bheeman hotmail.com> writes:
On Saturday, 16 December 2017 at 16:46:49 UTC, Jacob Carlborg 
wrote:

 On 2017-12-16 15:11, Vino wrote:

 Hi All,
 
   Request your help on reserve an dynamic array when the 
 capacity is reached to a point(eg: 80%) so the array to extend 
 the reserve by next 20%
 
 Example:
 Array!string Test;
 Test. reserve(100) - Initall
 Test =(.........) - The number of entries are dynamic
 if (array.capacity > 80%) { array.reserve(100+20%)


 There's a "capacity" property which you can use. Compare that 
 to the length of the array to know when it has reach 80%.


Hi Jacob,

   Thank you , yes we can use the length property and calculate 
the capacity, but the question is how to implement it 
dynamically, so let me explain a bit further.

1> Let assume that an array named Size is defined
string ConfigFile = "Test.txt"  //The size of the file is not 
known.
Array!string Size

2> Reserve the size of the array Test.
Size.reserve(100) //Initial allocation

3> Appending data
Size = File(ConfigFile).byLineCopy();

4> Let us assume the file Test.txt   contains 50,000 lines.

5> As per step 2 we have reserved the array to 100 which means 
that the array can hold 100 lines.

6> Check for every 1 mins if the length of the array(Size) is 
above 80(lines), then increase the reservation of the array by 
20, Size.reserve = (Size.capacity + 20).

7> Step 3 and Step 6 should be running parallel

8> Once step 3 is completed Step 6 should also be ended.

From,
Vino.B
Dec 16 2017
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/16/17 5:48 PM, Vino wrote:

 On Saturday, 16 December 2017 at 16:46:49 UTC, Jacob Carlborg wrote:

 On 2017-12-16 15:11, Vino wrote:

 Hi All,

   Request your help on reserve an dynamic array when the capacity is 
 reached to a point(eg: 80%) so the array to extend the reserve by 
 next 20%

 Example:
 Array!string Test;
 Test. reserve(100) - Initall
 Test =(.........) - The number of entries are dynamic
 if (array.capacity > 80%) { array.reserve(100+20%)


 There's a "capacity" property which you can use. Compare that to the 
 length of the array to know when it has reach 80%.


 
 Hi Jacob,
 
    Thank you , yes we can use the length property and calculate the 
 capacity, but the question is how to implement it dynamically, so let me 
 explain a bit further.


Array should automatically increase the size as you need more data. And 
it amortizes the extensions, so instead of adding a constant number of 
elements (as you are proposing), it multiplies the capacity by some 
value. So you end up with better performance.

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

-Steve
Dec 16 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
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
Dec 16 2017
parent reply Vino <vino.bheeman hotmail.com> writes:
On Sunday, 17 December 2017 at 00:45:06 UTC, Ali Çehreli wrote:

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


 [...]


 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.

 [...]


Hi Steven /Ali,

   Initially we use the native array and we observed the execution 
time was higher so we  then we changed all the native array to 
container array and we were able to see some performance gain, 
the memory usage is not a constrain for us, are main goal is how 
fast the program can perform. Please let me know your thoughts on 
the same.

From,
Vino.B
Dec 17 2017
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/17/17 11:18 AM, Vino wrote:

 On Sunday, 17 December 2017 at 00:45:06 UTC, Ali Çehreli wrote:

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


 [...]


 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.

 [...]


 
 Hi Steven /Ali,
 
    Initially we use the native array and we observed the execution time 
 was higher so we  then we changed all the native array to container 
 array and we were able to see some performance gain, the memory usage is 
 not a constrain for us, are main goal is how fast the program can 
 perform. Please let me know your thoughts on the same.
 


Yeah, the main reason to use Array is for performance.

Note, you may have better performance with Appender as well, as it does 
not need to query the GC for metadata.

-Steve
Dec 17 2017