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

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.

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.

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.

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

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.

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

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

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
}

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