Thread overview | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
December 22, 2020 Slice allocation after appending | ||||
---|---|---|---|---|
| ||||
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? |
December 23, 2020 Re: Slice allocation after appending | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rekel | 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 |
December 22, 2020 Re: Slice allocation after appending | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rekel | 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 |
December 23, 2020 Re: Slice allocation after appending | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli | 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 ^^ |
December 23, 2020 Re: Slice allocation after appending | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rekel | 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 |
December 23, 2020 Re: Slice allocation after appending | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rekel | 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.
|
December 23, 2020 Re: Slice allocation after appending | ||||
---|---|---|---|---|
| ||||
Posted in reply to frame | 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 |
Copyright © 1999-2021 by the D Language Foundation