[cppcon 2018] An allocator is a handle to a heap - Lessons learned from std::pmr - Arthur O'Dwyer

This talk given by Arthur is a recap from his talk on C++Now 2018.

Define object:

• An object has an address.
  (Unlike pure value, which will be replaced with the value by compiler in the assembly)
• Has state.
• Address, pointer, name, unique identifier, handle --- all synonymous for the purpose, they are value type.

Sequence Container:

• Act as object.
• Act as value.

Define allocator:

For std::vector,

• Where does the memory for v[i] come from?
• From A::allocate(n)
• What is the thing represented by points to the value?
• From A::pointer type.
• Container holds an instance of the allocator type A within itself.
• What can we put inside the allocator instance?
• :-)

C++17, let's use std::pmr::polymorphic_allocator !

• Has a pointer to a std::pmr::memory_resource
• All the shared state goes into the memory_resource

Usage:

// std
namespace pmr {
    template <class T>
    using vector = std::vector<T, std::pmr::polymorphic_allocator<T>>;
}
std::vector<int, std::pmr::polymorphic_allocator<int>> vec(allocator_instance);

Allocator is:
A value represents a handle to a source of memory with some other orthogonal pieces.
Thus:

• Allocator types should be copyable, just like pointers.
• Allocator types should be cheaply copyable, like pointers.
  They need not be trivially copyable
• Memory-resource types should generally be immobile.

Recap, Allocators must be 'copy-only' types

i.e If std::move(allocator) should do a copy instead of move, exactly act like std::move(pointer) should remains the same pointer.

Reference:

http://vsdmars.blogspot.com/2018/06/ccppcon-2018note-allocator-is-handle-to.html

Refers to: LWG issue 2593 https://timsong-cpp.github.io/lwg-issues/2593

An allocator should satisfy allocator completeness requirements.

Allocator completeness requirements

An allocator type X for type T additionally satisfies the allocator completeness requirements if both of the following are true regardless of whether T is a complete type:

• X is a complete type
• Except for value_type, all the member types of std::allocator_traits<X> are complete types.

Take aways:

• Use std::allocator_traits::construct to create instance.
• iterator_facade
  We implement a complete set of primitive functions (and data members); then inherit from iterator_facade to provide the standard zoo of operators.
• iterator_adaptor
  We override some but not all the primitive functions; then inherit from iterator_adaptor<Base> to provide the missing parts.
• Executor coming in C++23
  P0443: std::executor

[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

[cppcon2016][c++] Leak-Freedom in C++ - note

CppCon 2016 - Herb Sutter “Leak-Freedom in C++... By Default.”-
https://goo.gl/2TNgQI
--

• Ensure an object will be destroyed once it is no longer needed.
• Correct by construction!

template<typename T>
using Pimpl = const unique_ptr<T>;
unique_ptr<data[]> ptr;

Double linked list:

• a unique_ptr to the next
• a raw ptr to the back

shared_ptr with alias constructor:

• https://www.justsoftwaresolutions.co.uk/cplusplus/shared-ptr-secret-constructor.html
• Used for passing the leaf of a tree d.s around while keeping the root/tree alive.

• Do not violate layering.
• Don't create ownership cycles across modules by owning 'upward' (violates layering)
• Use weak_ptr to break cycles.

How?

• Don't pass an owner down to 'unknow code' that might store it.
  e.g storing a shared_ptr
• Simple.
  Use weak_ptr inside the call back callable object which point
  to outside resource.

ownership types:

• 1 object, 1 owner:
  unique_ptr
• 1 object , n owners:
  shared_ptr
• N objects, 1 or n owners:
  deffered_ptr

Reachability is a property of the while group.
Not detectable from 1 object, or subgroup.

Idea:
heap for deffered_ptr is isolated.
Each module could have one isolated heap.
github.com/hsutter/gcpp