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
parent reply "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
parent reply "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
parent reply "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
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 reply "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
next 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 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
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 reply "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
next sibling 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 "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 reply "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: 


David
Oct 17 2013
parent reply "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: 


 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
parent reply "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:

 
 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
parent reply "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
next sibling parent reply "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
next sibling parent reply "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
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 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 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 parent reply "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
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 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 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 reply "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
parent reply =?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
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 =


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.


(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 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
next sibling 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 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 reply "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
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 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 "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 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