On 2009-06-07 11:33:06 +0200, Fawzi Mohamed <fmoha...@mac.com> said:
Ehm some small corrections to the constants, so that their meaning is
better connected to what one expects in both versions
actually the original function proposed by Dave Fladebo is not so bad,
it calculates the average storage requirement per bit
(total_size/num_bits) and tries to allocate that space more.
The advantage is that it stays exponential like which means ~O(log(n))
(maybe log(n)*log(log(n))) reallocations needed when continuously
adding, but tries to waste less and less space the larger the array is.
I did propose two "reasonable" possibilities, that I give again here in
a cleaner way
{{{
const int b=2;
const a =100L;
version(A){
const minBits=11; // normally page size is at least 2K
} else {
const minBits=1;
}
static int log2plusB(size_t c)
{
int i=b;
while(c >>= 1){
++i;
}
return i;
}
variant(A)
long mult = 100 + a*(minBits+b) / log2plusB(newcap);
} else {
long mult = 100 + a*(minBits+b) / log2plusB(newlength);
}
// testing shows 1.02 for large arrays is about the point
of diminishing return
if (mult < 102)
mult = 102;
newext = cast(size_t)((newcap * mult) / 100);
newext += size-(newext % size);
}}}
version A uses the total memory, the other the number of elements.
Increasing a makes the the amount of reserved space larger (it is the
maximum amount of extra reserved space in %).
The value of minBits I choose is different from one version to the
other because min(log2(newcap))=~12, min(log2(newlength))=1
Increasing b makes the decrease flatter, and goes closer to treating
all sizes with the same extra space. For small b the decrease for
larger arrays is faster.
In general I think that the functional form is sound, and it is
superior to either fixed "double the size" or "add a constant size".
This approach should be used also in other places that need to
periodically reallocate.
The question is which values of a and b are optimal, and if it is
better to use the total size or the number of elements.
Now if someone would to some meaningful benchmarks (on real
applications), then I would be very happy, otherwise I would just take
one of my guesses...
Fawzi
