Array append proposal

[Steven Schveighoffer]

"KennyTM~" wrote
> Steven Schveighoffer wrote:
>> "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
>>
>>
>>
>
> That means the highest bit of .length will be set (not visible to coder of 
> course) if the array is of the form [x..$] right?

No, only if x is 0.  Because if x is nonzero, then the memory before the 
first element is not the heap-stored length.  This is one drawback I should 
have mentioned, you can't successfully append to a slice that is at the end 
of a memory block.  But you can't do that today, either.

-Steve