www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - I don't like slices in D

reply "Vitali" <notavailable mail.com> writes:
I expected slices to be in D (http://dlang.org/arrays.html) like 
they are in Go 
(http://blog.golang.org/go-slices-usage-and-internals). But they 
are not.

Why the array have to be reallocated after the length of a slice 
is changed? It makes slices useless.

Here a little example (it fails):

   void testSlices() {
     int[] dArr = [10, 11, 12];
     int[] dSlice = dArr[0..2];
     dSlice.length++;
     assert(dArr[2]==dSlice[2]); // failure
   }
Oct 17 2013
next sibling parent reply "David Eagen" <davideagen mailinator.com> writes:
On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
 I expected slices to be in D (http://dlang.org/arrays.html) 
 like they are in Go 
 (http://blog.golang.org/go-slices-usage-and-internals). But 
 they are not.

 Why the array have to be reallocated after the length of a 
 slice is changed? It makes slices useless.

 Here a little example (it fails):

   void testSlices() {
     int[] dArr = [10, 11, 12];
     int[] dSlice = dArr[0..2];
     dSlice.length++;
     assert(dArr[2]==dSlice[2]); // failure
   }

Change your slice to int[] dSlice = dArr[0..$] or [0..3]; The way you are doing it only takes the first 2 elements. Modified code: import std.stdio : writeln; void main() { int[] dArr = [10, 11, 12]; int[] dSlice = dArr[0..$]; assert(dArr[2] is dSlice[2]); // passes dSlice.length++; assert(dArr[2] == dSlice[2]); // passes }
Oct 17 2013
next sibling parent Lionello Lunesu <lionello lunesu.remove.com> writes:
On 10/17/13 22:03, Vitali wrote:
    // but what is the purpose of this?

auto arr1 = [1,2,3]; auto arr2 = arr1; arr2.length--; arr2 ~= 4; // append 4 What do you expect arr1[2] is? | | | | | | | | | | v It's the original value 3! Which makes sense: why would the slice affect the original array? If that were the case you wouldn't be able to safely pass a slice of a big array to any function.
Oct 17 2013
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/17/13 10:45 PM, Jesse Phillips wrote:
 I believe this
 was the behavior of D1, is not true in D2 and must not be true for
 immutable arrays such as string.

Yes, there have been repeated discussions in this group about changing that behavior, it created pernicious long-distance dependencies (someone would pass a slice to someone else, and they'd start trampling into the caller's data. For a while it seemed there would be no reasonable solution, until we finally figured the whole capacity caching thing. Andrei
Oct 18 2013
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
 I expected slices to be in D (http://dlang.org/arrays.html) 
 like they are in Go 
 (http://blog.golang.org/go-slices-usage-and-internals). But 
 they are not.

 Why the array have to be reallocated after the length of a 
 slice is changed? It makes slices useless.

 Here a little example (it fails):

   void testSlices() {
     int[] dArr = [10, 11, 12];
     int[] dSlice = dArr[0..2];
     dSlice.length++;
     assert(dArr[2]==dSlice[2]); // failure
   }

What's the use case for this? I haven't found myself ever needing something like that so far, but i'd be open to seeing an example.
Oct 17 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 10/17/2013 11:41 AM, Vitali wrote:

 On Thursday, 17 October 2013 at 18:29:47 UTC, John Colvin wrote:
 On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
 I expected slices to be in D (http://dlang.org/arrays.html) like they
 are in Go (http://blog.golang.org/go-slices-usage-and-internals). But
 they are not.

 Why the array have to be reallocated after the length of a slice is
 changed? It makes slices useless.

 Here a little example (it fails):

  void testSlices() {
    int[] dArr = [10, 11, 12];
    int[] dSlice = dArr[0..2];
    dSlice.length++;
    assert(dArr[2]==dSlice[2]); // failure
  }

What's the use case for this? I haven't found myself ever needing something like that so far, but i'd be open to seeing an example.

The use case is: void appendElement(ref int[] arr, int x) { arr ~= x;

That will not allocate if there is capacity.
 }

 void removeElement(ref int[] arr, int index) {
    arr = arr[0..index] ~ arr[index+1..$];

It must necessarily allocate, right? How does Go deal with that case? However, I see that the capacity of arr after that operation is just 3! Since a new array is allocated by the runtime, the capacity of arr could be larger as well. Perhaps that's the only problem here. (?)
 }

 void main() {
    int[] arr = [1, 2, 3];
    arr.reserve(7);       // Reserve capacity.
    arr.appendElement(4); // Here should be
    arr.removeElement(1); // no realocation of array,
    arr.appendElement(5); // but it is.
    assert(arr[1] == 3);
    assert(arr[2] == 4);
    assert(arr[3] == 5);
 }

 But maybe I don't understand what slices are for in D. Anyway in Go this
 works whithout reallocation.

Ali
Oct 17 2013
prev sibling next sibling parent "Vitali" <notavailable mail.com> writes:
On Thursday, 17 October 2013 at 18:21:30 UTC, David Eagen wrote:
 On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
 I expected slices to be in D (http://dlang.org/arrays.html) 
 like they are in Go 
 (http://blog.golang.org/go-slices-usage-and-internals). But 
 they are not.

 Why the array have to be reallocated after the length of a 
 slice is changed? It makes slices useless.

 Here a little example (it fails):

  void testSlices() {
    int[] dArr = [10, 11, 12];
    int[] dSlice = dArr[0..2];
    dSlice.length++;
    assert(dArr[2]==dSlice[2]); // failure
  }

Change your slice to int[] dSlice = dArr[0..$] or [0..3]; The way you are doing it only takes the first 2 elements. Modified code: import std.stdio : writeln; void main() { int[] dArr = [10, 11, 12]; int[] dSlice = dArr[0..$]; assert(dArr[2] is dSlice[2]); // passes dSlice.length++; assert(dArr[2] == dSlice[2]); // passes }

This doesn't answer my question. I repeat my question: "Why does a reallocation accure AFTER a resize of the length of a slice, although there is still capacity?"
Oct 17 2013
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 10/17/2013 11:00 AM, Vitali wrote:

 I expected slices to be in D (http://dlang.org/arrays.html)

There is also this article: http://dlang.org/d-array-article.html
 like they
 are in Go (http://blog.golang.org/go-slices-usage-and-internals). But
 they are not.

Every design comes with pros and cons. Go's slices can do that because they consis of three members: pointer, length, and capacity. Apparently they also know the actual array that they provide access to. D slices have only the first two of those members. (However, the capacity can still be obtained by the function capacity(), which is ordinarily called with the property syntax.)
 Why the array have to be reallocated after the length of a slice is
 changed?

The effect of incrementing length is adding an element to the end. Since slices don't own the underlying array elements, in order to preserve the potential element beyond their current end, the entire slice gets relocated. As described in the article above, this does not happen every time.
 It makes slices useless.

Slices have been very useful so far. Slices do have some gotchas, neither of which have been showstoppers.
 Here a little example (it fails):

    void testSlices() {
      int[] dArr = [10, 11, 12];
      int[] dSlice = dArr[0..2];
      dSlice.length++;

That operation has a potential of relocating the slice. You can check whether that will be the case: if (slice.capacity == 0) { /* Its elements would be relocated if one more element * is added to this slice. */ // ... } else { /* This slice may have room for new elements before * needing to be relocated. Let's calculate how * many: */ auto howManyNewElements = slice.capacity - slice.length; // ... }
      assert(dArr[2]==dSlice[2]); // failure
    }

Ali
Oct 17 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 10/17/2013 03:33 PM, Sean Kelly wrote:

 I'd be curious to see if this would ever relocate:

 int[] dArr = [10,11,12];
 const(int)[] dSlice = dArr[0..2];
 dSlice.length++;

 It shouldn't, since growing a const slice can never clobber the
 underlying array,

However, according to spec, the appended elements must be 0. There is an optimization opportunity if the elements beyond dSlice's end were all zeros and if the type system guaranteed that they were immutable. Only then dSlice's relocation could be elided.
 but I don't know if the current implementation handles
 this case.  Still, growing a const slice seems like a pretty useless
 thing to do, since you can only expect to end up with default values at
 the end.

Still, that may be desired to avoid special-casing the elements at the end. It would be simpler to append zeros and just use them. Ali
Oct 17 2013
prev sibling next sibling parent "Vitali" <notavailable mail.com> writes:
On Thursday, 17 October 2013 at 18:29:47 UTC, John Colvin wrote:
 On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
 I expected slices to be in D (http://dlang.org/arrays.html) 
 like they are in Go 
 (http://blog.golang.org/go-slices-usage-and-internals). But 
 they are not.

 Why the array have to be reallocated after the length of a 
 slice is changed? It makes slices useless.

 Here a little example (it fails):

  void testSlices() {
    int[] dArr = [10, 11, 12];
    int[] dSlice = dArr[0..2];
    dSlice.length++;
    assert(dArr[2]==dSlice[2]); // failure
  }

What's the use case for this? I haven't found myself ever needing something like that so far, but i'd be open to seeing an example.

The use case is: void appendElement(ref int[] arr, int x) { arr ~= x; } void removeElement(ref int[] arr, int index) { arr = arr[0..index] ~ arr[index+1..$]; } void main() { int[] arr = [1, 2, 3]; arr.reserve(7); // Reserve capacity. arr.appendElement(4); // Here should be arr.removeElement(1); // no realocation of array, arr.appendElement(5); // but it is. assert(arr[1] == 3); assert(arr[2] == 4); assert(arr[3] == 5); } But maybe I don't understand what slices are for in D. Anyway in Go this works whithout reallocation.
Oct 17 2013
prev sibling next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
 I expected slices to be in D (http://dlang.org/arrays.html) 
 like they are in Go 
 (http://blog.golang.org/go-slices-usage-and-internals). But 
 they are not.

 Why the array have to be reallocated after the length of a 
 slice is changed? It makes slices useless.

 Here a little example (it fails):

   void testSlices() {
     int[] dArr = [10, 11, 12];
     int[] dSlice = dArr[0..2];
     dSlice.length++;
     assert(dArr[2]==dSlice[2]); // failure
   }

As David Eagen said, your problem is that in D, dArr[0..2] is not inclusive, it's exclusive, so you get dArr[0] and dArr[1]. Changing it to dSlice = dArr[0..3] will work (or better, dArr[0..$]). However, there's something else going on here that's fishy: void testSlices() { int[] dArr = [10, 11, 12]; int[] dSlice = dArr[0..2]; writeln(dArr.ptr, " ", dArr.capacity, " ", dArr.length); writeln(dSlice.ptr, " ", dSlice.capacity, " ", dSlice.length); dSlice.length++; writeln(dSlice.ptr, " ", dSlice.capacity, " ", dSlice.length); writeln(dArr); writeln(dSlice); } 4002DFF0 3 3 4002DFF0 0 2 4002DFE0 3 3 [10, 11, 12] [10, 11, 0] dSlice says that it has length 2, but accessing dSlice[2] does not produce a RangeError... Likewise, printing it out prints 3 elements, not 2. This looks like a bug to me.
Oct 17 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
 dSlice says that it has length 2,

That's before appending an element.
 but accessing dSlice[2] does not
 produce a RangeError...

That's after appending an element. Ali
Oct 17 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Thursday, 17 October 2013 at 18:41:53 UTC, Vitali wrote:
   arr = arr[0..index] ~ arr[index+1..$];

This line is where the reallocation happens. a ~ b on built in arrays and slices, ALWAYS allocates to ensure it doesn't stomp over some other in-use memory. ~= can extend if there's capacity, but ~ always makes a new array without modifying the input. Ali linked to the array article that explains the implementation in more detail. The remove function should copy the data itself instead of using the ~ operator if you want it to operate in place.
Oct 17 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, October 17, 2013 20:31:26 Vitali wrote:
 I repeat my question: "Why does a reallocation accure AFTER a
 resize of the length of a slice, although there is still
 capacity?"

Because it _doesn't_ have the capacity. If you do writeln(dSlice.capacity); before incrementing dSlice's length, it'll print out 0. dSlice can't grow in place, because if it did, its new elements would overlap with those of dArr; dArr -> [10, 11, 12] dSlice -> [10, 11] ++dSlice.length; dArr -> [10, 11, 12] dSlice -> [10, 11, 0] You can't make a slice cover more of another array without reslicing that array. e.g. dSlice = dArr[0 .. $] dArr -> [10, 11, 12] dSlice -> [10, 11, 12] Appending to a slice or increasing its length (which is just appending to it with the init value of its element type) is adding a new element which is not part of any other array. If there is capacity available, then that will be done in place, and the slice will still be a slice of the array that it was sliced from. But if there isn't any capacity available (and there isn't in your example, because the original array has that space), then the runtime is forced to reallocate the slice in order to make space, and then it's no longer a slice of the original array. - Jonathan M Davis
Oct 17 2013
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 17 October 2013 at 18:51:08 UTC, Meta wrote:
 As David Eagen said, your problem is that in D, dArr[0..2] is 
 not inclusive, it's exclusive, so you get dArr[0] and dArr[1]. 
 Changing it to dSlice = dArr[0..3] will work (or better, 
 dArr[0..$]). However, there's something else going on here 
 that's fishy:

 void testSlices()
 {
 	int[] dArr = [10, 11, 12];
 	int[] dSlice = dArr[0..2];
 	writeln(dArr.ptr, " ", dArr.capacity, " ", dArr.length);
 	writeln(dSlice.ptr, " ", dSlice.capacity, " ", dSlice.length);

 	dSlice.length++;
 	writeln(dSlice.ptr, " ", dSlice.capacity, " ", dSlice.length);

 	writeln(dArr);
 	writeln(dSlice);
 }

 4002DFF0 3 3
 4002DFF0 0 2
 4002DFE0 3 3
 [10, 11, 12]
 [10, 11, 0]

 dSlice says that it has length 2, but accessing dSlice[2] does 
 not produce a RangeError... Likewise, printing it out prints 3 
 elements, not 2. This looks like a bug to me.

Never mind, that was extremely silly of me.
Oct 17 2013
prev sibling next sibling parent "Vitali" <notavailable mail.com> writes:
I didn't expect that you would doubt that the array gets 
reallocated. Here a code to test:

void appendElement(ref int[] arr, int x) {
	arr ~= x;
}

void removeElement(ref int[] arr, int index) {
	arr = arr[0..index] ~ arr[index+1..$];
}

void main() {
   int* arrPtr1;
   int* arrPtr2;
   int[] arr = [1, 2, 3];

   arr.reserve(7);       // Reserve capacity.
   arr.appendElement(4); // I don't want a realocation
   arrPtr1 = arr.ptr;
   assert(arr.capacity==7);
   arr.removeElement(1); // happen here,
   assert(arr.capacity==3);
   arr.appendElement(5); // but it happens.
   arrPtr2 = arr.ptr;

   assert(arr[1] == 3);
   assert(arr[2] == 4);
   assert(arr[3] == 5);
   assert(arrPtr1 != arrPtr2);  // different arrays <- here
}

I'm not accusing D having a bug here. I'm saying that in my eyes 
a reallocation of the array referenced by the slice is not 
useful, when capacity is still available.

 Ali Çehreli: You are right, Go's slices consist of three 
members. I have read it, although I din't test the code. In 
http://blog.golang.org/go-slices-usage-and-internals is said:
   "Slicing does not copy the slice's data. It creates a new slice 
value that points to the original array. This makes slice 
operations as efficient as manipulating array indices."

I repeat "[...] as efficient as manipulating array indices." In D 
this is not the case and can't imagine what purpose can it suit 
else.

 Meta and  David Eagen: My question is not about creating slices, 
but about make them shrink and grow without reallocating the 
referenced array.
Oct 17 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Thursday, 17 October 2013 at 19:23:37 UTC, Vitali wrote:
 I'm not accusing D having a bug here. I'm saying that in my 
 eyes a reallocation of the array referenced by the slice is not 
 useful, when capacity is still available.

There is no capacity available for the binary concatenation like that. Given this: arr = arr[0..index] ~ arr[index+1..$]; arr[index] is, as far as this function can tell anyway, still in use. The concat operator never overwrites in-use data. Consider this example: int[] a = [1,2,3,4]; void foo(int[] b) { int[] c = b ~ 4; } foo(a[0 .. 2]); Surely you wouldn't expect a == [1,2,4] now. But, that's what would happen if your function remove function didn't allocate! a[0 .. 2] would become [1,2] with a capacity of 4, because that's the original length. Then b ~ 4 sees that there's capacity, and then appends in place, writing b.length++; b[3] = 4; but assert(&b[3] is &a[3]), so that just overwrote a's data. But since b and c are both local variables, that's certainly not what you intended. Your example is a little less clear, since it takes the slice by reference, but it is still the same idea: there might be other slices to that same data that should not be overwritten. A new allocation is the only way to be sure. If you want to overwrite it though, your remove function can just copy the data itself without reallocation.
   "Slicing does not copy the slice's data. It creates a new 
 slice value that points to the original array. This makes slice 
 operations as efficient as manipulating array indices."

D does slicing the same way. Your problem is with appending/concatenating.
Oct 17 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, October 17, 2013 21:23:36 Vitali wrote:
  Meta and  David Eagen: My question is not about creating slices,
 but about make them shrink and grow without reallocating the
 referenced array.

The only way to make a slice "grow" and slice more of the array that it was a slice of is to reslice the original array and have the new slice be bigger. There isn't really any difference between a slice of an array and an array in D. They're both slices of a block of memory that the runtime owns. It's just that when you create an array by slicing an existing array, they end up referring to the same elements until one of them gets reallocated (which generally occurs when you append to one of them, and there is no available capacity for that array to grow - either because it's at the end of that block of memory or because another array refers to the memory past the end of that array). So, while a slice of an array is effectively a window into that array, it's really that both arrays are windows into a block of memory that the runtime owns, and so the runtime isn't going to treat an array differently just because it was created from slicing another array instead of by explicitly allocating it. In general, when you slice arrays, and you want the slice to continue to refer to the same elements, you only shrink the slice (generally by slicing it further, though you can also decrement its length), and if you want to increase the slice and still have it refer to the same elements as the original array rather than having it reallocate, then you need to reslice the original array with a greater length rather than manipulating the length of the current slice. - Jonathan M Davis
Oct 17 2013
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
 Why the array have to be reallocated after the length of a 
 slice is changed? It makes slices useless.

No, it doesn't. They are extremely helpful, particularly for high-performance applications.
 Here a little example (it fails):

   void testSlices() {
     int[] dArr = [10, 11, 12];
     int[] dSlice = dArr[0..2];
     dSlice.length++;
     assert(dArr[2]==dSlice[2]); // failure
   }

Of course it does. Increasing the length of an array causes the new elements to be default-allocated by the language spec, and as dArr and dSlice share the same memory, not reallocating dSlice would clobber the third element of dArr.
Oct 17 2013
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 17 October 2013 at 18:00:20 UTC, Vitali wrote:
     int[] dArr = [10, 11, 12];
     int[] dSlice = dArr[0..2];

Oh, and there is no difference between dynamic arrays and slices of them in D (as shown by the fact that the type is the same). David
Oct 17 2013
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 17 October 2013 at 18:41:53 UTC, Vitali wrote:
 void removeElement(ref int[] arr, int index) {
   arr = arr[0..index] ~ arr[index+1..$];
 }

If you know that 'arr' is the only reference to this piece of data, you can use arr.assumeSafeAppend() to enable re-use of the remaining storage: http://dlang.org/phobos/object.html#.assumeSafeAppend David
Oct 17 2013
prev sibling next sibling parent "Vitali" <notavailable mail.com> writes:
On Thursday, 17 October 2013 at 19:05:32 UTC, Jonathan M Davis 
wrote:
 before incrementing dSlice's length, it'll print out 0. dSlice 
 can't grow in
 place, because if it did, its new elements would overlap with 
 those of dArr;

 dArr -> [10, 11, 12]
 dSlice -> [10, 11]

Well this is only one part that makes no sense in my eyes. I thought the slices should be overlaping. Here, step by step: void main() { int* arrPtr1; int* arrPtr2; int[] arr = [1, 2, 3]; arrPtr1 = arr.ptr; arr.reserve(5); // reserve capacity arrPtr2 = arr.ptr; assert(arrPtr1 != arrPtr2); // ok, this makes sense assert(arr.capacity==7); // ok, this makes not so // much sense, but it's bigger than 5, // I guess it's ok // I reserved extra capacity. I got more // than I needed, but ok. arr ~= 4; // appending an element assert(arr[3]==4); arrPtr1 = arr.ptr; assert(arrPtr1==arrPtr2); // no reallocation, assert(arr.capacity==7); // good // I have enough capacity to append an // element; everything went fine arr.length++; assert(arr[4]==0 && arr.length==5); arrPtr1 = arr.ptr; assert(arrPtr1==arrPtr2); // still no reallocation, assert(arr.capacity==7); // very good // Also the direct manipulation of // the length works, as long as a // value is assigned that is bigger // then the length. arr.length--; arrPtr1 = arr.ptr; assert(arrPtr1==arrPtr2); // good, but.. assert(arr.capacity==0); // <- WHY ?? // after the length is reduced the // capacity is set to ZERO, this will // cause the array to be reallocated when // the length is increased by next time, // but what is the purpose of this? arr.length++; arrPtr1 = arr.ptr; assert(arrPtr1!=arrPtr2); // different arrays now! assert(arr.capacity==7); // yes, as expected }
Oct 17 2013
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 17 October 2013 at 19:23:37 UTC, Vitali wrote:
 I repeat "[...] as efficient as manipulating array indices." In 
 D this is not the case and can't imagine what purpose can it 
 suit else.

This is also the case for D. Without knowing the Go design in detail, I'd say the major difference between them is that in D, you can always be sure that *extending* a slice never leads to overwriting some memory you don't know about: --- void appendAnswer(int[] data) { data ~= 42; } void main() { auto a = [1, 2, 3, 4]; auto b = a[0 .. $ - 1]; void dump() { import std.stdio; writefln("a = %s, b = %s (%s)", a, b, b.capacity); } dump(); // Now let's assume b would still have all the capacity. b.assumeSafeAppend(); dump(); appendAnswer(b); dump(); } --- The D design makes sure that if your piece of code hands off a slice into some buffer, other parts can (by default) never end up actually modifying anything but that slice. There is quite a benefit to that, design-wise. David
Oct 17 2013
prev sibling next sibling parent "Vitali" <notavailable mail.com> writes:
On Thursday, 17 October 2013 at 20:01:37 UTC, David Nadlinger 
wrote:
 On Thursday, 17 October 2013 at 18:41:53 UTC, Vitali wrote:
 void removeElement(ref int[] arr, int index) {
  arr = arr[0..index] ~ arr[index+1..$];
 }

If you know that 'arr' is the only reference to this piece of data, you can use arr.assumeSafeAppend() to enable re-use of the remaining storage: http://dlang.org/phobos/object.html#.assumeSafeAppend David

This is maybe what I have missed. I will take a closer look on it. Thank you. Thanks for every one who has posted here. I think the function mentioned by David Nadlinger will solve my problems. That's all for today ^^.
Oct 17 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, October 17, 2013 22:24:43 Vitali wrote:
 On Thursday, 17 October 2013 at 20:01:37 UTC, David Nadlinger
 
 wrote:
 On Thursday, 17 October 2013 at 18:41:53 UTC, Vitali wrote:
 void removeElement(ref int[] arr, int index) {
 
 arr = arr[0..index] ~ arr[index+1..$];
 
 }

If you know that 'arr' is the only reference to this piece of data, you can use arr.assumeSafeAppend() to enable re-use of the remaining storage: http://dlang.org/phobos/object.html#.assumeSafeAppend David

This is maybe what I have missed. I will take a closer look on it. Thank you. Thanks for every one who has posted here. I think the function mentioned by David Nadlinger will solve my problems. That's all for today ^^.

Based on your responses, I suspect that you don't quite understand how slices work in D, and you're just going to shoot yourself in the foot by using assumeSafeAppend. If you haven't already read it, please read this article on arrays: http://dlang.org/d-array-article.html It should be enlightening. - Jonathan M Davis
Oct 17 2013
prev sibling next sibling parent "Sean Kelly" <sean invisibleduck.org> writes:
On Thursday, 17 October 2013 at 18:33:01 UTC, Ali Çehreli wrote:
 On 10/17/2013 11:00 AM, Vitali wrote:
 Here a little example (it fails):

    void testSlices() {
      int[] dArr = [10, 11, 12];
      int[] dSlice = dArr[0..2];
      dSlice.length++;

That operation has a potential of relocating the slice.

I'd be curious to see if this would ever relocate: int[] dArr = [10,11,12]; const(int)[] dSlice = dArr[0..2]; dSlice.length++; It shouldn't, since growing a const slice can never clobber the underlying array, but I don't know if the current implementation handles this case. Still, growing a const slice seems like a pretty useless thing to do, since you can only expect to end up with default values at the end.
Oct 17 2013
prev sibling next sibling parent "qznc" <qznc web.de> writes:
On Thursday, 17 October 2013 at 18:41:53 UTC, Vitali wrote:
 The use case is:

 void removeElement(ref int[] arr, int index) {
   arr = arr[0..index] ~ arr[index+1..$];
 }

The meaning of this code is: Create a new array out of composing two slices and assign it to arr. Of course, there is allocation happening. What you probably want is: Move arr elements index+1..$ to index..$-1 and decrease length by one, preserving capacity. You can use std.algorithm.remove, which does move part. Hence: import std.algorithm: remove; void removeElement(ref int[] arr, int index) { remove(arr,index); arr.length--; }
Oct 17 2013
prev sibling next sibling parent "Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:
On Thursday, 17 October 2013 at 20:03:53 UTC, Vitali wrote:
   arrPtr1 = arr.ptr;
   arr.reserve(5);     // reserve capacity
   arrPtr2 = arr.ptr;
   assert(arrPtr1 != arrPtr2); // ok, this makes sense
   assert(arr.capacity==7); // ok, this makes not so
   // much sense, but it's bigger than 5,
   // I guess it's ok

   // I reserved extra capacity. I got more
   // than I needed, but ok.

It will reserve enough memory for the requested size, in doing so it will allocate on some hardware friendly boundary. (Others here have a better grasp on why and what that is).
   arr.length--;
   arrPtr1 = arr.ptr;
   assert(arrPtr1==arrPtr2); // good, but..
   assert(arr.capacity==0); // <- WHY ??

   // after the length is reduced the
   // capacity is set to ZERO, this will
   // cause the array to be reallocated when
   // the length is increased by next time,
   // but what is the purpose of this?

Who owns (arrPtr1 + 4)? You've asked arr to relinquish ownership. While arrPtr1&2 can't claim ownership because they are pointers, arr2 could exist somewhere in the program. arr2 could have been declared: auto arr2 = arr[2..$]; arr2[$-1] = 9; assert(arr[$-1] == arr2[$-1]); // both reference same array arr.length--; arrPtr1 = arr.ptr; assert(arrPtr1==arrPtr2); assert(arr.capacity==0); assert(arr2.capacity==5); // So to perform the operation: arr.length++; Are you expecting: assert(arr[$-1] == arr2[$-1]); // It appears this is true in Go Now take a look at what happens to capacity if we remove the shrinking. auto arr3 = arr2[1..$]; assert(arr2.capacity == 5); assert(arr3.capacity == 4); arr3.length++; assert(arr2.capacity == 0); assert(arr3.capacity == 4); Full code: http://dpaste.dzfl.pl/ddcf5ff4 Go code is unsafe, it overwrites your other slice data. I believe this was the behavior of D1, is not true in D2 and must not be true for immutable arrays such as string. Go code: http://ideone.com/QEy0v5
Oct 17 2013
prev sibling next sibling parent "Vitali" <notavailable mail.com> writes:
On Thursday, 17 October 2013 at 22:30:52 UTC, Jonathan M Davis 
wrote:
 http://dlang.org/d-array-article.html

 It should be enlightening.

Yes, now I understand this article, but only after I had this long discussion here. The relevant statement for me is "The responsible party for managing a dynamic array's memory is the D runtime." For me this means that the programmer isn't suppose to manage allocation and reallocation of the array, because it is abstracted by the slices. Well, if it's so, then I have doubts that it will help to write performant code, BECAUSE of the abstraction. With this in mind I take back everything I said about slices and leave only a doubt that slices are performant. --- To clarify previous things: Whether the concatenation "~=" appends without or with reallocation, depends on the available capacity of the left slice. The concatenation "~" never reallocates and creates always a new slice with capacity of 0. My prevoius example of the function "removeElement(ref int[], int)" will not work. The right implementation would be: void removeElement(ref int[] arr, int index) { arr[index..$-1] = arr[index+1..$].dup; arr.length--; arr.assumeSafeAppend(); }
Oct 18 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Friday, 18 October 2013 at 13:38:01 UTC, Vitali wrote:
   My prevoius example of the function "removeElement(ref int[], 
 int)" will not work. The right implementation would be:
 void removeElement(ref int[] arr, int index) {
   arr[index..$-1] = arr[index+1..$].dup;

.dup allocates a copy. The right implementation would be to copy the data yourself, then reduce length, and then just leave it at that. void removeElement(ref int[] arr, int index) { for(size_t idx = index; idx < arr.length - 1; idx++) arr[idx] = arr[idx + 1]; arr.length = arr.length - 1; // arr.length-- won't compile due to silliness }
Oct 18 2013
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Friday, 18 October 2013 at 14:27:36 UTC, Adam D. Ruppe wrote:
     for(size_t idx = index; idx < arr.length - 1; idx++)
         arr[idx] = arr[idx + 1];

You can do it via slice element-wise assignment: arr[index..$-1][] = arr[index+1..$][]
Oct 18 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Adam D. Ruppe:

     arr.length = arr.length - 1; // arr.length-- won't compile 
 due to silliness

This code now compiles, the bug was fixed: void foo(ref int[] arr) { arr.length--; } void main() {} Bye, bearophile
Oct 18 2013
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Friday, 18 October 2013 at 14:29:44 UTC, Dicebot wrote:
 On Friday, 18 October 2013 at 14:27:36 UTC, Adam D. Ruppe wrote:
    for(size_t idx = index; idx < arr.length - 1; idx++)
        arr[idx] = arr[idx + 1];

You can do it via slice element-wise assignment: arr[index..$-1][] = arr[index+1..$][]

Ah, nvm, it will trigger an exception for overlapping source and dest.
Oct 18 2013
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Friday, 18 October 2013 at 14:29:44 UTC, Dicebot wrote:
 You can do it via slice element-wise assignment:

nope, run the copy syntax and get this: object.Error: overlapping array copy (unless this was changed recently too)
Oct 18 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Dicebot:

 You can do it via slice element-wise assignment:

 arr[index..$-1][] = arr[index+1..$][]

Overlapping slices error. You have to copy with Phobos... Bye, bearophile
Oct 18 2013
prev sibling next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Friday, 18 October 2013 at 13:38:01 UTC, Vitali wrote:
 With this in mind I take back everything I said about slices 
 and leave only a doubt that slices are performant.

By avoiding the concatenation operators and expansion through increasing the length property, slices can be used separately from the runtime's opaque dynamic array type. Slices can be backed by any memory by slicing a pointer or fixed-length array. Also, slices with compile-time initializers are backed either by TLS or global memory. There is also one incidence in the language where such a non-runtime-backed slice appears implicitly: --- void foo(int[] numbers...); void main() { foo([1, 2]); // Uses a GC-managed array for `numbers` foo(1, 2); // Uses a stack-allocated array for `numbers` } ---
Oct 18 2013
prev sibling next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 19 October 2013 at 03:46:52 UTC, Jakob Ovrum wrote:
 By avoiding the concatenation operators and expansion through 
 increasing the length property, slices can be used separately 
 from the runtime's opaque dynamic array type. Slices can be 
 backed by any memory by slicing a pointer or fixed-length 
 array. Also, slices with compile-time initializers are backed 
 either by TLS or global memory.

Also, string literals are backed by global memory (sometimes ROM).
 There is also one incidence in the language where such a 
 non-runtime-backed slice appears implicitly:

To clarify: there is one incidence where a slice of *stack memory* is implicitly created.
Oct 18 2013
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 17 Oct 2013 23:45:18 -0400, Ali =C3=87ehreli <acehreli yahoo.com=
 wrote:

 On 10/17/2013 03:33 PM, Sean Kelly wrote:

  > I'd be curious to see if this would ever relocate:
  >
  > int[] dArr =3D [10,11,12];
  > const(int)[] dSlice =3D dArr[0..2];
  > dSlice.length++;
  >
  > It shouldn't, since growing a const slice can never clobber the
  > underlying array,

 However, according to spec, the appended elements must be 0. There is =

 optimization opportunity if the elements beyond dSlice's end were all =

 zeros and if the type system guaranteed that they were immutable. Only=

 then dSlice's relocation could be elided.

(catching up on D forums) Ali is correct, the above code will always reallocate. Underneath, the = array runtime has no specialized code to deal with const, only shared. In reality, the dSlice.length++ line is equivalent to doing: dSlice ~=3D int.init; for all flavors of const. -Steve
Jan 14 2014
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 18 Oct 2013 01:45:30 -0400, Jesse Phillips  
<Jesse.K.Phillips+D gmail.com> wrote:

 On Thursday, 17 October 2013 at 20:03:53 UTC, Vitali wrote:
   arrPtr1 = arr.ptr;
   arr.reserve(5);     // reserve capacity
   arrPtr2 = arr.ptr;
   assert(arrPtr1 != arrPtr2); // ok, this makes sense
   assert(arr.capacity==7); // ok, this makes not so
   // much sense, but it's bigger than 5,
   // I guess it's ok

   // I reserved extra capacity. I got more
   // than I needed, but ok.

It will reserve enough memory for the requested size, in doing so it will allocate on some hardware friendly boundary. (Others here have a better grasp on why and what that is).

The memory allocator works in powers of 2 bytes from 16 to PAGE size. A D array has runtime data to maintain inside the block, which is why the resulting array length is a power of 2 - 1. For instance, 5 integers would only fit into a block of 32 bytes. You may expect a capacity of 8, and it would be true, except the runtime has to actually store the capacity somewhere, so it consumes some bytes to do that inside the block itself. So a block of 8 ints becomes a block of 7 ints. There is also the issue of needing a sentinel byte between blocks to prevent leaking into the next block. So the last element was wasted anyway before I added the capacity. -Steve
Jan 14 2014