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

[Andrei Alexandrescu]

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.


Andrei