[std-proposals] “Winked-out” optimization on generic collections

[Gareth Lloyd]

A generic collection can take an arbitrary allocator to control its
allocation behaviour. That allocator may be monotonic, as in deallocation
is a noop. This means that for types that were allocated and constructed
with this allocator then the destruction, if is_trivially_destructible, and
deallocation would be noops. This has a performance benefit when used in
your own types because the destruction of your internal structures can be
“Winked-out”, you just don’t have to do it.

On initial inspection this all looks great, take C++17
polymorphic_allocator and a monotonic_buffer_resource, turn up optimization
and LTO, devirtualization kicks in, calls are inlined, and destruction of
our collection should be “winked-out” right?

Wrong. This works fine for vector, but not for node structures like list.
The root problem is no compiler (msvc/gcc/clang) optimizes away empty loops
that have a data dependent traversal. 6.8.2.2 Forward progress hints to me
that compilers can. (http://eel.is/c++draft/intro.progress#1).

int init_int();

void * init_ptr();

void foo()

{

//loop eliminated

for(auto i = init_int(); i; --i);



//loop not eliminated

for(

auto p = init_ptr();

p;

p = *(void**)p

);

}

foo():

sub rsp, 8

call init_int()

call init_ptr()

test rax, rax

je .L1

.L3:

mov rax, QWORD PTR [rax]

test rax, rax

jne .L3

.L1:

add rsp, 8

ret

So that is one part of the story, compilers could implement this
optimization if I’m understanding the standard correctly. This all happens
outside the language. With pmr it is perfectly fine that a pmr container is
not statically determined to be trivially_destructible. But you may want to
have generic containers which take another allocator via compile time
polymorphism which enables the “winked-out” optimization irrespective of
optimizer used and additionally you also want the generic container to
itself be trivially_destructible.

For a generic collection to be potentially trivially destructible it cannot
provide its own destructor. Look at the following illustrative code:

#include <type_traits>

#include <iostream>

#include <memory>

#include <experimental/type_traits>



// Example memory resource

struct slab_allocator_resource

{

explicit slab_allocator_resource(std::size_t spaceNeeded)

: m_buffer(std::malloc(spaceNeeded)),

m_freeBegin(m_buffer),

m_freeSpace(spaceNeeded)

{

if (!m_buffer) throw std::bad_alloc();

}



~slab_allocator_resource() { std::free(m_buffer); }



template<typename T>

[[nodiscard]] T * allocate(std::size_t n)

{

return static_cast<T *>(allocate_bytes(alignof(T), sizeof(T) * n));

}



private:

void * allocate_bytes(std::size_t align, std::size_t bytes)

{

auto mem = std::align(align, bytes, m_freeBegin, m_freeSpace);

if (!mem) throw std::bad_alloc();

m_freeBegin = static_cast<char *>(m_freeBegin) + bytes;

m_freeSpace -= bytes;

return mem;

}



void * m_buffer;

void * m_freeBegin;

std::size_t m_freeSpace;

};



// Example allocator

template<typename T>

struct my_alloc

{

using noop_deallocate = std::true_type; // Indicate it is a noop
deallocate

using value_type = T;

my_alloc() = delete;

my_alloc(slab_allocator_resource* res) : res{res} {}

template <class U> constexpr my_alloc(const my_alloc<U>&) noexcept {}

[[nodiscard]] T* allocate(std::size_t n) { return res->allocate<T>(n); }

slab_allocator_resource * res;

};



//Proposed something like this into allocator_traits

template<typename Alloc>

struct allocator_traits_demo

{

private:

template<class U> using detect_noop_deallocate = typename
U::noop_deallocate;



public:

using is_noop_deallocate =

std::experimental::detected_or_t<std::false_type,
detect_noop_deallocate, Alloc>;

};



template<typename T>

struct node

{

node * m_next = nullptr;

T m_value = T{};



explicit node(T value, node * next = nullptr)

: m_next{next},

m_value{value} {}

};



template<typename T, typename Alloc>

struct list_impl : Alloc

{

//**************REGULAR IMPLEMENTATION DETAIL START

using allocator_type = typename std::allocator_traits<Alloc>::template
rebind_alloc<node<T>>;



list_impl() = default;

explicit list_impl(allocator_type const & a) : Alloc{a} {}



void push(T v)

{

auto a = allocator_type{*this};

auto new_node = a.allocate(1);

a.construct(new_node, v, m_head);

m_head = new_node;

}



node<T> * m_head = nullptr;

//**************REGULAR IMPLEMENTATION DETAIL END



//**************CONDITIONAL DTR START

using use_default_dtr = std::conjunction<

std::is_trivially_destructible<node<T>>,

typename allocator_traits_demo<allocator_type>::is_noop_deallocate

;

void non_trivial_dtr() //may be required depending on T and Alloc

{

auto a = allocator_type{*this};

auto current_node = m_head;

while (current_node != nullptr)

{

auto old_node = current_node;

current_node = current_node->m_next;

a.destroy(old_node);

a.deallocate(old_node, 1);

}

};



// Not possible to SFINAE

//

//template<typename =
std::enable_if_t<std::negation<use_default_dtr>::value>>

//~list_impl(){ non_trivial_dtr(); }



//**************CONDITIONAL DTR END

};



//**************CONDITIONAL DTR SHIM START

template<typename Impl>

struct add_destructor : Impl

{

using Impl::Impl;

~add_destructor()

{

Impl::non_trivial_dtr();

}

};



template <typename T, typename Alloc = std::allocator<int>>

using list = std::conditional_t<

list_impl<T,Alloc>::use_default_dtr::value, // Use condition

list_impl<T, Alloc>, // ignore dtr

add_destructor<list_impl<T,Alloc>> // apply dtr

;

//**************CONDITIONAL DTR SHIM END



int main()

{

using sut1_t = list<int, my_alloc<int>>;

using sut2_t = list<sut1_t, my_alloc<sut1_t>>;



std::cout

<< std::boolalpha

<< "list of ints is trivially destructible: "

<< std::is_trivially_destructible_v<sut1_t> << '\n'

<< "list of lists of ints is trivially destructible: "

<< std::is_trivially_destructible_v<sut2_t> << '\n';

};



Things to notice

1) Need to detect something within the allocator so that we can modify
the generic data type accordingly. i.e. noop_deallocate

2) In my example a strong coupling between the allocator and the
resource is shown, for a more general allocator a detector may be required
to propagate that something from the resource to a generic allocator

3) The data type uses this information along with other information to
form a condition for if the non-trivial destructor is required

4) Enable if technique does not work

5) Type needs wrapping to add the non-trivial destructor if it is
required



I propose:

· Something like noop_deallocate to be added as an optional member
type of the allocator

· A corresponding detector added to allocator_traits


Requesting thoughts on:

· What should be the approach to make conditional destruction easier
to implement?