Path: ...!3.eu.feeder.erje.net!feeder.erje.net!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:18:40 +0100
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <875xu8vsen.fsf@bsb.me.uk>
References: <v4ojs8$gvji$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Mon, 17 Jun 2024 11:18:41 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f69b21fe46179def9aae9c77317b77e3";
	logging-data="615472"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/V+zg+EbDwO71Sgv3/5Ez+X7ySuhqKr58="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:Pjjz8v/eeUGJR2brdGh36h8PPoE=
	sha1:f8Xh0Ql2zjrM3ay/qgmv4Y/P/jw=
X-BSB-Auth: 1.007fdcf76d0baf05e01e.20240617101840BST.875xu8vsen.fsf@bsb.me.uk
Bytes: 2323

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.

-- 
Ben.