[D-runtime] Extending pages in GC

[Steve Schveighoffer]

Currently, in the GC, there is this routine:

extend(void * p, size_t minsize, size_t maxsize)

The parameters are the pointer to extend, the minimum number of bytes to add to 
the block, and the maximum number of bytes to add.

This only works if the block is page size or greater.  It essentially queries 
the pool for pages that are "committed" and "free" that are after the currently 
allocated block, and adds them to the block.

If the minimum number of pages required to satisfy extend are not free and 
comitted, then it uses a Pool method:

extendPages(uint n)

Which will "commit" up to n pages if it has that many uncomitted pages, or it 
will return an error.

The issue is, what argument do you pass to extendPages?  The only sane value to 
pass is minsize, because if you pass maxsize and it fails, then you didn't get 
anything.

But why shouldn't extendPages commit as many pages as possible?  If that was the 
case, then you could get closer to your desired maxsize.

Here is the syndrome I'm trying to fix.  When using appending on an array to add 
one element at a time, the array append code will use a function newCapacity to 
add a certain percentage of memory to a block (the size varies, from something 
like 300% of the current size for small arrays to 20% for very large arrays).  
If it can use extend, it will.  But it will only use newCapacity if completely 
reallocating.  I recently change it to try extend with the minimum size needed 
to append as minsize, and the result of newCapacity as the maxsize.

What I found was happening is, even though the maxsize requested was hundreds, 
even thousands, of pages, I would get a single page, then 15 pages, then a 
single page, then 15 pages, etc.  So clearly the pages are available, but the 
routine doesn't add all it can.  What happens is the "commit" size must be a 
multiple of 16 pages.  So when extend cannot get any free pages, it calls 
extendPages to get enough pages to cover minsize (usually 1).  extendPages must 
commit a multiple of 16 pages, so it commits 16.  extend gets its one page, and 
returns.  There are now 15 free pages, so the next append adds 15 more.  But 
this defeats the algorithm which tries to pre-allocate a proportional amount of 
data while appending.

What I want to have is a function that tries its best to get to maxsize, using 
any means possible, including comitting pages.  I plan to add such 
functionality.  What I'm not sure of is, should I modify the existing functions, 
or add new ones?

My proposed changes would be to add a new extendPagesUpTo(n) (name to be worked 
on) which may extend *up to* n pages, and then modify extend to use this 
function instead.  I don't want to change extendPages(n) because some code may 
rely on the current behavior of returning an error if it cannot extend to *at 
least* n pages.  However, I think extend can be changed because it already is 
expected to return some value between minsize and maxsize or 0 if it couldn't do 
it.

What do you think?

-Steve