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