[D-runtime] Fw: [phobos] newCapacity function in array appending

[Steve Schveighoffer]

----- Original Message ----
> From: Sean Kelly <sean at invisibleduck.org>
> To: D's runtime library developers list <d-runtime at puremagic.com>
> Sent: Wed, July 14, 2010 4:54:35 PM
> Subject: Re: [D-runtime] Fw: [phobos] newCapacity function in array appending
> 
> On Jul 14, 2010, at 6:19 AM, Steve Schveighoffer wrote:
> > 
> > I  assume the newCapacity function is used to avoid constantly looking for 
>new 
>
> > memory to allocate.  The theory being if you are appending, you  don't want 
>to 
>
> > just allocate exactly what you need, you want to  preallocate a little more.
> 
> What gets me is that the GC already does this,  since it uses blocks that are 
>powers of two in size, and then page-sized chunks  (which may again have extra 
>space allocated at the end based on some qualities  of the alloc request).  I 
>can see newCapacity allocating 4x extra on an int  append than a byte append, 
>but the other logic has always seemed a bit  overthought to me.  But then I 
>never sat down and tested it so I figured  maybe it's actually good in 
>practice.  I didn't notice the screwed up  growth factor based on element size 
>though.

Any appends of data < page do not use newCapacity, it's only for page size and 
above.  And then, it was only when allocating a brand new block.  From the bug 
report you can see it grew linearly by a page each time, until it needed to 
reallocate, and then the growth was ridiculous (200% growth!).

My new checked in code sort of hovers around 40% growth for larger blocks, even 
when extending in place.  I think the formula may need to be tweaked some more, 
but it's definitely much better than the linear growth pattern.  In my test 
program, it shaves off about 1/10th of a second.  The down side of course is 
when you are appending to a large array, it's going to add 40% back on itself 
which will be significant, even if you are just adding one element.  I think for 
very large arrays, we probably want to make the growth approach some low 
percentage (like 1 or 2%).  I also am wondering whether we should consider the 
number of elements being added, i.e. if you are only adding 1 or 2 elements, 
don't grow as much.

-Steve