On Mon, Apr 25, 2022 at 7:23 PM Breno Guimarães via Std-Proposals <
std-proposals_at_[hidden]> wrote:

>
> Creating unrelated objects contiguously in memory is a very useful
> technique to implement some data structures and avoid needless allocations.
>
> Take std::make_shared<T>(...) for example. It will execute one single
> allocation [...]
>
the purpose of this email is to float the idea on a standard library
> facility to make this an every(other)day technique rather than a trick.
> For the sake of introducing some concreteness, let's start with this naive
> API:
>
> template<class... Ts>
> std::tuple<std::pair<Ts*, Ts*>...>
> make_contiguous_objects(initializer_for<Ts>...);
>
> This function would return a tuple or begin/end pointers for each T in Ts
> that were created on the heap, given some information on how to initialize
> them.
>
> So, for std::make_shared<T[]>(size_t n), a big part of the job could be
> achieved through:
>
> auto objs = std::make_contiguous_objects<ControlBlock, T>(/*number of
> control blocks=*/ 1, /*number of Ts=*/ n);
>

I think this is widely *almost* applicable, but I'm not sure if the devil
might be in the details. It looks analogous to `std::uninitialized_copy`,
for example — `uninitialized_copy` is *almost* what you need to implement
std::vector's copy constructor, except that it's missing allocator
support, so nobody can use it for that purpose.

make_shared<T> wants make_contiguous_objects<CtrlBlock, T>(1, 1).
make_shared<T[]> wants make_contiguous_objects<CtrlBlock, T>(1, n).
But in both cases, we need to preserve the ability to std::destroy *only*
the T (when the last shared_ptr goes away but weak_ptrs are still being
held), and then destroy the CtrlBlock and deallocate the whole shebang
later (when the last weak_ptr goes away).

plf::hive<T>'s "allocate new capacity" function wants
make_contiguous_objects<T, skipfield_type>(n, n).
But it doesn't want to *construct* the T objects yet; it just wants to
allocate the memory for them. They'll be constructed (and destroyed) later,
as the container's size() fluctuates.

In both plf::hive and std::allocate_shared, we have the same problem that
we need to do uses-allocator construction for the objects. That's easily
addressed (I think) by just doubling the size of your API:
   template<class... Ts, class... Counts> std::tuple<Ts*...>
make_contiguous_objects(Counts...);
   template<class... Ts, class Allocator, class... Counts> auto
allocate_contiguous_objects(const Allocator& a, Counts...);

This actually points out a second problem: Your API works great if the
caller wants to default-construct their objects. But what if they want to
construct them in some other way, like what if `T` is not
default-constructible? Mind you, this is a lower-priority problem than
"what if the caller doesn't want to construct them at all."

I think it won't be hard for you to implement your "first draft" API... but
then you need to spend some time looking for use-cases (preferably in the
STL or Boost or other well-known libraries that can be assumed not to be
doing anything stupid by accident) and actually find out whether your API
helps them. I suspect it will be *almost* good enough, but not quite, for
one reason or another, in basically every real-world case.

my $.02,
Arthur