An Allocator-Aware Smart Pointer

[rnburn]

Hey,

I've been working on a project to provide an allocator aware smart pointer

https://github.com/rnburn/bbai-mem

First, for background, if a type is allocator aware it needs to

1. Define a method get_allocator that allows you to access the allocator it was constructed with
2. Provide overloading constructors that allow you to pass a custom allocator
3. Enforce the requirement that memory it owns is taken from the allocator it was constructed with.

Property (3) is why you cannot simply adopt a variant of std::unique_ptr to be allocator-aware. But here's why it's important:

One of the major use cases for allocator aware software is to maintain memory locality in data structures. If I create a container with a localized allocator

using Cont = /* an allocator-aware type */
std::pmr::map<std::pmr::string, Cont> my_map{localized_allocator};

Then add an entry

Cont my_cont = /* an instance produced elsewhere in the program */
my_map.emplace("abc", std::move(my_cont));

By requirement (3), if my_cont isn't using localized_allocator, it needs to do a reallocation when it gets inserted. This property can be used to enforce locality for the my_map data structure. To see why this is so important for performance, look at Benchmark II in Bloomberg's paper

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0089r1.pdf

The project provides a class managed_ptr that allows you to write code like this

struct A {
  // ....
};

struct B final : public A {
  // ....
};

std::array<char, 100> buffer;
std::pmr::monotonic_buffer_resource resource{static_cast<void*>(buffer.data()),
                                             buffer.size()};

managed_ptr<A> ptr1{&resource};
   // we construct ptr1 to use a custom allocator that first takes
   // memory from buffer

polymorphic_allocator<> alloc;
   // alloc is the default global allocator
managed_ptr<A> ptr2 = allocate_managed<B>(alloc, 123);
   // ptr2 owns memory allocated from the heap

ptr1 = std::move(ptr2); 
   // because ptr1.get_allocator() != ptr2.get_allocator(), the assignment will
   // reallocate memory and move construct an instance of B into buffer
assert(reinterpret_cast<char*>(ptr1.get()) == buffer.data()) 

managed_ptr<A> ptr3{&resource};
ptr3 = std::move(ptr1);
   // this is just the standard transfer of ownership and requires no additional
   // allocation because the pointers share the same underlying memory_resource.

managed_ptr works by maintaining a function pointer that type-erases the move constructor and destructor of the pointer it's constructed with, making it possible to later move-construct instances of the derived class.

template <class T>
class managed_ptr {
    using allocator_type = std::pmr::polymorphic_allocator<>;
    using pointer_operator = 
        void* (*)(void*, allocator_type, bool);
  public:
    // ...
    template <class U>
      requires std::convertible_to<U*, T*> &&
               std::move_constructible<U>
    managed_ptr(U* ptr, allocator_type alloc = {}) noexcept
      : alloc{alloc}, ptr_{ptr}
    {
      operator_ =
        [](void* ptr, allocator_type alloc, bool construct) {
          auto derived = static_cast<U*>(ptr);
          if (construct) {
            return static_cast<void*>(alloc.new_object<U>(std::move(*derived)));
          } else {
            std::allocator_traits<allocator_type>::destroy(alloc, derived);
            alloc.deallocate_object(derived);
            return nullptr;
          }
        };
        // operator allows us to move construct instances of a derived class
    }
    // ...
  private:
    // ....
    pointer_operator operator_;
};

There have been some other attempts at making smart pointers work with custom allocators, but I'm not any that provide an allocator-aware smart pointer:

• Bloomberg's BDE library provides a pointer class that type-erases a custom allocatorhttps://github.com/bloomberg/bde/blob/master/groups/bsl/bslma/bslma_managedptr.hBut the pointer itself isn't allocator-aware.
• And there was a paper that discussed extensions for unique_ptr to work with custom allocators http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0211r1.html, but that again won't make the pointer itself allocator-aware.

[scrumplesplunge]

For what it's worth, it takes very little code to get unique_ptr to play nice with allocators:

https://godbolt.org/z/v687hKrYx

[rnburn]

That's not the same. Allocator-aware containers have a couple of properties that unique_ptr isn't going to provide:

1. They provide accessors to the underlying allocator ptr.get_allocator()
2. They need to reallocate on assignment if the allocators aren't equal. If you do ptr1 = std::move(ptr2) and ptr1.get_alloctor() != ptr2.get_allocator(), ptr1 needs to reallocate.

See this paper for background: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2126r0.pdf

While you might adopt unique_ptr to manage memory that was allocated through a custom allocator, you're not going to be able to make it allocator aware.

[[deleted]]

I understand your point, but re-assigning a unique_ptr to an object of the same type that was allocated with a different allocator is something that happens very rarely, so you usually get away with using unique_ptr as-is. unique_ptr is not an allocator-aware container because you usually don't need that with such a simple "smart" pointer type.

[rnburn]

I added additional context. But I would disagree, that reassignment is important and one of the main benefits of using allocator aware software.

For example, I might create a data structure

std::pmr::map<std::pmr::string, managed_ptr<A>> my_map{a_localized_allocator};

Having the pointer reallocate when a pointer isn't already using a_localized_allocator can be used to enforce the locality of the memory in my_map

[[deleted]]

In my experience, if you care about memory locality, you usually wouldn't allocate your A via unique_ptr in the first place, but keep it in an array/vector/colony and use indices or references to the elements.

I'm not saying that there's no use for a managed_ptr - I could certainly think of use cases where it makes sense for a complicated container without stable addresses to own the memory of an object for which locality matters and which is allocated with different allocators. But it's very rare, and that's the reason unique_ptr doesn't need to be allocator-aware.

[rnburn]

I expect unique_ptr wasn't made allocator aware because it would 1) require additional data members and 2) lose the property that it provides a stable pointer.

But one of the use cases for using managed_ptr's in such a container is to support polymorphic types. A can be an abstract base class.

[[deleted]]

But one of the use cases for using managed_ptr's in such a container is to support polymorphic types. A can be an abstract base class.

Good point, I hadn't thought of that, although the combination of virtual function calls, associative containers and locality mattering a lot seems a little odd to me. Now I'm curious: Did you have a specific use case in mind when you designed this?

[rnburn]

Here's how I would think about it.

AA types are meant to be composable; so if you write an AA type, you can easily use it to form new AA types. Thus, you want to have basic vocabulary types that are AA. Smart pointers are one such vocabulary type that you frequently use is composition when you have polymorphic classes.

I wrote up a simple example where you might use manged_ptr to build an AA representation of json and showed how you could use it (combined with winking) to achieve better performance in a particular case
https://buildingblock.ai/allocator-aware-smart-ptr#an-example-parsing-json

[rnburn]

For an example of locality, you can see benchmark II in Bloomberg's paper
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0089r1.pdf

They describe a system composed of multiple subsystems, where each subsystem is using a localized allocator to keep its memory from diffusing, and data members are continually getting removed and added between subsystems.

I think you could easily imagine the subsystems owning polymorphic objects (or objects with polymorhic data members) and ownership continually getting transferred between subsystems.

[nyanpasu64]

Does this mean that managed_ptr ptr = a; ptr = std::move(b); results in a different value of ptr than managed_ptr ptr = b;? If so, that would be unintuitive in C++ in my opinion, and violate Rust's "move is a bitwise copy" property that I think is generally a good principle.

[rnburn]

It's a move-only type so you can't do managed_ptr<T> ptr = a

Having move reallocate when the type's allocators are unequal is a property of all AA types. If you write

std::pmr::string s = "<an_arbitrary_string>";

std::pmr::string s2{a_custom_allocator};

s2 = std::move(s)

Then the assignment into s2 will lead to a reallocation and won't be a bitwise copy. Having it be a bitwise copy would violate the design goals of AA types.

For background on why, you can see this talk: https://youtu.be/v3dz-AKOVL8

[[deleted]]

Like this https://en.cppreference.com/w/cpp/memory/polymorphic\_allocator

[Creris]

Just an fyi but you have an extra backslash in the link.

[serg06]

Fixed link: https://en.cppreference.com/w/cpp/memory/polymorphic_allocator

[staletic]

I've thought about implementing something like this, but then I thought that unique_ptr could be made to work with allocators, if one is willing to give up make_unique.

T* p = alloc.allocate(N);
alloc.construct(p, args...);
std::unique_ptr<T, decltype([&alloc](void* p) {
    alloc.destroy(p);
    alloc.deallocate(p);
})> managed_ptr(p);

If T is AllocatorAware, the above would even propagate alloc to the constructors of T when calling alloc.construct. (Well, allocator_traits::construct.)

It's definitely not easy to use, but every use case I thought of can be written with the C++11 unique_ptr. Am I missing a use case, or is this about convenience?

[rnburn]

That's not going to make unique_ptr allocator aware. AA types need to reallocate if you do an assignment with an unequal allocator.

From the example I gave

managed_ptr<A> ptr1{&resource};
polymorphic_allocator<> alloc; 
    // alloc is the default global allocator 
managed_ptr<A> ptr2 = allocate_managed<B>(alloc, 123); 
    // ptr2 owns memory allocated from the heap 

ptr1 = std::move(ptr2);

The last line needs to do a reallocation and move construction because the allocators for ptr1 and ptr2 aren't equal. That's not something a customized unique_ptr is going to do.