Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben@bsb.me.uk>
Newsgroups: comp.lang.c
Subject: Re: realloc() - frequency, conditions, or experiences about relocation?
Date: Mon, 17 Jun 2024 10:55:33 +0100
Organization: A noiseless patient Spider
Lines: 44
Message-ID: <87zfrjvqp6.fsf@bsb.me.uk>
References: <v4ojs8$gvji$1@dont-email.me> <875xu8vsen.fsf@bsb.me.uk>
	<v4ovqf$j5hq$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Mon, 17 Jun 2024 11:55:34 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f69b21fe46179def9aae9c77317b77e3";
	logging-data="615472"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX199v8u6tLRfSX+cYrx+9x9xbaFUdoCmeCI="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:StE9LcOr9N8aN8/cCOP2wtfcoh8=
	sha1:Oll7KiAojbwOqTdghjGzVCJD4AM=
X-BSB-Auth: 1.d5809cbd62f99a5f327a.20240617105533BST.87zfrjvqp6.fsf@bsb.me.uk
Bytes: 3039

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.