[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

[cpp] iter/const iter

[C++] [STL] vector.insert cache affinity concern.

Blog post:
Microsoft’s vector::insert is slower than it should be

Reference:
http://en.cppreference.com/w/cpp/container/vector/insert

The blog post is not really anything special but did a research on
cache affinity with vector.insert.

The author was fascinated by MS's implementation of
vector.insert with PRValue, which uses 3 reverse function call.

The trick has been mentioned in the book(thus i don't see any 'wow' factor out of it):
Programming Pearls(2nd edition) Ch. 2 Section 3, P.14 while ago.
And it honors cache locality if the range of data fits into the cache.

The author also brought up using
memmove
to do the rotation.

The memmove() function shall copy n bytes from the object pointed to by s2 into the object pointed to by s1. 

Copying takes place as if the n bytes from the object pointed to by s2 are first copied into a temporary array of n bytes that does not overlap the objects pointed to by s1 and s2, and 

then the n bytes from the temporary array are copied into the object pointed to by s1.

That is, memmove needs an extra temporary space. And not cache locality friendly if data range is too large.

Will look into Folly's implementation later this week.

Reference:

https://github.com/facebook/folly/blob/master/folly/FBVector.h

[C++] Allocator

Reference:
A visitor’s guide to C++ allocators

[STL] EASTL -- Electronic Arts Standard Template Library

EASTL -- Electronic Arts Standard Template Library

[C++11] Threads and memory model for C++

Threads and memory model for C++

[C++11][Lambda][STL][NOTE] make lambda adaptable / ptr_fun / mem_fun

ptr_fun with a lambda function
Can we get the type of a lambda argument?
Efficient Use of Lambda Expressions and std::function


---------------
std::mem_fn
Use std::mem_fn to replace ptr_fun, mem_fun, mem_fun_ref
std::function
Use std::function to replace  std::unary_function , std::binary_function

The meaning of using this function wrapper is to make the sheer pointer to function adaptable by assigning some typedef.(Look up details of this typedef/using in ISO STD)

The unary function objects obtained from std::ref, std::cref, std::negate, std::logical_not, std::mem_fn, std::function, std::hash, or from another call to std::not1 have "argument_type" type defined, as are function objects derived from the deprecated std::unary_function.

[book] The C++ Standard Library - A Tutorial and Reference, 2nd Edition

I have received my copy of
The C++ Standard Library - A Tutorial and Reference, 2nd Edition 
SWEET!!!
I'll update my reading of this book here.

For the learning path of C++, books to read, read HERE.

Book Errata

[C++][STL] valarray

C++ valarray vs. vector

std::valarray

[c++][STL][Note] Allocator

Most of the standard containers never ask their associated allocator for memory.

In the C++ standard, the default allocator for objects of type T (cunningly known as allocator<T>) offers the typedefs allocator<T>::pointer and allocator<T>::reference, and it is expected that user-defined allocators will provide these typedefs, too.


The Standard says that an implementation of the STL is permitted to assume that all allocator objects of the same type are equivalent and always compare equal.



there's certainly good motivation for it:
template<typename T> // a user-defined allocator class SpecialAllocator {...}; // template typedef SpecialAllocator<Widget> SAW; // SAW = "SpecialAllocator // for Widgets" list<Widget, SAW> L1; list<Widget, SAW> L2: … L1.splice(L1 .begin(), L2); // move L2's nodes to the //front of L1





Recall that when list elements are spliced from one list to another, nothing is copied. Instead, a few pointers are adjusted, and the list nodes that used to be in one list find themselves in another. 

This makes splicing operations both fast and exception-safe. In the example above, the nodes that were in L2 prior to the splice are in L1 after the splice.




When L1 is destroyed, of course, it must destroy all its nodes (and deallocate their memory), and because it now contains nodes that were originally part of L2. L1's allocator must deallocate the nodes that were originally allocated by L2's allocator. 

Now it should be clear why the Standard permits implementers of the STL to assume that allocators of the same type are equivalent. It's so memory allocated by one allocator object (such as L2's) may be safely deallocated by another allocator object (such as L1's). 

Without being able to make such an assumption, splicing operations would be more difficult to implement.


STL implementations may assume that allocators of the same type are equivalent. 

It means that portable allocator objects — allocators that will function correctly under different STL implementations — may not have state.

Let's be explicit about this: it means that portable allocators may not have any nonstatic data members, at least not any that affect their behavior.

That means, for example, you can't have one SpecialAllocator that allocates from one heap and a different SpecialAllocator that allocates from a different heap. Such allocators wouldn't be equivalent, and STL implementations exist where attempts to use both allocators could lead to corrupt runtime data structures.

Notice that this is a runtime issue. Allocators with state will compile just fine. They just may not run the way you expect them to.

The responsibility for ensuring that all allocators of a given type are equivalent is yours. Don't expect compilers to issue a warning if you violate this constraint.
programmers concerned about portability will limit themselves to custom allocators with no state.


1.operator new and allocator:allocate differ in return types. operator new returns a void*, which is the traditional C++ way of representing a pointer to uninitialized memory. allocator::allocate returns a T* (via the pointer typedef), which is not only untraditional, it's premeditated fraud. The pointer returned from allocator::allocate doesn't point to a T object, because no T has yet been
constructed!

2.Implicit in the STL is the expectation that allocator::allocate's caller will eventually construct one or more T objects in the memory it returns (possibly via allocator::construct, via uninitialized_fill, or via some application of raw_storage_iterators), though in the case of vector::reserve or string::reserve, that may never happen.

3. Most of the standard containers never make a single call to the allocators with which they are instantiated.

list<int> L; // same as list<int, allocator<int> >; // allocator<int> is never asked to // allocate memory! set<Widget, SAW> s; // recall that SAW is a typedef for //SpecialAllocator<Widget>; no // SAW will ever allocate memory!

This oddity is true for list and all the standard associative containers (set. Multiset, map. and multimap).


That's because these are node-based containers, i.e., containers based on data structures in which a new node is dynamically allocated each time a value is to be stored. In the case of list, the nodes are list nodes.

In the case of the standard associative containers, the nodes are usually tree nodes, because the standard associative containers are typically implemented as balanced binary search trees.


Now , code says more than words:

template<typename T, // possible list typename Allocator = allocator<T> > // implementation class list{ private: Allocator alloc; // allocator for objects of type T struct ListNode{ // nodes in the linked list T data: ListNode *prev; ListNode *next; }; … }; template<typename T> // the standard allocator is declared class allocator { // like this, but this could be a userpublic: // written allocator template, too template<typename U> struct rebind{ typedef allocator<U> other; } … } Allocator::rebind<ListNode>::other;


What you do need to know is that if you choose to write allocators and use them with the standard containers, your allocators must provide the rebind template, because standard containers assume it will be there. (For debugging purposes, it's also helpful to know why node-based containers of T objects never ask for memory from the allocators for T objects.)

Summary:
Make your allocator a template, with the template parameter T representing the type of objects for which you are allocating memory.
Provide the typedefs pointer and reference, but always have pointer be T* and reference be T&.
Never give your allocators per-object state. In general, allocators should have no nonstatic data members.
Remember that an allocator's allocate member functions are passed the number of objects for which memory is required, not the number of bytes needed. Also remember that these functions return T* pointers Ma the pointer typedef), even though no T objects have yet been constructed.
Be sure to provide the nested rebind template on which standard containers depend.



---------------


template <class T> class malloc_allocator { public: typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; ... };

It's no accident that these types are so similar to those in an STL container: a container class usually gets those types directly from its allocator.

so the first thing a container has to do before using an allocator is create allocator objects.

any two malloc_allocator objects are interchangeable; if a1 and a2 are both of type malloc_allocator<int>, we can freely allocate memory through a1 and deallocate it through a2. We therefore define a comparison operator that says all malloc_allocator objects are equal:

template <class T> inline bool operator==(const malloc_allocator<T>&, const malloc_allocator<T>&) { return true; } template <class T> inline bool operator!=(const malloc_allocator<T>&, const malloc_allocator<T>&) { return false; }

Would you ever want to have an allocator where different objects weren't interchangeable? Certainly — but simple and useful examples are hard to come by. One obvious possibility is memory pools.

malloc_allocator<int>::pointer is int*, malloc_allocator<int>().allocate(1) returns enough memory for one int object.

Containers, like allocators, start with nested types: value_type, reference, const_reference, size_type, difference_type, iterator, and const_iterator. In general, most of those types can be taken directly from the container's allocator — thus illustrating why the container's value type and the allocator's must match.

The iterator types, of course, don't usually come from the allocator; usually an iterator is some kind of class, closely tied to the container's internal representation.

It's illegal to instantiate an allocator with an incomplete type. //Template issue



The only question is what happens when you perform an operation that requires two containers to cooperate on memory management. There are exactly two such operations in the standard library: swap (all containers) and std::list::splice. In principle, an implementation could handle them in several different ways:

Forbid swap or splice between two containers whose allocators aren't equal.
Put a test for allocator equality in swap and splice. If the allocators aren't equal, then fall back to some other operation like copying and assignment.
For swap only: swap the containers' allocators as well as their data. (It's hard to see how we could generalize this to splice. It also presents a problem: how do you swap things that don't have assignment operators?)



A sample allocator based on malloc
template <class T> class malloc_allocator { public: typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; template <class U> struct rebind { typedef malloc_allocator<U> other; }; malloc_allocator() {} malloc_allocator(const malloc_allocator&) {} template <class U> malloc_allocator(const malloc_allocator<U>&) {} ~malloc_allocator() {} pointer address(reference x) const { return &x; } const_pointer address(const_reference x) const { return x; } pointer allocate(size_type n, const_pointer = 0) { void* p = std::malloc(n * sizeof(T)); if (!p) throw std::bad_alloc(); return static_cast<pointer>(p); } void deallocate(pointer p, size_type) { std::free(p); } size_type max_size() const { return static_cast<size_type>(-1) / sizeof(T); } void construct(pointer p, const value_type& x) { new(p) value_type(x); } void destroy(pointer p) { p->~value_type(); } private: void operator=(const malloc_allocator&); }; template<> class malloc_allocator<void> { typedef void value_type; typedef void* pointer; typedef const void* const_pointer; template <class U> struct rebind { typedef malloc_allocator<U> other; }; }; template <class T> inline bool operator==(const malloc_allocator<T>&, const malloc_allocator<T>&) { return true; } template <class T> inline bool operator!=(const malloc_allocator<T>&, const malloc_allocator<T>&) { return false; }

Reference:
The Standard Librarian: What Are Allocators Good For?

[c++][STL] std::advance

std::advance

Iterator block_end=block_start;
std::advance(block_end,block_size);