Search
Dynamic Array reserve
Dec 16
Vino
Dec 16
Vino
Dec 17
Vino
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

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
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

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
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
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

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