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

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

On 17/06/2024 10:18, Ben Bacarisse wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
 

In a recent thread realloc() was a substantial part of the discussion.
"Occasionally" the increased data storage will be relocated along
with the previously stored data. On huge data sets that might be a
performance factor. Is there any experience or are there any concrete
factors about the conditions when this relocation happens? - I could
imagine that it's no issue as long as you're in some kB buffer range,
but if, say, we're using realloc() to substantially increase buffers
often it might be an issue to consider. It would be good to get some
feeling about that internal.

There is obviously a cost, but there is (usually) no alternative if
contiguous storage is required.  In practice, the cost is usually
moderate and can be very effectively managed by using an exponential
allocation scheme: at every reallocation multiply the storage space by
some factor greater than 1 (I often use 3/2, but doubling is often used
as well).  This results in O(log(N)) rather than O(N) allocations as in
your code that added a constant to the size.  Of course, some storage is
wasted (that /might/ be retrieved by a final realloc down to the final
size) but that's rarely significant.
 

So can we work it out?

What is "it"?

Let's assume for the moment that the allocations have a semi-normal
distribution,

What allocations?  The allocations I talked about don't have that
distribution.

with negative values disallowed. Now ignoring the first few
values, if we have allocated, say, 1K, we ought to be able to predict the
value by integrating the distribution from 1k to infinity and taking the
mean.

I have no idea what you are talking about.  What "value" are you looking
to calculate?

--
Ben.