# Allocators in C++
---
### Outline
* new/delete operator, operator new/delete, placement new
* [Reference](https://www.cnblogs.com/luxiaoxun/archive/2012/08/10/2631812.html)
* std::allocator
* Introduce the std::allocator, allocator_trait
* How to implement your own allocator
* How the container to consider modern allocator
----
### Outline
* std::pmr
- nested container, implicit scoped allocate
- vector<map<int,string>>
- polymorphic_allocator, memory_resources, pmr::container
- how to use pmr in c++17
----
### new/delete operator
* Global new/delete what we know
1. Call ==operator new/delete== to allocate/deallocate the memory
2. Call ==constructor/destructor== at the specific memory location
* The behavior is always same and cannot be overloaded
----
### operator new/delete
* Allocate ==size== bytes memory
* It's available to overload
```cpp!
struct Test {
void* operator new(size_t size) {
auto ptr = ::operator new(size); // call global operator new
std::cout<<"Operator new "<<size<<"bytes"<<std::endl;
return ptr;
}
void operator delete(void* ptr) {
std::cout<<"Operator delete at "<<ptr<<std::endl;
::operator delete(ptr); // call global operator delete
}
};
```
----
### Full Test Struct
``` cpp!
#include <iostream>
using namespace std;
struct Test {
int a, b, c;
Test() { cout << "constructor of Test" << endl; }
~Test() { cout << "destructor of Test" << endl; }
void* operator new(size_t size) {
auto ptr = ::operator new(size); // call global operator new
std::cout << "Operator new " << size << " bytes at " << ptr << std::endl;
return ptr;
}
void operator delete(void* ptr) {
std::cout << "Operator delete at " << ptr << std::endl;
::operator delete(ptr); // call global operator delete
}
};
int main() {
Test* t = new Test();
delete t;
return 0;
}
/* Output:
Operator new 12 bytes at 0x7beeb0
constructor of Test
destructor of Test
Operator delete at 0x7beeb0
* /
```
----
### Operator new with more parameter
``` cpp
#include <iostream>
using namespace std;
struct Test {
// ... other implementation
void* operator new(size_t size, int s) {
auto ptr = ::operator new(size);
std::cout << "Operator new " << size << " bytes at " << ptr <<" with int "<<s<< std::endl;
return ptr;
}
void* operator new(size_t size, const char* str) {
auto ptr = ::operator new(size);
std::cout << "Operator new " << size << " bytes at " << ptr <<" with string "<<str<< std::endl;
return ptr;
}
};
int main() {
Test* t = new("Hello") Test;
delete t;
t = new(42) Test;
delete t;
return 0;
}
/* Output:
Operator new 12 bytes at 0x2211eb0 with string Hello
constructor of Test
destructor of Test
Operator delete at 0x2211eb0
Operator new 12 bytes at 0x2211eb0 with int 42
constructor of Test
destructor of Test
Operator delete at 0x2211eb0
* /
```
----
### Placement new
* A global version of overload operator new.
* Return the pointer and don't care the ==size== parameter
* Call global placement new if the operator new is already overload
* [stackoverflow](https://stackoverflow.com/questions/32999722/placement-new-with-overloaded-ordinary-new-operator)
----
``` cpp
// pseudo implementation
// void *operator new( size_t, void * p ) { return p; }
int main() {
Test* t = new Test();
t->~Test(); // call the destructor
std::cout<<"\n";
t = ::new (t) Test; // call global placement new
delete t;
return 0;
}
/* Output
Operator new 12 bytes at 0x21bdeb0
constructor of Test
destructor of Test
constructor of Test
destructor of Test
Operator delete at 0x21bdeb0
* /
```
----
### Why placement new
* Reuse the allocated memory
1. Use the stack for locality
``` cpp
int main()
{
std::array<std::byte, 1024> buffer;
std::byte* buf = buffer.data();
Test *px = ::new(buf) Test;
px->a = 10;
px->~X();
return 0;
}
```
2. Called by allocator::constructor
---
# Allocator
* [CppCon 2017: Bob Steagall “How to Write a Custom Allocator”](https://www.youtube.com/watch?v=kSWfushlvB8)
* Introduce the allocator in ==C++03==
* Allocator_traits in modern c++
* Write a custom allocator
* Allocator-Awared Container's View
----
* What is allocator
1. The basic purpose of an allocator is to provide a source of memory for a given type, and a place to return that memory to once it is no longer needed.
* Bjarne Stroustrup
2. A service that grants exclusive use of a region of memory to a client.
* Alisdair Meredith
----
* Why Custom Allocator
* Higher performance
* stack-based allocation
* Per-container private allocation
* Per-thread allocation
* Pooled/slab allocation
* Arena allocation
* Debug/test
* Relocatable data
* Shared memory
* Self-contained memory
----
### C++03 allocator
```cpp!
template<class T> struct allocator {
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T const* const_pointer;
typedef T& reference;
typedef T const& const_reference;
typedef T value_type;
template<class U> struct rebind {typedef allocator<U> other;}
pointer allocate(size_type n, allocator<void>::const_pointer hint=0);
void deallocate(pointer p, size_type n);
void construct(pointer p, T const& val);
void destroy(pointer p);
};
template<class T, class U> bool operator==(allocator<T>const &, allocator<U>const &);
template<class T, class U> bool operator!=(allocator<T>const &, allocator<U>const &);
```
----
### allocate/deallocate
```cpp!
template<class T> inline T* allocator<T>::allocate(size_t n) {
// operator new, only new no construct
return static_cast<T*>(::operator new(n * sizeof(T)));
}
template<class T> inline void allocator<T>::deallocate(T* p, size_t) {
// operator delete, only delete no destruct
::operator delete(p);
}
```
----
### constrct/destroy
```cpp!
template<class T> inline void allocator<T>::construct(pointer p, T const& val) {
// placement new
::new(static_cast<void*>(p)) T(val);
}
template<class T> inline void allocator<T>::destroy(pointer p) {
(static_cast<T*>(p))->~T();
}
```
----
### operator ==
* **a1**, **a2** is allocator, ==(a1 == a2) == true== means that the memory allocated from **a1** can be deallocated by **a2**.
```cpp!
template<class T, class U>
inline bool operator==(allocator<T>const &, allocator<U>const &) {
return true;
}
template<class T, class U>
inline bool operator!=(allocator<T>const &, allocator<U>const &) {
return false;
}
```
----
### allocator::rebind
* provide the interface for the container, like std::list
```cpp!
template<class U> struct rebind {typedef allocator<U> other;}
template<class T, class Alloc = allocator<T>>
class list {
typedef typename Alloc::template rebind<list_node<T>>::other node_allocator;
typedef typename node_allocator::pointer node_pointer;
}
template<class T, class Alloc> typename list<T,Alloc>::node_pointer
list::<T, Alloc>::alloc_node(T const& t) {
node_allocator na(this->m_alloc);
node_pointer np = na.allocate(1u);
na.construct(np, t);
return np;
}
```
----
### C++03 allocators - implication
* pointer type always T*
* no support for synthetic pointers / alternate addressing models
* ==std::unique_ptr==
* Implementations assumed that instance are always equal and interchangeable
* standard containers did not support stateful allocators
----
### C++03 allocators - implication
* many intersting problems could not be solved using the standard constainers
* shared memory data structures, self-contained heap
* scoped allocation was tricky
* consider the case of ==map<string, vector<list< string>>>==
* the allocator for the nested conatainer
----
### New requirements to improve allocator support in modern c++
* nullablepointer.requirements
* can compare to ==std::nullptr==
* allocator.requirements
* Define what allocator is and its relationship to allocator traits
* [CppReference: Allocator requirements](https://en.cppreference.com/w/cpp/named_req/Allocator)
----
### New requirements to improve allocator support in modern c++
* pointer.traits
* Describe a uniform interface to pointer-like types used by ==allocator_traits==
* allocator.traits
* Describe uniform interface to allocator types used by containers
----
### New requrements to improve allocator support in modern c++
* allocator.adaptor
* Describes an adaptor template that supports deep propagation of allocators
* container.requirements.general
* Allocator-Awared(AA) Container means that **do something make sense** when use the non-default allocator
* [CppReference: Allocator-Awared Container](https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer)
----
### Review C++03 allocators - implication
* pointer type always ==T*==
* ==pointer_traits==
* Implementations assumed that instance are always equal and interchangeable
* many intersting problems could not be solved using the standard constainers
* Container Support ==stateful allocator== and these two things is possible.
----
### Review C++03 allocators - implication
* scoped allocation was tricky
* consider the case of
* map<string, vector<list< string>>>
* ==allocator.adaptor==
* std::scoped_allocator_adaptor
----
### Modern Allocator Model
```mermaid!
graph LR;
A[SomeAllocator< T,..., MyAlloc< T>>] ---> B[allocator_traits< MyAlloc< T>>];
C[MyAlloc< T>] -- implement --> B;
B -- has --> D[pointer_traits< MyAlloc::pointer>];
```
----
### Lateral propagation
* Is the ==allocator== available to be moved/copied/swapped when the ==container== is moved/copied/swapped.
* copy/move assignment
* swap
* ==allocator_traits== provide information for AA container.
----
### Modern Allocator implementation
* Some of the previous verbiage and burden is removed
* No need to define ==reference== or ==const_reference== typedefs
* No need to implement ==construct()== or ==destroy()==
* Only need to specify properties and services that are not the defaults provided by ==allocator_traits==
----
### Modern Allocator implementation
* However, allocator implementtors must now consider
* How to specify copy/move/swap operations for stateful allocators
* **Pablo Haplpern** said that we should not change the allocator in container after initilization
* How to represent pointers for non-traditional addressing
----
### Allocator Traits Overview
```cpp=
template<class Alloc> struct allocator_traits
{
// basic information
using allocator_type = Alloc;
using value_type = typename Alloc::value_type;
using pointer = INFERRED;
using const_pointer = INFERRED;
using void_pointer = INFERRED;
using difference_type = INFERRED;
using size_type = INFERRED;
// Lateral propagation
using propagation_on_container_copy_assignment = INFERRED; // POCCA
using propagation_on_container_move_assignment = INFERRED; // POCMA
using propagation_on_container_swap = INFERRED; // POCS
using is_always_equal = INFERRED;
// rebind
template <class T> using rebind_alloc = INFERRED;
template <class T> using rebind_traits = allocator_traits<rebind_alloc<T>>;
static pointer allocate(Alloc& a, size_type n);
static void deallocate(Alloc& a, pointer p, size_type n);
template<class T, class... Args>
static void construct(Alloc& a, T* p, Args&&... args);
template<class T>
static void destroy(Alloc& a, T* p);
static size_type max_size(Alloc const& a) noexcept;
// Return the alloc when calling container copy construct
static Alloc select_on_container_copy_construction(Alloc const& a);
}
```
----
### Allocator Traits Overview - pointer
```cpp!
template <class Alloc> struct allocator_traits {
using pointer = typename Alloc::pointer | value_type*;
using pointer = Alloc::const_pointer
| pointer_traits<pointer>::rebind<const value_type>;
using void_pointer = Alloc::void_pointer
| pointer_traits<pointer>::rebind<void>;
using const_void_pointer = Alloc::const_void_pointer
| pointer_traits<pointer>::rebind<const void>;
using difference_type = Alloc::difference_type
| pointer_traits<pointer>::difference_type;
using size_type = Alloc::size_type
| make_unsigned_t<difference_type>;
}
```
----
### Allocator Traits Overview - Lateral propagation
* ==propagate_on_container_move_assignment== is **std::true_type** for **std::allocator**, and others are default.
```cpp!
template<class Alloc> struct allocator_traits
{
using propagate_on_container_copy_assignment
= Alloc::propagate_on_container_copy_assignment
| std::false_type;
using propagate_on_container_move_assignment
= Alloc::propagate_on_container_move_assignment
| std::false_type;
using propagate_on_container_swap
= Alloc::propagate_on_container_swap
| std::false_type;
using is_always_equal = Alloc::is_always_equal
| std::is_empty<Alloc>::type;
}
```
----
### Allocator Traits Overview - Rebind
```cpp!
template<class Alloc> struct allocator_traits {
template<class T> using rebind_alloc = Alloc::rebind<T>::other
| SomeAlloc<T, Args...> // if Alloc is a SomeAlloc
| // ill-formed!
template <class T> using rebind_traits = allocator_traits<rebind_alloc<T>>;
}
```
----
### Allocator Traits Overview - allocate/deallocate
```cpp!
template<class Alloc> struct allocator_traits {
static pointer allocate(Alloc& a, size_type n) {
return a.allocate(n);
}
static pointer allocate(Alloc& a, size_type n, const_void_pointer hint) {
return a.allocate(n, hint)
| a.allocate(n);
}
static void deallocate(Alloc& a, pointer p, size_type n) {
a.deallocate(p, n);
}
};
```
----
### Allocator Traits Overview - construct/destroy
```cpp!
template<class Alloc> struct allocator_traits {
template<class T, class... Args>
static void construct(Alloc& a, T* p, Args&&... args) {
a.construct(p, std::forward<Args>(args)...)
| ::new (static_cast<void*>(p)) T(std::forward<Args>(args)...);
}
template<class T>
static void destroy(Alloc& a, T* p) {
a.destroy(p)
| p->~T();
}
};
```
----
### Allocator Traits Overview - Other
```cpp!
template<class Alloc> struct allocator_traits {
static size_type max_size(Alloc const& a) noexcept {
return a.max_size()
| numeric_limits<size_type>::max()/sizeof(value_type);
}
static Alloc select_on_container_copy_construction(Alloc const& a) {
return a.select_on_container_copy_construction();
| a;
}
};
```
----
### Minimal Allocator Example
* [Code Example](https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DIApACYAQuYukl9ZATwDKjdAGFUtAK4sGIM1ykrgAyeAyYAHI%2BAEaYxBIAzKQADqgKhE4MHt6%2B/oGp6Y4CoeFRLLHxXEl2mA6ZQgRMxATZPn4Btpj2RQwNTQQlkTFxibaNza25HQrjA2FD5SNVAJS2qF7EyOwcJhoAguYJYcjeWADUJglubCwkAJ4A%2BsSYCuubmJfYuwdmRwwnXnOlzcTWITDun2%2Bh2Op0wFyuThmz1YkP2UP2BEwLGSBkxwJOTAUCjOABVUXskV4HGcWGE8CwxA8xLRUKIiMQLgB2Kz7M58s5edJGM4ANzEXkwDwId2ScMuABFSZceXt%2BTS6QzaEzaCy2SQIMt4YqsFQmF5aARld81ZjsbiPlcCUSznJPrSGPTGczWUx2RB3Z6td69cRga6EtgzmgGDNzAA2Q0MVCYVRbZIELlWTny9Gq/kkgBUZ2DvswEHSAC9JRmGMsTNzrWr%2BWaiEX0xyFWcZr68MgHqJY1dC58ICAQKhZWD2WdwgB3CAMM5FyuYVBUCAk5Zbq28pt8mboMdoLyWq7A8xmEuYi5mMznq4Me9uC9nLpYxgEYm%2Bm93s9XCAiqgeDoAWyztk%2BF4mAArG4j63jueZ7s8BAbIuZzgQkKpqvWOa7nygHAWcWBXmWhboaQXZ4FWUqGvWWF7l2BCHig6yns%2BZ63sROo%2Bte36QX%2BbgAUBIFgRB8EwXBv70XuY4TnEvokERb6YhAyR1phjZ8jhULZgh3y2jipb4gYzpkhGZzRKgnjfHJU6KQqCr%2BhqXrcSGwJmZG0axmYcYUQGmrarqCmhkOnxRgI3kJpmyGoWcBDEBKVq6RiWKGXijomcSHkWVZtA2ZOwVnGAYCOf5LlBey7lhV5lo%2BX5zlBq5wVVeZNXxrR3IxcQi6mrQShJbhBxosNexhBmDJhAamaaYxzEirUlUIoI9UegFV4kMCY2QuZj4aSNar8MQEBjWceBGmcGjKqdwJQZdGmWNYeAddJTYMAAdMkgoIA80RMMgADWx3qS92kjaDewcKstCcFBvB%2BBwWikKgnDPg9lhdm8Ww3gkPCkAQmiQ6s/0gAkCRvaTFOU1TvnQxwkhwwTSOcLwCggBoeME6scCwEgaDYnQcTkJQfPJAL8TAFwt6kFgIq9pgABqeCYLOADysrw7jNAWnErMQNEjPRGETR3JwuOG8wxB3Cr0TaAtpu8HzbCCCrDC0CbCO8FgDJGOIHvS3gzx1PNrN%2BymtQntsuNjV0jO0Hg0RgpbHhYIz8X0vbqxUAYwAKIrytq4w9syIIIhiOwUjF/IShqIzuiBAYRgoNY1j6PHrOQKsE49CHAC0B4KqYaMWGYiM1HUzgQK4kx%2BIEITzGUFR6AUGQCNPS9pCvDCDAvSydN09SzGvgRjz0fTNNvwyVGM/RH9f5/z5fEirK8GxbE/%2BgwwzfvIxwZyqAAHHGHucZJBnGAMgZAZxJZvTMGcCAuBCD2V%2BFwZYvB8Yey3KQBAmAmBYHiAaUgxMuBxjeoAhIGgoI4yglBMwnI4xmEkP/D%2BdMv6Ix/izNmHMMGkG5ogEAYdkAnhIELCATQc7KEMF0IQCBUCzg1g7VA/NcSZAkeEWg0jZHw0RiLMWIAJZSx0fQYgERWDbAUUouIKsTwaLkYzARexiA52ZkEVQtQGj4HhrwfgJdRDiArt4quKh1B%2BzrvoQwxhm6WFbtEduBCu6ZF7v3BI8pB5WEsCPFmmNy5jA8aoqRMjbHcF4LOMEyQM7MNhqQLRvAf7YFcYI6cACgEgLARAqBZgYFwNRmkmwZwEHTkOCgtBnMiYgEkAATlIRoBIcYqhQS4FUcZGhJD104PTKpjN2G2E4egrQmDaZmFYTU5xuzCakHmsQdIzhJBAA%3D)
* Bob Steagall suggests us to declare all what we can.
```cpp=
template<class T>
struct minimal_allocator {
using value_type = T;
minimal_allocator() = default;
template<class U>minimal_allocator(minimal_allocator<U> const&) noexcept {}
T* allocate(size_t n){
auto* ptr = static_cast<T*>(::operator new(n * sizeof(T)));
std::cout<<"allocate "<<n<<" elements at "<<(void*)ptr<<"\n";
return ptr;
}
void deallocate(T* p, size_t) {
std::cout<<"deallocate at "<<(void*)p<<"\n";
::operator delete(p);
}
};
```
----
### Container's View - Part 1
```cpp=
template<class T, class Alloc = std::allocator<T>
class some_container {
public:
using value_type = T;
using allocator_type = Alloc;
using alloc_traits = std::allocator_traits<allocator_type>;
using pointer = typename alloc_traits::pointer;
using const_pointer = typename alloc_traits::const_pointer;
using size_type = typename alloc_traits::size_type;
using difference_type = typename alloc_traits::difference_type;
using reference = value_type&;
using const_reference = value_type const&;
}
```
----
### Container's View - Part 2
```cpp=
template<class T, class Alloc = std::allocator<T>
class some_container {
public:
some_container(some_container const& other);
some_container(some_container const& other, allocator_type const& alloc);
some_container(some_container&& other);
some_container(some_container&& other, allocator_type const& alloc);
some_container& operator=(some_container const& other);
some_container& operator=(some_container&& other);
swap(some_container& other);
private:
impl_data m_impl;
allocator_type m_alloc;
}
```
----
### Container's View - Part 3
* traits_type::select_on_container_copy_construction
* propagate_on_container_copy_assignment(POCCA), propagate_on_container_move_assignment(POCMA), propagate_on_container_copy_assignment(POCS)
----
### Container's View - Part 3
* traits_type::select_on_container_copy_construction
* POCCA, POCMA, POCS
```cpp!
template<class T, class Alloc>
some_container<T,Alloc>::some_container(some_container const& other)
: m_impl()
, m_alloc(alloc_traits::select_on_container_copy_construction(other.malloc)) {...}
template<class T, class Alloc> some_container&
some_container<T, Alloc>::operator =(some_container const& other) {
if (&other != this) {
if (alloc_traits::POCCA == std::true_type) {
if (this->m_alloc != other.m_alloc) {
this->clear_and_deallocate_memory();
}
this->m_alloc = other.m_alloc;
}
this->assign_from(other.cbegin(), other.cend);
}
return *this;
}
template<class T, class Alloc> some_container&
some_container<T, Alloc>::operator =(some_container&& other) {
if (alloc_traits::POCMA == std::true_type) {
this->clear_and_deallocate_memory();
this->m_alloc = std::move(rhs.m_alloc);
this->m_impl = std::move(rhs.m_impl);
} else if (alloc_traits::is_always_equal == std:;true_type || this->m_alloc == rhs.m_alloc) {
this->clear_and_deallocate_memory();
this->m_impl = std::move(rhs.m_impl);
} else {
this->assign(std::move_iterator(rhs.begin()), std::move_iterator(lhs.end()))
; }
return *this;
}
template<class T, class Alloc> void
some_container<T,Alloc>::swap(some_container& other) {
if (&other != this) {
if (alloc_traits::POCS == std::true_type) {
std::swap(this->m_impl, other.m_impl);
std::swap(this->m_alloc, other.m_alloc);
} else if (alloc_traits::is_always_equal == std:;true_type || this->m_alloc==rhs.m_alloc) {
std:;swap(this->m_impl, other.m_impl);
} else {
assert(0); // implementation in gcc9.2
// Undefined Behavior
// Because the iterator is invalid after swap the implment but not swap the allocate
}
}
}
```
----
### Now, We know
* C++11 provide the allocate_traits for both allocate developer and container developer
* Implement your own allocator by following [Allocator Requirement](https://en.cppreference.com/w/cpp/named_req/Allocator)
* Implement the Allocator-Awared Container by following the [AA class requiredment](https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer)
* Consider POCCA, POCMA, POCS
---
### Polymorphic Memory Resource(PMR), C++17
* [CppCon 2017: Pablo Halpern “Allocators: The Good Parts”](https://www.youtube.com/watch?v=v3dz-AKOVL8)
* [Getting Allocators out of Our Way - Alisdair Meredith & Pablo Halpern - CppCon 2019](https://www.youtube.com/watch?v=RLezJuqNcEQ)
----
### Polymorphic Memory Resource(PMR), C++17
* PMR introduction
* Use the pmr
* Create a pmr allocator
* Implicit scoped-allocator
* Create an allocator-awared container
* Current standard memory_rousource we can use
----
### PMR introduction
* Almost std container support pmr
* std::pmr:::string
* std::pmr:::vector
* std::pmr:::unordered_map/map
* std::pmr:::unordered_set/set
* std::pmr:::list
```cpp
namespace pmr {
template <typename T>
using vector = std::vector<T, std::polymorphic_allocator<T>;
}
```
* header file ==<memory_resource>==
----
### PMR introduction
* Support the std::allocator_traits
* As the name suggests, there is a polymorphism in the allocator
```cpp=
template <class Tp>
class polymorphic_allocator {
memory_resource* rsrc;
public:
polymorphic_allocator() noexcept: rsrc(get_default_resource()){}
polymorphic_allocator(memory_resource* r): rsrc(r){}
}
```
----
### PMR introduction
* 3 pure virtual function.
```cpp=
template <class Tp>
class memory_resource {
public:
// delegate to the protected virtual function
void* allocate(...);
void deallocate(...);
bool is_equal(const memory_resource& other);
protected:
virtual void* do_allocate(...) = 0;
virtual void do_deallocate(...) = 0;
virtual bool do_is_equal(...) = 0;
}
```
----
### PMR introduction
```mermaid
graph LR
A[std::pmr::vector< int>] --> B[polymorphic_allocator]
B -- implement ---> C[allocator_traits< MyAlloc< T>>]
B -- has --> D[memory_resource]
D -- derived --> E[new_delete_resource]
D -- derived --> F[null_member_resource]
D -- derived --> G[synchronized_pool_resource]
D -- derived --> H[unsynchronized_pool_resource]
D -- derived --> I[monotonic_buffer_resource]
```
----
### PMR introduction
----
### The allocator is part of the type
* This won't work:
```cpp
void func(const std::vector<int>&);
std::vector<int, MyAlloc<int>> v(someAlloc);
func(v); // ERROR: v is a different type
```
* This works, but doesn't scale:
```cpp!
template <class Alloc> void func(const std::vector<int, Alloc>&);
```
* Think about string
```cpp!
template <class Alloc> void func(
const std::basic_string<_CharT, _Traits,
Alloc>&)
```
----
### After using std::pmr::allocator
* This will work
```cpp!
void func(const std::pmr::vector<int>&);
std::pmr::vector<int> v1;
std::pmr::vector<int> v2{&resource2};
func(v1); // OK
func(v2); // OK
```
----
### PMR introduction
----
### create an allocator - dervied from memory resource
```cpp!
class debug_resource : public std::pmr::memory_resource {
protected:
void* do_allocate(std::size_t bytes, std::size_t alignment) override {
void* ptr = std::pmr::new_delete_resource()->allocate(bytes, alignment);
std::cout << "allocate " << bytes << " bytes at " << ptr << "\n";
return ptr;
}
void do_deallocate(void* p, std::size_t bytes,
std::size_t alignment) override {
std::cout << "deallocate at " << p << "\n";
std::pmr::new_delete_resource()->deallocate(p, bytes, alignment);
}
bool do_is_equal(
const std::pmr::memory_resource& other) const noexcept override {
return this == &other;
}
};
```
----
### PMR introduction
----
### PMR introduction - Create a scoped allocator
----
### PMR introduction - Create a scoped allocator
* [Code Example](https://godbolt.org/z/ss6za18Eo)
```cpp!
template <typename T>
using PmrVec = std::pmr::vector<T>;
int main() {
debug_resource dbg_res;
PmrVec<PmrVec<int>> v(&dbg_res);
std::cout << "Outer vector resize\n";
v.resize(5);
// outer vector resize
// allocate 160 bytes at 0x1a3fec0
std::cout << "Inner Vector resize\n";
v[0].resize(5);
// Inner Vector resize
// allocate 20 bytes at 0x1a3ff70
// deallocate at 0x1a3ff70
// deallocate at 0x1a3fec0
}
```
----
### PMR introduction
----
### PMR introduction - create an new container
```cpp!
template<typename T>
class MyVector {
private:
VecImpl m_impl;
std::polymorphic_allocator<T> alloc;
public:
MyVector()
: m_impl{}
, alloc{std::pmr::get_default_resource()}{}
template<typename U>
MyVector(const std::polymorphic_allocator<U> other)
: m_impl{}
, alloc{other.resource()}{}
MyVector(memory_resource* res): m_impl{}, alloc{res}{}
public:
void push_back(const T& v) {
...
auto ptr = alloc.allocate(n);
...
}
}
```
----
## Current standard memory_rousource we can use
* std::pmr::new_delete_resource
* std::pmr::null_memory_resource
* std::pmr::unsynchronized_pool_resource
* std::pmr::synchronized_pool_resource
* std::pmr::monotonic_buffer_resource
----
### std::pmr::new_delete_resource
* a resource that delegates to the general heap(using operator new, operator heap)
* always available, general purpose and thread safe
* Used by default if no other resource is specified.
```cpp
std::pmr::memory_resource* newdel
= std::pmr::new_delete_resource();
```
----
### std::pmr::null_memory_resource
* don't do allocator, return bad_alloc when use.
``` cpp
std::pmr::memory_resource* null_resource
= std::pmr::null_memory_resource();
```
----
### std::pmr::unsynchronized_pool_resource
* Pools of ==similar-sized objects== ensure excellent spatial locality
* Good for dynamic data structures that ==grow and shrink==
* Single-threaded
* Appropriate only for non-concurrent containers
* Cannot be used simultaneously by containers in different threads
* Avoids concurrency lock overhead
----
### std::pmr::synchronized_pool_resource
* A thread-safe version ==std::pmr::unsynchronized_pool_resource==
----
### Two kinds of pool_resource
----
### std::pmr::monotonic_buffer_resource
* **Ultra-fast**, **single-threaded**, allocate from **contiguous buffers** and **do-nothing deallocate**
* For containers that grow monotonically throughout their lifetime
* Can allocate from stack memory
----
### std::pmr::monotonic_buffer_resource
----
### How to use memory_resource to initilize the pmr container
```cpp!
#include <memory_resource>
#include <vector>
#include <array>
int main() {
using PmrVec = std::pmr::vector<int>;
PmrVec v1{std::pmr::new_delete_resource()};
PmrVec v2{std::pmr::null_memory_resource()};
std::pmr::unsynchronized_pool_resource unsynchronized_pool;
std::pmr::synchronized_pool_resource synchronized_pool;
PmrVec v3{&unsynchronized_pool};
PmrVec v4{&synchronized_pool};
std::array<std::byte, 1024*1024> buffer;
std::pmr::monotonic_buffer_resource buf(buffer.data(), buffer.size());
PmrVec v5{&buf};
}
```
----
### Plan B when the memory_resource is exhausted
* ==memory_resource* upstream==
```cpp
class monotonic_buffer_resource: public memory_resource {
monotonic_buffer_resource(
void* buffer,
std::size_t buffer_size,
memory_resource* upstream = new_delete_resource()):
..., _upstream{upstream}{}
memory_resource* _upstream;
}
```
----
### Plan B when the memory_resource is exhausted
``` mermaid
graph LR
A[monotonic] --> B[new_delete_resource]
C[unsynchronized_pool] --> B
```
----
### You can also use hierachical upstream
```cpp=
int main() {
using PmrVec = std::pmr::vector<int>;
std::array<std::byte, 1024*1024> buffer;
std::pmr::monotonic_buffer_resource
buf(buffer.data(), buffer.size());
std::pmr::unsynchronized_pool_resource
unsynchronized_pool{&buf};
PmrVec v{&unsynchronized_pool};
}
```
``` mermaid
graph LR
A[monotonic] --> B[new_delete_resource]
C[unsynchronized_pool] --> A
D[std::pmr::vector< int>] --> C
```
----
# benchmark
* [BenchMark](https://quick-bench.com/q/tg68PNIz8D5PGL4axr9dDGHChmc)
----
# benchmark
* ==std::pmr::pool_options== can optimize pool_resources.
----
### Conclusion
* C++11 provide the ==allocator_traits== to guide the developers
* [Allocator Requirement](https://en.cppreference.com/w/cpp/named_req/Allocator)
* [AA class requiredment](https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer)
* C++17 hopes you use ==std::pmr::polymorphic_allocator== and ==memory_resource== to simplify the code.
* Using is simple.
* Implement memory_resource is simple.
* Be careful to choose the memory_resource in your scheme.
{"metaMigratedAt":"2023-06-18T00:40:51.604Z","metaMigratedFrom":"YAML","title":"Allocators in C++","breaks":true,"slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"09379b25-db04-47a4-8912-78e722b7a548\",\"add\":50991,\"del\":19880}]"}