[C++][cppcon 2018][note] “C++17's std - -pmr Comes With a Cost" - David Sankel

What std::pmr trying to solve?

• Allocation is slow
• Fragmentation hurts performance
• pre-C++17 allocator is overly complicated

Speed

• std::pmr::synchronized_pool_resource
  For data frequently accessed at the same time (thread safe)
• std::pmr::unsynchronized_pool_resource
  no thread synchronization cost (not thread safe)
• std::pmr::monotonic_buffer_resource
  high speed, high space (not thread safe)

The memory_resource should have global lifetime.
When passing pointer into function(including constructor), always consider the lifetime of the pointer it points to.


Ok, here's the tricky part.
Consider code below presented by David Sankel:

int main() {
    static Loggingresource memoryResource(
        std::pmr::new_delete_resource()}; // why static? why not local?
    
    std::pmr::set_default_resource(&memoryResource);
    
    std::pmr::vector<int> ints;
    ints.push_back(42);
}

The reason for why making memoryResource global variable? It's due to in different TU(translation unit), functions could have static variables as well, and the init. sequence of this static variable depends on when the function being called. If the static variable of a function from other TU using std::pmr::vector, the destruction sequence of it is later then local variable of main function.

This reminds us the well known article from Alexander Bernauer: RAII vs. exit()

ALWAYS CONSIDER VARIABLE CONSTRUCT/DESTRUCT SEQUENCE

Refer to Linking notes and How main() is executed on Linux

1. starts up program threading
2. call _init()
   __attribute__((constructor))
3. **registers** the _fini() and _rtld_fini(). called after program terminiates.
   __attribute__((destructor))
4. call main()

class Bar2 {
    std::string data{"data"};
};


class Foo2 {
    std::unique_ptr<Bar2, 
         polymorphic_allocator_delete /* our deleter taking memory_resource ptr */> 
             d_bar;
    
    public:
        Foo2() : d_bar(nullptr /* init. with null */, {{std::pmr::get_default_resource()}}) {
            std::pmr:polymorphic_allocator<bar2> alloc{
                std::pmr::get_default_resource()};
            Bar2 *const bar = alloc.allocate(1); // 1 as one Bar2 instance. Not sizeof(Bar2)
            // Be ware here, we should have a try/catch here
            // since Bar2 constructor can throw.
            // and manually call alloc.deallocate 
            // Remember Effective C++ Item 52, placement new
            // and placement delete should go in pairs.
            alloc.construct(bar);
            d_bar.reset(bar);        
        }
};

To the question from audience asking why using polymorphic allocator instead of using placement new?

Because, because...
operator new has scope...
there's deleting destructor...
Allocator gives us a uniform way to grab memory from heap.

Destructor should NOT throw.
It's hard, but take that into consideration, seriously.

Recap:
[C++11] destructor with noexcept
[C++] Exception in detail.


std::pmr::polymorphic_allocator::destroy noexcept(false)
std::pmr::polymorphic_allocator::deallocate noexcept(false)

class polymorphic_allocator_delete{
    public:
        polymorphic_allocator_delete(
            std::pmr::polymorphic_allocator<std::byte> allocator)
            : d_allocator(std::move(allocator) /* actually, a copy, not move */) 
            {}
        template<typename T>
        void operator() (T *ptr) {
            std::pmr::polymorphic_allocator<T>(d_allocator).destroy(ptr);
            std::pmr::polymorphic_allocator<T>(d_allocator).deallocate(ptr, 1);
        }
        
    private:
        std::pmr::polymorphic_allocator<std::byte> d_allocator;
};

std::pmr::polymorphic_allocator::polymorphic_allocator has no move constructor

With this implementation, the size being allocated is larger with extra 4 words due to unique_ptr has captured a pointer to deleter.

Try using type instead of using ptr to function, which prior has only 1 byte.
Ref: [C++14] unique_ptr with type erasure as shared_ptr

Most of the STL container has a std::pmr namespace version.

Do NOT change the default global memory_resource during the run time. It's dangerous.

We can use std::byte or void for polymorphic_allocator:

std::pmr::polymorphic_allocator<std::byte>
std::pmr::polymorphic_allocator<void>

By using void is align with 'new' operator, which returns void*

Strong exception safety

IFF value type's move constructor is noexcept, otherwise container will go back using value type's copy constructor instead. When? For std::vector, while it need's more slots.

class Foo {
    std::pmr::polymorphic_allocator<std::byte> d_allocator;
    std::unique_ptr<Bar2, 
        polymorphic_allocator_delete
           /* our deleter taking memory_resource ptr */> 
               d_bar;
    
    public:
        // Let's focus on move constructor

        // passing in new allocator
        Foo(Foo&& rhs, std::pmr::polymorphic_allocator<std::byte> allocator);
        Foo(Foo&& rhs) noexcept : 
        d_allocator(other.d_allocator /* no need move because it's copy ptr anyway */), 
        d_bar(nullptr, {d_allocator /* Make sure d_allocator is declared before d_bar*/})
        {
            d_bar.reset(other.d_bar.release());
        }
};

So, can we get rid of d_allocator? Since it's just a placeholder for global memory_resource.

Yes, we can.

How? The data member has the memory_resource which shares it. We can grab it from there.

Sum up

Excerpt from the talk, allocator awareness best practices:

• Fix allocator at construction
• Allocator argument to constructor, copy constructor, move constructor, and move copy constructor passing allocator to data members(containers)
• move constructor takes extra new allocator argument
• A member type of std::pmr::polymorphic_allocator<std::byte>
• get_allocator call from data member to get the shared memory_resource
• Always use global storage for the default allocator(arguable..)
• Set the default allocator only in main(reasoning due to static namespace variable in different TU init. sequence isn't guaranteed.

It's becoming complicated...
The doctrine to keep in mind is that, fix allocator in the code path. If it's not, there is a problem.

I do not think this pmr adding is mature enough for all data type instances since it's not being supported by all std:: datatypes and corner cases needs to be concerned. Yet, it could; however, being used in scope to tackle with certain problems.
i.e memory pool

Reference:
How tcmalloc Works
jemalloc

[C++][Cppcon 2018][note] An Allocator is a Handle to a Heap - Arthur O'Dwyer

Headers:
<memory_resource>
<memory>


Tools:
std::allocator_traits , use as  std::allocator_traits<allocator<T>>
std::is_empty , test if a type can be used with [no_unique_address] (reference: http://vsdmars.blogspot.com/2018/05/caccu2018-tricks-library-implementation.html)


Concept (must read):
C++ concepts: Allocator

excerpt from Howard Hinnant' Allocator Boilerplate

• Allocator must be CopyConstructible and MoveConstructible
  There's no Move Constructor, please refer to:
  std::allocator::allocator
  std::pmr::polymorphic_allocator::polymorphic_allocator
  The concept of Allocator mentioned clearly:
  A a1(std::move(a))
  A a1 = std::move(a)
  A a(std::move(b))
  The value of a is unchanged and a1 == a. (since C++20)
  Allocator must be "Copy-Only" types.
  Why? 
  Consider:
  vector<int, Allocator<int>> v1;
  vector<int, Allocator<int>> v2 = std::move(v1);
  // There's no allocator, it's been moved!
  v1.clear(); v1.push_back(42);
  Refer to: LWG issue 2593
• If propagate_on_container_copy_assignment{} is true, the allocator must be CopyAssignable.
• If propagate_on_container_move_assignment{} is true, the allocator must be MoveAssignable.
• If propagate_on_container_swap{} is true, the allocator must be Swappable.
• If they exist, these operations should not propagate an exception out. However they do not need to be marked with noexcept.
• Recommend mark them with noexcept if the compiler does not implicitly do so, so that traits such as is_nothrow_copy_constructible<allocator<T>> give the right answer.

Refresh:
Effective STL, Item 10, 11

Reference:
http://vsdmars.blogspot.com/2017/10/c-allocator-template-code.html

Back to the main topic:

std::pmr i.e <memory_resource>
std::pmr::polymorphic_allocator (value type)

By skimming through the
polymorphic_allocator constructor signature, there's no move constructor, indicates that, it shares resources.
Unlike stateless allocator, polymorphic_allocator doesn't have 'state', but value, which is the value of pointer point to the shared resource. It has state, but immutable state, which is that the pointer to resource is const.
'allocate'/'deallocate' can be marked as 'const', which the data member pointer point's to the shared resource shouldn't be changed.

That is to say, polymorphic_allocator is a Regular type.

Be ware about who owns the memory resource(std::pmr::memory_resource, NOT a value type)?

We can call std::pmr::get_default_resource to get the underneath memory_resource ptr.

--------------------------------------------------------
For stateless allocator:
An allocator object represents a source of memory.

Now for valued allocator:
An allocator value(aka. ptr to memory_resource) represents a handle to a source of memory.

e.g (hell, simple. Now we can even _not_ consider making UDT destructor virtual, deleting destructor issues etc.)

class My_Resource : public memory_resource{
    // non-const since change states
    void *do_allocate(size_t bytes, size_t align) override {
        return ::operator new(bytes, std::align_val_t(align));
    }
    // non-const since change states    
    void do_deallocate(void *p, size_t bytes, size_t align) override {
        ::operator delete(p, bytes, std::align_val_t(align));
    }
    
    bool do_is_equal(const memory_resource& rhs) const noexcept override {
        return (this == &rhs); // God, no dynamic_cast for '==', never!
    }
};


inline memory_resource *get_my_resource() noexcept {
    static My_Resource instance; // thread safe
    return &instance;
}

std::pmr::polymorphic_allocator internally will store the value of a pointer point to memory_resource, which is a word(64 bits) in 64bit machine, which means there are as much as 2^64 distinct memory_resource can be used.

Why std::pmr::polymorphic_allocator taking memory_resource as pointer instead of reference?
Be careful that if passing a local resource by reference, it dangerous. It's hard to see inside the callee that the reference it's lifetime/ownership. However, if passing as pointer, the engineer should know to be aware that it's lifetime/ownership.


Getting the traditional ::operator new/delete memory_resource:
std::pmr::new_delete_resource

Thus, can we make our own stateless std::pmr::polymorphic_allocator?
Of course! Just by default using std::pmr::new_delete_resource as std::memory_resource.


Excerpt from the talk sub-sum up:

• Allocator types should be copyable, just like pointers.
• Always true but in C++17 it's more obvious.
• Allocator types should be cheaply copyable, like pointers.
• Not necessarily trivially copyable.
• Memory_resource types should generally be immobile(with the same virtual memory address)
• A memory resource might allocate chunks out of a buffer stored inside itself as a data member.

-------
std::pmr::synchronized_pool_resource Alike Herb Sutter's talk in Cpp 2015? A centralized heap memory management.

std::pmr::unsynchronized_pool_resource Unthread safe version of std::pmr::synchronized_pool_resource
-------
Allocators are 'rebindable family' types.

Why? From Effective STL, Item 10, due to associate containers that the type instance stored is not the 'type instance' but internal data structure inside the container.
i.e
Containers take this type inside:
rebind_alloc<T> from std::allocator_traits

std::array does not use allocator, it's allocated on stack.
std::vector is the only sequential container which doesn't use rebind.
---------
Other 'rebindable families' in C++:

• Allocator types
  allocator_traits<Alloc<T>>::rebind_alloc<U> == Alloc<U>
• Pointer types
  pointer_traits<Ptr<T>>:rebind<U> == Ptr<U>
• Smart-pointer types
  decltype(reinterpret_pointer_cast<U>(Sptr<T>{})) == Sptr<U>
• Promise and future types
  decltype(future<T>{}.then([](auto&&... u) -> U {throw;})) == future<U>

----------

Each 'rebindable family' has a prototype:

• Pointer and smart-pointer families have a 'void pointer' type
• Ptr<void>, Sptr<void>
• Allocator families have a 'proto-allocator' type
• Alloc<void>
• Promise and future types have a 'future of void' type
• future<void>

----------
Fancy pointer:

i.e
std::allocator_traits::allocate could return a pointer points to either:

• T*
• s.t fancier, like boost::interprocess::offset_ptr

----------

Reference:
[reddit] Q: How should C++ support persistent memory?
http://vsdmars.blogspot.com/2018/06/cproposalnote-implicit-creation-of.html

[C++] allocator template code

Reference:
https://howardhinnant.github.io/allocator_boilerplate.html
http://en.cppreference.com/w/cpp/container/vector/operator%3D
http://en.cppreference.com/w/cpp/memory/allocator_traits


C++11 and forward:

The commented out code represents functionality that std::allocator_traits<allocator<T>> defaults for us.

Notes:

• is_always_equal is new for C++11 (hopefully that will be C++17).  It is now in C++17.
• The default implementation for max_size() is not incredibly useful.
  Better if:
  

  return std::numeric_limits<size_type>::max() / sizeof(value_type);
  

• Under discussion is the possibility to remove the requirement that you provide operator== and operator!= if is_always_equal{} is true.
• The nested types reference and const_reference are no longer required in C++11 (as they were in C++03).
• The member functions address(reference) and address(const_reference) are no longer required in C++11 (as they were in C++03).
• Allocator must be CopyConstructible and MoveConstructible. If propagate_on_container_copy_assignment{} is true, 
• allocator must be CopyAssignable if propagate_on_container_move_assignment{} is true, allocator must be MoveAssignable. 
• If propagate_on_container_swap{} is true,  allocator must be Swappable. 
• If they exist, these operations should not propagate an exception out. 
• However they do not need to be marked with noexcept.
  Recommend marking them with noexcept if the compiler does not implicitly do so,
  so that traits such as is_nothrow_copy_constructible<allocator<T>> give the right answer.
• If two allocators compare equal, that means that they can deallocate each other's allocated pointers. 
• If two instances of your allocators can't do this, they must not compare equal to each other, else run time errors will result.
• However copies, even converting copies, are required to compare equal.

template <class T>
class allocator
{
public:
    using value_type    = T;

//     using pointer       = value_type*;
//     using const_pointer = typename std::pointer_traits<pointer>::template
//                                                     rebind<value_type const>;
//     using void_pointer       = typename std::pointer_traits<pointer>::template
//                                                           rebind<void>;
//     using const_void_pointer = typename std::pointer_traits<pointer>::template
//                                                           rebind<const void>;

//     using difference_type = typename std::pointer_traits<pointer>::difference_type;
//     using size_type       = std::make_unsigned_t<difference_type>;

//     template <class U> struct rebind {typedef allocator<U> other;};

    allocator() noexcept {}  // not required, unless used
    template <class U> allocator(allocator<U> const&) noexcept {}

    value_type*  // Use pointer if pointer is not a value_type*
    allocate(std::size_t n)
    {
        return static_cast<value_type*>(::operator new (n*sizeof(value_type)));
    }

    void
    deallocate(value_type* p, std::size_t) noexcept  // Use pointer if pointer is not a value_type*
    {
        ::operator delete(p);
    }

//     value_type*
//     allocate(std::size_t n, const_void_pointer)
//     {
//         return allocate(n);
//     }

//     template <class U, class ...Args>
//     void
//     construct(U* p, Args&& ...args)
//     {
//         ::new(p) U(std::forward<Args>(args)...);
//     }

//     template <class U>
//     void
//     destroy(U* p) noexcept
//     {
//         p->~U();
//     }

//     std::size_t
//     max_size() const noexcept
//     {
//         return std::numeric_limits<size_type>::max();
//     }

//     allocator
//     select_on_container_copy_construction() const
//     {
//         return *this;
//     }

//     using propagate_on_container_copy_assignment = std::false_type;
//     using propagate_on_container_move_assignment = std::false_type;
//     using propagate_on_container_swap            = std::false_type;
//     using is_always_equal                        = std::is_empty<allocator>;
};

template <class T, class U>
bool
operator==(allocator<T> const&, allocator<U> const&) noexcept
{
    return true;
}

template <class T, class U>
bool
operator!=(allocator<T> const& x, allocator<U> const& y) noexcept
{
    return !(x == y);
}