[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20251103002708.GV1827@brightrain.aerifal.cx>
Date: Sun, 2 Nov 2025 19:27:08 -0500
From: Rich Felker <dalias@...c.org>
To: Arthur O'Dwyer <arthur.j.odwyer@...il.com>
Cc: Thiago Macieira <thiago@...ieira.org>,
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: Re: realloci(): A realloc() variant that works in-place
On Sun, Nov 02, 2025 at 06:55:53PM -0500, Arthur O'Dwyer wrote:
> 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.
At this point this sounds completely orthogonal to the realloci
discussion. Asymptotically, in-place realloc is *never* going to
succeed in doubling the size of an object. The only times it will
succeed are in non-size-segregating allocators when the old object is
either at the "top of the heap" (only one such object exists in the
process at any given time) or where you just happened to free an
object that just happened to be positioned right above it. This
happens so rarely that there is utterly no point in optimizing for it.
It the program doesn't work or performs badly when this optimization
can't succeed (which is most of the time) then the program needs to be
fixed not to do whatever it was trying to do.
Rich
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.
