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 ^^.

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.

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

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.

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--;
}

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

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

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();
}

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
}

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..$][]