The great slice debate -- should slices be separated from arrays?

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> On Tue, 24 Nov 2009 14:07:27 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
> 
>> Steven Schveighoffer wrote:
>>> On Tue, 24 Nov 2009 11:07:43 -0500, Andrei Alexandrescu 
>>> <SeeWebsiteForEmail at erdani.org> wrote:
>>>
>>>> Steven Schveighoffer wrote:
>>>>> In many other posts, people have been festering over dropping 
>>>>> T[new] and not having a reference array type.  The argument is (and 
>>>>> forgive me if this is a strawman, someone from the other side can 
>>>>> post if I'm incorrect): If we make arrays a separate type from 
>>>>> slices, and only allow appending on arrays, then we solve the 
>>>>> stomping problem and the hard-to-determine reallocating problem.  
>>>>> For those who are unfamiliar with these problems, I'll try to 
>>>>> outline them at the bottom of the post.
>>>>>  I contend that even if we make arrays a separate type, even if 
>>>>> arrays are made a true reference type, slices will still suffer 
>>>>> from the same hard-to-determine reallocation problem *unless* we 
>>>>> make slices fatter.
>>>>>  My proof is as simple as an example.  Assume 'Array' is the new 
>>>>> type for an array:
>>>>>  auto a = new Array!(int)(15); // allocate an array of 15 integers, 
>>>>> all 0
>>>>> auto s = a[0..5];
>>>>> a ~= [1,2,3,4,5];
>>>>> a[0] = 1.
>>>>>  Now, what does s[0] equal?
>>>>
>>>> Array may include a field
>>>>
>>>>     bool sliceExtracted;
>>>>
>>>> that is set to true whenever you take a slice from the array and set 
>>>> to false whenever the array's data is reallocated. The array's 
>>>> documentation could mention that ~= is amortized constant if there 
>>>> are no intervening slicing operations.
>>>  We weren't talking about performance, but I think I know what you 
>>> are saying: To solve the hard-to-determine reallocation problem, you 
>>> propose that any array which has had a slice taken from it, will 
>>> reallocate on append even if it could grow into the block?  That 
>>> seems like a rather blunt solution...
>>>  if(arr[0.."hello".length] == "hello")
>>>    arr ~= "xyz"; // oops, reallocate because we took a slice earlier.
>>>  Wouldn't this make slicing combined with appending unusable for 
>>> performance reasons?  Then the only time you want to use slices is if 
>>> you are done appending to the array, and then even today's 
>>> implementation wouldn't cause the hard-to-determine problem for code 
>>> written that way.
>>>  Maybe I misunderstood you, let me know.
>>
>> You understood me correctly. I think it's reasonable if Array defines 
>> ~= in relation to using other primitives. It's a common approach, for 
>> example, in C++ and Java to define an operation (such as bumping or 
>> dereferencing an iterator) in terms of no intervening conflicting 
>> operations against the same object.
> 
> Why do we need this scheme then?  If it only makes sense to use slicing 
> when you are done appending, then why not use that model with today's 
> rules?  Why make code that uses slices before you are finished appending 
> perform poorly?  Why make code that uses temporary slices (like I showed 
> in my example) perform poorly?

Because we don't know how to make things perfect in all circumstances.

Andrei