Array append proposal

[Steven Schveighoffer]

"Sergey Gromov" wrote
> Fri, 10 Oct 2008 11:11:40 -0400,
> Steven Schveighoffer wrote:
>> 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.
>
> Then you'd better keep the memory block size there, too.  It's the
> memory block size check which kills performance right now.

I'm not trying to fix performance.  I'm trying to fix slice corruption 
issues (without adversely affecting performance).

However, it would be nice to have this stored also.  It's definitely 
possible, but the overhead might be a bit too much.  Imagine allocating a 4 
byte array, and having 8 bytes of overhead.

If it turns out everything needs to be 8-byte aligned (not sure, I'm not 
really an expert about that kind of stuff), then yes, putting in a capacity 
field would be a great addition.

>
>> * 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.
>
> I don't think a primitive type should concern itself with thread safety.
> So you can always keep simple length in the array's global length field.

Except that this works today without threading issues.  Two threads can 
append to the same array, one appending in place and the other allocating a 
new array (because the size got too big).  However, there are cases where it 
doesn't work.

But this is a simple mechanism to prevent threading issues (which should be 
very fast), shouldn't it be employed?

If the capacity field is included, then the thread contention mechanism 
might start to be relevant, but as of today, the penalty for checking 
capacity will far outweigh the penalty for doing this simple check.

It could also be ignored if the shared/unshared paradigm is implemented and 
the array is denoted as unshared.

>> 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;
>
> Imagine the code
>
> int[] arr = new int[10000];
> int[] arr2 = arr;
> arr.length = 0;
> for(int i = 0; i < 10000; i++)
>   arr[i] = i;
>
> arr2 is overwritten and you can do nothing about that.  Downsize should
> convert arr into an ordinary slice.  So this sort of optimization stops
> working.  Well, it's a hack anyway but then you need a legitimate way of
> pre-allocating an array leaving its length zero.

I think you made an error there.  arr.length is 0, so you can't set any 
elements in it (as you are in the loop).  I think you may have meant:

for(int i = 0; i < 10000; i++)
   arr ~= i;

But my point was, what is the difference between doing:

arr = arr[0..0];
arr.length = 0;

The second is generally the method used to do pre-allocate hack, so it could 
have a special connotation that it does change the heap-stored length.

My preference is for it NOT to do that.  But others may say this is an 
essential feature that they need.  In that case, I'd make arr.length = 0 set 
the heap length and arr = arr[0..0] leave the heap length alone.

If I had it my way, arr.length = 0 would NOT set the heap-stored length, and 
those users that complain would be politely directed to an array builder 
struct in the lib ;)

-Steve