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

[Sean Kelly]

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.

> One of the issues with the current GC is that getting a size of a memory block 
> that consists of hundreds or thousands of pages is that it is a linear search 
> for the end of the block.   This is mitigated by the LRU cache, but once you 
> exceed the number of cache, performance should probably fall off a cliff 
> (however, it doesn't for reasons I don't understand).  But when I extend a 
> block, it must do this same linear search to find the page size before doing an 
> extend.  I'm trying to do that linear search as little as possible.  All this 
> could probably be mitigated if the allocated length was somehow cached per 
> allocated page.

Yeah, dealing with big blocks kind of stinks.  Maybe something like this would indeed be worth trying.

> I didn't write newCapacity, so I'm not sure about the theory behind it, or what 
> desirable properties for appending are.  But it does make sense to me that if 
> you are continuously appending, you want to preallocate more than "just enough 
> to append the new data".  How much more, I have no clue :)  I assumed the 
> formula in newCapacity was written by someone who knows what they are doing.  
> Well, except for using the element size in the percentage formula.

Yeah, me too :-)