www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Array append proposal

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Oct 10 2008
next sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
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.
Oct 10 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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.

-Steve
Oct 10 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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
Oct 10 2008
next sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 12:28:02 -0400,
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.


Yes, I've got it from your first explanation, thank you.  :)
Oct 10 2008
prev sibling parent reply KennyTM~ <kennytm gmail.com> writes:
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?

--

BTW, I think this design is like a hack. What about a separate bool field?
Oct 10 2008
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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
Oct 10 2008
parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Fri, 10 Oct 2008 21:04:54 +0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 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.


And this is something that needs to be fixed.
Oct 10 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Denis Koroskin" <2korden gmail.com> wrote in message 
news:op.uitjgjkdo7cclz proton.creatstudio.intranet...

 On Fri, 10 Oct 2008 21:04:54 +0400, Steven Schveighoffer 
 <schveiguy yahoo.com> wrote:


 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.


 And this is something that needs to be fixed.


Allocating in-place to the end of an array is an optimization.  It's not 
guaranteed to happen, and you can't write code that depends on it.

However, having a slice overwrite other parts of an array because it appends 
in place (the current D behavior) is a serious design flaw.  That is what 
I'm trying to fix.

-Steve
Oct 10 2008
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"KennyTM~" wrote

 BTW, I think this design is like a hack. What about a separate bool field?


A separate bool field adds 4 (or 8 for 64-bit) extra bytes to the array 
struct size.  I'm trying to avoid counter-arguments like this by leaving the 
array struct size the same.

-Steve
Oct 10 2008
prev sibling parent reply Sergey Gromov <snake.scaly gmail.com> writes:
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.


 * 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.


 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.
Oct 10 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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
Oct 10 2008
parent reply Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 13:30:14 -0400,
Steven Schveighoffer wrote:

 "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.


Garbage collector granularity is 16 so there is no overhead in your 
example.  A 9-byte array would take 2 memory blocks instead of one 
though.


 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.


I think it's a coincidence mostly related to thread-safety of the GC.  
Also, atomic swaps are not free, and additional ifs are not free.  I'm 
not sure this feature is required.
Oct 10 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Sergey Gromov" wrote

 Fri, 10 Oct 2008 13:30:14 -0400,
 Steven Schveighoffer wrote:

 "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.


 Garbage collector granularity is 16 so there is no overhead in your
 example.  A 9-byte array would take 2 memory blocks instead of one
 though.


Very true, I didn't think of it that way.  So probably having the capacity 
stored in the heap is acceptable.  It just changes the threshold at which 
the overhead is expensive, 8 bytes instead of 16 (don't forget the sentinel 
byte).


 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.


 I think it's a coincidence mostly related to thread-safety of the GC.
 Also, atomic swaps are not free, and additional ifs are not free.  I'm
 not sure this feature is required.


I don't know much about the penalty from atomic swap.  I'm not a CPU guru, 
so I assumed they were quick, at least quick enough to be acceptable.  If 
they aren't, then the proposal is still valid without the thread handling. 
You just need to implement threading constructs around arrays, similar to 
today.

BTW, you still need to do an if to check if the length is equal, even if you 
don't do the compare and swap.

-Steve
Oct 10 2008