[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <dvwr6xi2d73jnzrrpp4ketrmie6kubs4oxogc5q6ncfbcc65v6@rt22v7lrpauw>
Date: Mon, 3 Nov 2025 00:58:39 +0100
From: Alejandro Colomar <alx@...nel.org>
To: Thiago Macieira <thiago@...ieira.org>
Cc: Florian Weimer <fw@...eb.enyo.de>, libc-alpha@...rceware.org,
musl@...ts.openwall.com, Arthur O'Dwyer <arthur.j.odwyer@...il.com>,
Jonathan Wakely <jwakely@...hat.com>
Subject: Re: realloci(): A realloc() variant that works in-place
Hi Thiago,
On Sun, Nov 02, 2025 at 03:10:45PM -0800, Thiago Macieira wrote:
> On Sunday, 2 November 2025 05:31:59 Pacific Standard Time Alejandro Colomar
> wrote:
> > The purpose of realloci() is being extremely cheap. So, why would one
> > ask for extra size?
>
> Speculative growth. When the container is being added to, it knows it needs at
> least one more element, but it can't predict the future to know how many more.
> So it asks "pretty please" for a few more.
realloci() would still give a few more. The difference is that if you
speculate from std::vector, you're speculating, while realloci() gives
you more without speculation.
> However, we can keep the code and simply ask for a bit more in the same
> parameter, instead of two. With the interface as you've described, it's not a
> failure to be unable to return as many bytes as requested.
Actually, read until the end of this mail. I'm starting to understand
the extra parameter.
> > If the caller needs 37 kiB, it should ask for exactly 37 kiB. The
> > allocator would likely give 40 kiB.
>
> With ptmalloc inside glibc, the rounding up is likely only to be to the
> smallest allocation unit, that is, 16 bytes.
Hmmm, it seems you're right; when dealing with tens of kiB, granularity
is at 16 B.
alx@...uan:~/tmp$ cat r.c
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
int
main(void)
{
void *p;
p = NULL;
p = realloc(p, 37 * 1024);
printf("37 * 1024: %zu\n", malloc_usable_size(p));
for (ptrdiff_t i = -10; i < 10; i++) {
p = realloc(p, 41 * 1024 + i);
printf("41 * 1024 + %td: %zu\n", i, malloc_usable_size(p));
}
}
alx@...uan:~/tmp$ gcc -Wall -Wextra r.c
alx@...uan:~/tmp$ ./a.out
37 * 1024: 37896
41 * 1024 + -10: 41976
41 * 1024 + -9: 41976
41 * 1024 + -8: 41976
41 * 1024 + -7: 41992
41 * 1024 + -6: 41992
41 * 1024 + -5: 41992
41 * 1024 + -4: 41992
41 * 1024 + -3: 41992
41 * 1024 + -2: 41992
41 * 1024 + -1: 41992
41 * 1024 + 0: 41992
41 * 1024 + 1: 41992
41 * 1024 + 2: 41992
41 * 1024 + 3: 41992
41 * 1024 + 4: 41992
41 * 1024 + 5: 41992
41 * 1024 + 6: 41992
41 * 1024 + 7: 41992
41 * 1024 + 8: 41992
41 * 1024 + 9: 42008
> So it's unlikely to return 40 kB,
> aside of some special circumstances (e.g., an mmap()-backed allocation).
Now that I checked, it seems musl's mmap(2) threshold is in the hundreds
of kiB. I was expecting it to be lower.
> However, the upper layer can ask for 40 kB if it speculates it might need that
> and only be given 37.5 kB.
How about two consecutive calls?
size = realloci(p, speculative_size);
if (size != -1)
goto done;
size = realloci(p, needed_size);
if (size != -1)
goto done;
do_actual_realloc();
> > Then the caller will ask again when
> > it needs 41 kiB. Why would the caller want to allocate something like
> > 64 kiB (just as an example), but then be happy with 37? This call is
> > much cheaper than an actual move with realloc(3) or malloc(3)+free(3).
>
> So it is. I don't know yet whether it's going to be too expensive to call it
> for every single element growth - I expect it will be. So container is
> probably going to request more than a single element when growing, but
> probably not double as it does today.
Hmmm, could be.
> All this will need fine-tuning once implementations exist.
>
> > So, why not require the caller to not ask too much? We could go back to
> > reporting an error if there's not enough memory.
> >
> > Of course, it would still guarantee no errors when shrinking, but
> > I think we could error out when growing.
>
> I'd prefer no errors either way. If there isn't memory to grow the underlying
> space (a brk() system call returns ENOMEM), then realloci() returns as much as
> it could get but not more.
The problem is that this is asking the implementation to speculate.
Consider the case that a realloci() implementation knows that the
requested size fails. Let's put some arbitrary numbers:
old_size = 10000;
requested_size = 30000;
It knows the block can grow to somewhere between 10000 (which it
currently has) and 30000 (the system reported ENOMEM), but now it has
the task of allocating as much as it can get. Should it do a binary
search of the size? Try 20000, then if it fails try 15000, etc.?
That's speculation, and it would make this function too slow.
I suspect that's why xallocx() has the extra parameter. It removes the
need for speculating. However, what that parameter is doing is hiding
two calls in a single one. Maybe it would be better to ask the user to
do the two calls explicitly.
Let's compare:
speculative_size = needed_size + EXTRA_GROWTH;
size = realloci(p, speculative_size);
if (size != -1)
goto done;
size = realloci(p, needed_size);
if (size != -1)
goto done;
do_actual_realloc();
with:
size = realloci2(p, needed_size, EXTRA_GROWTH);
if (size != -1)
goto done;
do_actual_realloc();
Hmmmmm, if people are going to do this every time they need realloci(),
then I guess it makes sense to have it more compact. Also, you can have
a constant EXTRA_GROWTH that you use all the time, so you don't need to
calculate the speculative size unnecessarily (wasting another line of
code, plus one for the declaration of the variable).
I'm starting to like the interface of xallocx(). Prior art often has
reasons. :)
Have a lovely night!
Alex
--
<https://www.alejandro-colomar.es>
Use port 80 (that is, <...:80/>).
Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
