Array append proposal

[Steven Schveighoffer]

I had this idea just now while reading some of the discussion about how new 
arrays should be classes and slices should be unappendable.

I know the T[new] syntax has been passed around to indicate a newly 
allocated array of T (which has different semantics than normal arrays). 
I'm not sure the exact details, so forgive me if this was the plan, but I 
can't find the details of it anywhere.  All I remember is that the 
appendability of the array depended on the type system to tell you 'yes, 
this is a T[new] array so it can be appended to'.

But I thought, what if you copied the T[new] array to another T[new] array? 
Then you append to one, then append to the other, oops!

So I thought how will one know that the other has increased the allocated 
length?

One way, of course, is to use a class as the array type, but there are 
several downsides to that.  First, you lose value semantics.  i.e. one can 
copy the array reference, but then your array can grow if another reference 
is used to append.

So here is another proposal... It's kinda kooky, so bear with me ;)

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.

Several notes on this scheme:

* No 'special' type is required.  This means, you can append to a slice just 
fine, and it magically becomes a fully-allocated array, without accidentally 
overwriting other data, and without requiring you to store it as a different 
type.
* No extra data per array struct is required
* If the array type is large, and the number of elements small, the overhead 
is going to be large
* Getting the length of the struct requires an 'and' op in order to remove 
the extraneous bit.
* Operations which affect the length/ptr would have to worry about the extra 
bit also.
* This scheme is immune to copying an array reference and appending to both. 
The second will not match it's length with the heap-stored length, and so 
the array will not overwrite the first.
* There are some threading issues to look at, but I am nowhere near as 
versed in this as some of you guys.  I'd guess you can do something similar 
to Bartosz' thin locks?  Except you would never expand the lock.  The first 
time you lose contention, you assume you can't append in place, and allocate 
a new memory space.  The only drawback is if the array which grabbed the 
lock decides it will allocate a new array as well, and the second attempt to 
append could have done it in place, you lose some performance there.  But 
that's probably a rare corner case. The bit that is used for the 'is array 
head' can be used for lock contention.  So something like this is stored in 
the heap:

bit [31]: set if nobody is trying to expand array, unset if it is currently 
being expanded.
bit [0:30]: the stored length

So in order to expand an array, you compare and swap with your struct-local 
length+atBeginning, swapping it for 0.
*  success: check GC if block can accomodate new data;  if so, store the new 
length back into the heap-stored length, with the MSB set;  if not, allocate 
a new array, copying the data from the original.
*  failure: allocate a new array, copying the data from the original.

One final caveat.  Currently there exists code like this for building a 
large array:

int[] arr = new int[10000];
arr.length = 0;
for(int i = 0; i < 10000; i++)
   arr ~= i;

In the new scheme, should the code:

arr.length = 0;

cause the array to try and shrink the heap-stored length to 0?  My 
preference is no, as this is going to be much less inefficient than 
something like:

int[] arr = new int[10000];
for(int i = 0; i < 10000; i++)
   arr[i] = i;

So the original code should be discouraged.  I think most folks agree that 
an array builder class/struct (which has a stored/settable capacity field) 
would be much more efficient than using the GC to check each time whether 
data can be appended.

Thoughts?

-Steve