Enhanced array appending

[Steven Schveighoffer]

grauzone Wrote:

> Steven Schveighoffer wrote:
> > The problem is that adding a capacity field only works if the object is a reference type.  A value type will make either choose to make copies of the capacity field, resulting in the same stomping problem (and maybe worse), or will zero out one of the copy's capacity field, resulting in an artificial limitation for appending.  The only true way to make this work right is to have a capacity field shared among all the aliases to the same data, and the most logical place for that is in the allocated block.
> 
> I see... Go makes slices value types (which references the array data), 
> but I'm not sure how or if they handle this situation.
> 
> Then, why use a cache to find the pointer to the capacity field inside 
> the array memory block? You could just store a pointer to the capacity 
> field in the slice.
> 
> Something like this, I guess:
> 
> struct slice {
>      void* ptr;
>      size_t length;
>      array_info* array;
> }
>
> [snip]
> 
> Would this work?

Yes, but the problem I see with it is you are passing around that array_info pointer with the slice for *all* slices, not just ones you intend to use appending on.  There is plenty of code that uses arrays and slices without ever doing appending, so that extra pointer is wasted space, and also increases the cost of passing slices by value.

Your idea is essentially the idea behind my patch, except you can get the array info without having an additional pointer.  The cost of lookup for the block info is mitigated by the cache, making lookups cost very little.

The patch is a compromise between performance for appending and performance for everything else.  I think there will still be a need in specialized code for a fatter array type that allows appending without complicated GC lookups, but the patch provides safe appending for a reasonable performance hit without affecting other aspects of array usage.  As with all compromises, there are always different ways of doing things, so time will tell if this patch is the best method.

-Steve