If T[new] is the container for T[], then what is the container for T[U]?

[Robert Jacques]

On Sat, 25 Apr 2009 11:57:25 -0400, dsimcha <dsimcha at yahoo.com> wrote:
> == Quote from Robert Jacques (sandford at jhu.edu)'s article
>> On Sat, 25 Apr 2009 09:16:39 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>> > Stewart Gordon wrote:
>> >> Andrei Alexandrescu wrote:
>> >>> It looks we can't make it with only T[]. We need a genuine container
>> >>> type, and T[new] was suggested.
>> >> <snip>
>> >>  What do you mean by a "genuine container type"?
>> >
>> > One with capacity and probably value semantics.
>> >
>> > Andrei
>> First, capacity is only static (i.e. can be included in the array as you
>> suggest) for free-list based allocation. Which is _only_ used by malloc
>> and mark-sweep GCs. And I'm really hoping Leandro gives us something
>> better than mark-sweep.
>
> But in a pointer bumping GC, the right way to do dynamic arrays would be  
> to
> allocate some extra space for the array beyond the length requested, to  
> allow it
> to be appended to without being reallocated.  In this case, the extra  
> space is
> being allocated under the hood by the array functions, not the garbage  
> collector,
> but it's still there and you still need a capacity field to track it  
> without
> expensive GC queries.

1) There are multiple types of pointer bumping GCs and checking/exending  
an array can be pretty darn cheap. (You only have to find the memory page)
2) Pointer bumping is only half a GC, generally the other half is going to  
move/compact the array, at which point the capacity *should* be changed.
3) Over-allocating all arrays is a wonderful waste of memory and  
performance (re chache lines, etc). A cleaner answer is an array builder  
class, which only pays for this overhead when it's actually needed.