Re: realloc() - frequency, conditions, or experiences about relocation?

Anton Shepelev wrote:

[cross-posted to: ci.stat.math]
 
Malcolm McLean:
 

We have a continuously growing buffer, and we want the
best strategy for reallocations as the stream of
characters comes at us. So, given we now how many
characters have arrived, can we predict how many will
arrive,

 
Do you mean in the next bunch, or in total (till the end of
the buffer's lifetime)?
 

and therefore ask for the best amount when we reallocate,
so that we neither make too many reallocation (reallocate
on every byte received) or ask for too much (demand
SIZE_MAX memory when the first byte is received).?
 
Your strategy for avoiding these extremes is exponential
growth. You allocate a small amount for the first few
bytes. Then you use exponential growth, with a factor of
ether 2 or 1.5.

 
This strategy ensures a constant ratio between the amount of
reallocated data to the length of the buffer by making
reallocations less frequent as the buffer grows.
 

And so we integrate the distribution between the point we
are at and infinity. Then we tkae the mean. And that gives
us a best estimate of how many bytes are to come, and
therefore how much to grow the buffer by.

 
You have an apriori distribution of the buffer size (can be
tracked on-the-fly, if unknown beforehand) and a partially
filled buffer.  The task is to calculate the a-posteriori
distribution of that buffer's final size, and then to
allocate the predicted value based on a good percentile.
 
How about using a percentile instead of the mean, e.g. if
the current size corresponds to percentile p, you allocate a
capacity corresponding to percentile 1-(1-p)/k , where k>1
denotes the balance between space and time efficency.  For
example, if the 60th percentile of the buffer is required
and k=2, you allocate a capacity sufficient to hold
100-(100-60)/2=80% of buffers.

Based on essentially no background to this question, not much can be
said. However, if one starts from the suggestion above to use the mean
of some distribution (or later some percentile), one notes that the
"mean" is just the minimum of a quadratic cast function ,,, so an
improvement would be to base the choice on some more realistic cost
function, chosen for the actual application. Given that the scenario
apparently involves a sequence of such decisions, the obvious extension
of the cost-based approach would be to employ some form of dynamic
programming. Of course, this might not be appealing, in which case one
might choose the theoretically-simple approach of tuning a policy based
on good stchastic simulations of the situation.