On Mon, Apr 25, 2022 at 7:23 PM Breno Guimarães via Std-Proposals <std-proposals@lists.isocpp.org> 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