Array append proposal

[Steven Schveighoffer]

"Steven Schveighoffer" wrote
> "Sergey Gromov" wrote
>> Fri, 10 Oct 2008 11:11:40 -0400,
>> Steven Schveighoffer wrote:
>>> First, store the allocated length of the array on the heap along with 
>>> the
>>> array data.  On a 32-bit system, the size will always be 4 bytes, but 
>>> there
>>> can be padding bytes added to keep the alignment for the first element 
>>> in
>>> the array correct.  The maximum padding, I am not sure about.  I 
>>> remember
>>> people saying that for certain operations, 16 byte alignment is 
>>> required?
>>> Or is it just 8?  So for instance an array of doubles, there would be an
>>> 8-byte field storing the length in the first 4 bytes, and padding in the
>>> second 4 bytes.
>>>
>>> Perhaps someone with more knowledge of alignment requirements can 
>>> comment.
>>> I'd also appreciate some insight on how this would look on a 64 bit 
>>> system.
>>>
>>> The final detail is how to tell whether the element before an array is 
>>> the
>>> length or not.  I propose to use the most significant bit in the array
>>> length field.  This prevents having arrays of > 2GB, but that's probably
>>> impossible anyways ;)
>>>
>>> If this bit is set, then the array can be appended to in place if its 
>>> length
>>> equals the length stored in the heap (and of course, the memory block
>>> contains enough space).  If not, then a new array is allocated, and the 
>>> data
>>> copied, the length stored in the heap is left alone.
>>
>> How do you implement a slice?  It points in the middle of another array,
>> data around that point is arbitrary.  There is no way you can check if
>> you are at the beginning of an array or not.
>
> If the first element of the slice is not the first element of the 
> allocated array, then it does not have its 'at the beginning' bit set in 
> its local length.

An example:

int[] array = new int[10];

array's length field is set to 0x8000_000a -> most significant bit set means 
it can possibly be appended to.

int[] slice = array[0..$];

slice's length field is set to 0x8000_000a -> most significant bit set means 
it can possibly be appended to.

int[] slice2 = array[1..5];

slice2's length field is set to 0x0000_0004 -> most significant bit unset. 
Will always allocate a new array on an append.

-Steve