Pop quiz [memory usage]

[Fawzi Mohamed]

On 2009-06-07 11:33:06 +0200, Fawzi Mohamed <fmohamed at 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