[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CADvuK0Kk0StmD+Lv25S62gWrr=R01BfGcccomE0mpQ9nqqa7Lw@mail.gmail.com>
Date: Sun, 2 Nov 2025 18:55:53 -0500
From: "Arthur O'Dwyer" <arthur.j.odwyer@...il.com>
To: Thiago Macieira <thiago@...ieira.org>
Cc: Alejandro Colomar <alx@...nel.org>, Florian Weimer <fw@...eb.enyo.de>, libc-alpha@...rceware.org,
musl@...ts.openwall.com, Jonathan Wakely <jwakely@...hat.com>
Subject: Re: realloci(): A realloc() variant that works in-place
On Sun, Nov 2, 2025 at 6:10 PM Thiago Macieira <thiago@...ieira.org> 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.
>
I'll just chime in to mention that I recently had cause to look into what
various STL implementations (libc++, libstdc++, Microsoft) do when you
write something like:
std::vector<char> v;
v.resize(VERY_LARGE_NUMBER);
v.push_back(1);
Naturally every STL implementation will ask the vector's
std::allocator<int> for basically 2*VERY_LARGE_NUMBER bytes of memory at
this point.
If that much memory is available, then we're on the happy path and
everything's great. If less memory is available, the allocator throws a
std::bad_alloc exception.
Now for the interesting part: `vector::push_back` really only *needs* a
*single* additional byte — VERY_LARGE_NUMBER+1 bytes — in order to do its
job. Does any STL implementation actually catch the std::bad_alloc
exception and retry with a smaller allocation, in order to diligently do
the job it was asked to do?
Answer: *No.* In practice, *no* STL implementation retries allocations
inside `vector::push_back`. In practice, anytime the allocator throws, that
exception propagates out and we're done. So that means that std::vector has
basically "one chance" — it gets to make of the allocator a *single*
request, and so (in theory) it must choose that request wisely. (In
practice, running out of memory is rare and nobody cares if you run out a
little earlier than you would've otherwise.)
If there *were* a way to ask a C++ allocator for "2*VERY_LARGE_NUMBER
bytes, but, if you can't do that, I'll settle for as few as
VERY_LARGE_NUMBER+1 bytes," then presumably `vector::push_back` is exactly
the place we'd see that API getting used.
But this whole (bunch of) thread(s) started because of Thiago's throwaway
comment along the lines of "C++ doesn't care about realloc because realloc
has a bad API," and I think this thread (these threads) are just driving
that point home. If I wanted to reach a good allocator API, "I wouldn't
start from here." I don't think one can design a good allocator API by
making a ton of tiny patches on top of `malloc` and `realloc`. You have to
design the API *first*, and then show how to implement `malloc` and
`realloc` in terms of it.
(Also, C++ couldn't use it without also redesigning `std::allocator`, which
is almost just a thin wrapper around `malloc` and `free`. `std::allocator`
doesn't even have a counterpart to `realloc` at the moment.)
–Arthur
Content of type "text/html" skipped
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.
