www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Slice allocation after appending

reply Rekel <paultjeadriaanse gmail.com> writes:
According to the D slice article 
(https://dlang.org/articles/d-array-article.html), slices do not 
care where they start, only where they end, when checking whether 
expanding in place is permitable, or at least that is what I 
understood regarding it.

Now I'm unsure how to check this, I tried to a bit using the 
online editor and a bit of pointer usage which seemed to confirm 
my suspicion, but does this mean that taking a (small) slice at 
the end of a (possibly) very large dynamic array can lead to 
problematic behavior?
For example;


 int[] a = new int[10]; // Imagine this is very large
 int[] b = a[$-1..$];   // Small slice at the end
 b ~= 2;                // b extends, possibly in place
 a ~= -1;               // a no longer can, so the entire array 
 needs reallocating


(instead of be reallocating & a growing in place)

Again I'm not very certain I fully understood how slices are 
implemented, but is this example, and the problem I imagine it 
leading to, valid?
Dec 22 2020
next sibling parent Basile B. <b2.temp gmx.com> writes:
On Tuesday, 22 December 2020 at 22:12:29 UTC, Rekel wrote:

 According to the D slice article 
 (https://dlang.org/articles/d-array-article.html), slices do 
 not care where they start, only where they end, when checking 
 whether expanding in place is permitable, or at least that is 
 what I understood regarding it.

 Now I'm unsure how to check this, I tried to a bit using the 
 online editor and a bit of pointer usage which seemed to 
 confirm my suspicion, but does this mean that taking a (small) 
 slice at the end of a (possibly) very large dynamic array can 
 lead to problematic behavior?


No there's some runtime and GC magic under the hood. Appending on 
the slice is more like a smart "copy on append" operation so "a" 
will always ends with -1 and "b" with 2. It's described here : 
https://dlang.org/articles/d-array-article.html#how-it-works
Dec 22 2020
prev sibling next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 12/22/20 2:12 PM, Rekel wrote:


 Now I'm unsure how to check this, I tried to a bit using the online
 editor and a bit of pointer usage which seemed to confirm my suspicion,
 but does this mean that taking a (small) slice at the end of a
 (possibly) very large dynamic array can lead to problematic behavior?


Considering D's "no stomp" behavior with array elements, yes, that can 
happen.


 Again I'm not very certain I fully understood how slices are
 implemented, but is this example, and the problem I imagine it leading
 to, valid?


It is valid. One can always copy the small array before appending to it 
and the large array would be preserved. (Uncomment the "ADD THIS" line 
below.)

I added a nested function to your code to help visualize the states of 
the two arrays:

import std.stdio;
import std.meta;

void main() {
   int[] a = new int[10]; // Imagine this is very large
   int[] b = a[$-1..$];   // Small slice at the end

   auto info(string tag) {
     writefln!"\n(%s)"(tag);
     writeln("array      ptr            length    capacity");
     writeln("--------------------------------------------");
     static foreach (arr; AliasSeq!(a, b)) {
       writefln!"%-10s %s %8s %8s"(
         arr.stringof, arr.ptr, arr.length, arr.capacity);
     }
   }

   info("Before appending to b");
   // b = b.dup;    // <-- ADD THIS
   b ~= 2;                // b extends, possibly in place
   info("Before appending to a");
   a ~= -1;               // a no longer can, so the entire array needs
   info("At the end");
}

Try the -profile command line switch when compiling your program and it 
will show where memory allocations occur. Very helpful in exposing such 
problem spots...

Ali
Dec 22 2020
parent reply Rekel <paultjeadriaanse gmail.com> writes:
On Wednesday, 23 December 2020 at 04:03:37 UTC, Ali Çehreli wrote:


 It is valid. One can always copy the small array before 
 appending to it and the large array would be preserved.



 Try the -profile command line switch when compiling your 
 program and it will show where memory allocations occur. Very 
 helpful in exposing such problem spots...

 Ali


I'm not sure what your aliasSeq does, sadly I don't find the 
documentation's explanation satisfactory. Though thank's a lot, 
now I know what to take into account, & I didn't know about the 
-profile switch yet ^^
Dec 23 2020
parent reply frame <frame86 live.com> writes:
On Wednesday, 23 December 2020 at 11:19:38 UTC, Rekel wrote:


 I'm not sure what your aliasSeq does, sadly I don't find the 
 documentation's explanation satisfactory.


Try to write

static foreach (arr; [a, b]) { .. }

- it will not work because that loop is generated at compile time 
(static). It will generate the inside code for every usage later 
in code and for each element (a and b) so the 2 lines inside will 
be compiled to 4 lines really when you call info().

But the compiler cannot access the values of a and b at compile 
time (which it thinks it should by using "static" in this case) 
so we need to say the compiler:

- do not use value or address of [a, b] directly
- instead, use [a, b] as symbol - just prepare the code for later 
usage

This is what AliasSeq! does in this example. You can put all 
static stuff inside an AliasSequence:

41      = literal/value
int     = type
int[]   = type
int[] a = symbol/alias


Here it contains not values but the symbols to it. That 
implementation can become very handy for some situations but for 
this simple case

foreach (arr; [a, b]) { .. }

would also work. The difference is that the foreach loop is 
happen at runtime and will not compiled as multiple lines.
Dec 23 2020
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 12/23/20 8:14 AM, frame wrote:


 That implementation
 can become very handy for some situations but for this simple case

 foreach (arr; [a, b]) { .. }

 would also work.


Absolutely.


 The difference is that the foreach loop is happen at
 runtime and will not compiled as multiple lines.


AliasSeq also allowed me to print the names of the local array variables 
'a' and 'b'.

Ali
Dec 23 2020
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 12/22/20 5:12 PM, Rekel wrote:

 According to the D slice article 
 (https://dlang.org/articles/d-array-article.html), slices do not care 
 where they start, only where they end, when checking whether expanding 
 in place is permitable, or at least that is what I understood regarding it.
 
 Now I'm unsure how to check this, I tried to a bit using the online 
 editor and a bit of pointer usage which seemed to confirm my suspicion, 
 but does this mean that taking a (small) slice at the end of a 
 (possibly) very large dynamic array can lead to problematic behavior?


Problematic in what way? It will not stomp on data that is live. So I'd 
say it's the opposite of problematic.

You can check whether an append will reallocate or not by checking the 
capacity. If arr.capacity <= arr.length, then an append will reallocate.


 For example;
 

 int[] a = new int[10]; // Imagine this is very large
 int[] b = a[$-1..$];   // Small slice at the end
 b ~= 2;                // b extends, possibly in place
 a ~= -1;               // a no longer can, so the entire array
needs 
 reallocating


 (instead of be reallocating & a growing in place)


For sure a will need reallocating. The runtime cannot know that you will 
append with a, so it uses the space for b.

If you'd rather b reallocate, you can use the concatenation operator on 
it instead:

b = b ~ 2;

Or you can manage the array allocations yourself without using the 
runtime (see std.array.Appender).


 
 Again I'm not very certain I fully understood how slices are 
 implemented, but is this example, and the problem I imagine it leading 
 to, valid?


Is the description you have valid? yes. Is it a problem with the 
implementation? I'd say no. If you change your expectations, you can 
avoid this situation easily.

-Steve
Dec 23 2020