Re: Dynamic Array reserve
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
Re: Dynamic Array reserve
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
Re: Dynamic Array reserve
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.00
length: 2 capacity: 2 <-- allocations: 2 alloc/item: 1.00
length: 3 capacity: 4 <-- allocations: 3 alloc/item: 1.00
length: 4 capacity: 4 allocations: 3 alloc/item: 0.75
length: 5 capacity: 7 <-- allocations: 4 alloc/item: 0.80
length: 6 capacity: 7 allocations: 4 alloc/item: 0.67
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.56
length: 10 capacity: 11 allocations: 5 alloc/item: 0.50
[... 80 more lines here ... ]
length:91 capacity:1049867 allocations: 33 alloc/item: 0.33
length:92 capacity:1049867 allocations: 33 alloc/item: 0.33
length:93 capacity:1049867 allocations: 33 alloc/item: 0.33
length:94 capacity:1049867 allocations: 33 alloc/item: 0.33
length:95 capacity:1049867 allocations: 33 alloc/item: 0.33
length:96 capacity:1049867 allocations: 33 alloc/item: 0.33
length:97 capacity:1049867 allocations: 33 alloc/item: 0.33
length:98 capacity:1049867 allocations: 33 alloc/item: 0.33
length:99 capacity:1049867 allocations: 33 alloc/item: 0.33
length:100 capacity:1049867 allocations: 33 alloc/item: 0.33
--- Testing int[] ---
length: 1 capacity: 3 <-- allocations: 1 alloc/item: 1.00
length: 2 capacity: 3 allocations: 1 alloc/item: 0.50
length: 3 capacity: 3 allocations: 1 alloc/item: 0.33
length: 4 capacity: 7 <-- allocations: 2 alloc/item: 0.50
length: 5 capacity: 7 allocations: 2 alloc/item: 0.40
length: 6 capacity: 7 allocations: 2 alloc/item: 0.33
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.33
length: 10 capacity: 15 allocations: 3 alloc/item: 0.30
[... 80 more lines here ... ]
length:91 capacity:1048571 allocations: 24 alloc/item: 0.24
length:92 capacity:1048571 allocations: 24 alloc/item: 0.24
length:93 capacity:1048571 allocations: 24 alloc/item: 0.24
length:94 capacity:1048571 allocations: 24 alloc/item: 0.24
length:95 capacity:1048571 allocations: 24 alloc/item: 0.24
length:96 capacity:1048571 allocations: 24 alloc/item: 0.24
length:97 capacity:1048571 allocations: 24 alloc/item: 0.24
length:98 capacity:1048571 allocations: 24 alloc/item: 0.24
length:99 capacity:1048571 allocations: 24 alloc/item: 0.24
length:100 capacity:1048571 allocations: 24 alloc/item: 0.24
Ali
Re: Dynamic Array reserve
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
Re: Dynamic Array reserve
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
Re: Dynamic Array reserve
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
Dynamic Array reserve
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
Re: Garbage Collector profiling and the dynamic array reserve() function
On Wednesday, 18 October 2017 at 15:39:43 UTC, Steven Schveighoffer wrote: On 10/18/17 1:40 AM, Tony wrote: On Tuesday, 17 October 2017 at 13:27:24 UTC, Steven Schveighoffer wrote: I don't know what "allocations" represents, but reserve actually calls gc_malloc, and the others do not (the space is available to expand into the block). There should be only one allocation IMO. So there should be a bug report written for this? It all depends on what "allocations" means. I'd wait to find out from someone who is familiar with the GC profiling. -Steve I don't have a lot of clues on how the GC profiling work, but looking at reserve() it calls mem.xmalloc() for allocations which in fact calls GC.malloc(). Looking at the profiling for GC though: https://github.com/dlang/dmd/blob/69567a32c5bffae5513b41e7691c91b50766b552/src/ddmd/e2ir.d#L5952 It doesn't look like there's anything for array reserve calls, unless: [ RTLSYM_ALLOCMEMORY, RTLSYM_TRACEALLOCMEMORY ] are triggered from the allocations done in reserve(), but I have no idea about that.
Re: Garbage Collector profiling and the dynamic array reserve() function
On 10/18/17 1:40 AM, Tony wrote: On Tuesday, 17 October 2017 at 13:27:24 UTC, Steven Schveighoffer wrote: I don't know what "allocations" represents, but reserve actually calls gc_malloc, and the others do not (the space is available to expand into the block). There should be only one allocation IMO. So there should be a bug report written for this? It all depends on what "allocations" means. I'd wait to find out from someone who is familiar with the GC profiling. -Steve
Re: Garbage Collector profiling and the dynamic array reserve() function
On Tuesday, 17 October 2017 at 13:27:24 UTC, Steven Schveighoffer wrote: I don't know what "allocations" represents, but reserve actually calls gc_malloc, and the others do not (the space is available to expand into the block). There should be only one allocation IMO. -Steve So there should be a bug report written for this?
Re: Garbage Collector profiling and the dynamic array reserve() function
On 10/17/17 2:14 AM, Tony wrote:
Found this unanswered question on StackOverflow.
This program:
import std.stdio;
void add(ref int[] data)
{
data ~= 1;
data ~= 2;
}
void main()
{
int[] a;
writeln("capacity:",a.capacity);
auto cap = a.reserve(1000); // allocated may be more than requested
assert(cap >= 1000);
assert(cap == a.capacity);
writeln("capacity:",a.capacity);
a.add();
writeln(a);
}
compiled with "dmd -profile=gc"
has this output in profilegc.log
bytes allocated, allocations, type, function, file:line
4 1 int[] profiling.add profiling.d:8
4 1 int[] profiling.add profiling.d:7
The question is: why doesn't using reserve() cause an allocation to be
shown?
I don't know what "allocations" represents, but reserve actually calls
gc_malloc, and the others do not (the space is available to expand into
the block). There should be only one allocation IMO.
-Steve
Garbage Collector profiling and the dynamic array reserve() function
Found this unanswered question on StackOverflow.
This program:
import std.stdio;
void add(ref int[] data)
{
data ~= 1;
data ~= 2;
}
void main()
{
int[] a;
writeln("capacity:",a.capacity);
auto cap = a.reserve(1000); // allocated may be more than
requested
assert(cap >= 1000);
assert(cap == a.capacity);
writeln("capacity:",a.capacity);
a.add();
writeln(a);
}
compiled with "dmd -profile=gc"
has this output in profilegc.log
bytes allocated, allocations, type, function, file:line
4 1 int[] profiling.add profiling.d:8
4 1 int[] profiling.add profiling.d:7
The question is: why doesn't using reserve() cause an allocation
to be shown?
