Страницы

Поиск по вопросам

среда, 17 июля 2019 г.

Как написать свой аллокатор?

Часто пишут что с не-стандартным аллокатором код может работать быстрее, а как вообще написать свой аллокатор?


Ответ

Требования к аллокаторам, и их значения по-умолчанию приведены в главе "Allocator requirements [allocator.requirements]". В этой же главе приводится пример минимального аллокатора:
template struct SimpleAllocator { typedef Tp value_type; SimpleAllocator(аргументы конструктора);
template SimpleAllocator(const SimpleAllocator& other);
Tp* allocate(std::size_t n); void deallocate(Tp* p, std::size_t n); };
template bool operator==(const SimpleAllocator&, const SimpleAllocator&); template bool operator!=(const SimpleAllocator&, const SimpleAllocator&);
Предполагается, что контейнеры обязаны обращаться к аллокатору не напрямую, а через шаблон std::allocator_traits, который предоставляет значения по-умолчанию, такие как typedef T* pointer;, и т.п.
Однако существующие реализации стандартных библиотек не везде используют allocator_traits. По этому если мы попробуем например скомпилировать код std::basic_string, SimpleAllocator> s; то мы получим такие ошибки:
/usr/local/bin/../lib/gcc/x86_64-unknown-linux-gnu/4.9.2/../../../../include/c++/4.9.2/bits/basic_string.h:114:41: error: 'rebind' following the 'template' keyword does not refer to a template typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
или
1>S:\MSVS2013\VC\include\xstring(664): error C2903: 'rebind' : symbol is neither a class template nor a function template
В обоих случаях в реализации стандартной библиотеки написано _Alloc::rebind вместо allocator_traits<_Alloc>::rebind
Таким образом, при написании своего аллокатора, надо смотреть на ошибки компиляции, и при необходимости дописывать нужные члены класса.
Ниже приведен пример Arena аллокатора, который компилируется (VC++2013, g++-4.9.2)
#include #include #include #include
class Arena { public: Arena() {} ~Arena() { assert(m_allocations == 0); }
void* allocate(std::size_t n) { if (n > m_available) { m_chunks.emplace_back(100500); m_available = m_chunks.back().size(); m_memory = &m_chunks.back().front(); }
auto mem = m_memory; m_available -= n; m_memory += n; ++m_allocations; return mem; } void deallocate(void* p, std::size_t n) { --m_allocations; auto mem = (unsigned char*)p; if (mem + n == m_memory) { m_memory = mem; m_available += n; } }
private: std::deque> m_chunks; std::size_t m_available = 0; unsigned char* m_memory; int m_allocations = 0; };
template struct ArenaAllocator { using value_type = T;
using Traits = std::allocator_traits>;
#if !defined _MSC_VER // libstdc++ использует конструктор по умолчанию: // __a == _Alloc() ArenaAllocator() : m_arena(nullptr) {}
// libstdc++ требует следующие определения using size_type = typename std::allocator::size_type; using difference_type = typename std::allocator::difference_type; using pointer = typename std::allocator::pointer; using const_pointer = typename std::allocator::const_pointer; // "reference" не входит Allocator Requirements, // но libstdc++ думает что она всегда работает с std::allocator. using reference = typename std::allocator::reference; using const_reference = typename std::allocator::const_reference; #endif
explicit ArenaAllocator(Arena& arena) : m_arena(&arena) {} template ArenaAllocator(const ArenaAllocator& other) : m_arena(other.m_arena) {}
T* allocate(std::size_t n) { return (T*)m_arena->allocate(n * sizeof(T)); } void deallocate(T* p, std::size_t n) { m_arena->deallocate(p, n * sizeof(T)); }
// требуется в VC++ и libstdc++ template void construct(U* p, Args&&... args) { std::allocator().construct(p, std::forward(args)...); } template void destroy(U* p) { std::allocator().destroy(p); } template struct rebind { using other = ArenaAllocator; };
Arena* m_arena; };
template bool operator==(const ArenaAllocator& lhs, const ArenaAllocator& rhs) { return lhs.m_arena == rhs.m_arena; } template bool operator!=(const ArenaAllocator& lhs, const ArenaAllocator& rhs) { return !(lhs == rhs); }
#include #include #include #include #include #include #include #include #include #include
using a_string = std::basic_string, ArenaAllocator>;
template using a_vector = std::vector>; template using a_deque= std::deque>; template using a_list = std::list>; template using a_set = std::set, ArenaAllocator>; template using a_map = std::map, ArenaAllocator>>; template using a_unordered_set = std::unordered_set, std::equal_to, ArenaAllocator>; template using a_unordered_map = std::unordered_map, std::equal_to, ArenaAllocator>>;
struct X {};
int main() { Arena arena; ArenaAllocator arena_allocator(arena);
a_string s_empty(arena_allocator); a_string s_123("123", arena_allocator);
a_vector v_int({1, 2, 3}, arena_allocator); a_vector v_x(42, X{}, arena_allocator); a_vector v_str({s_empty, s_123}, arena_allocator); a_vector v_str_copy(v_str, arena_allocator); a_deque d_int({1, 2, 3}, arena_allocator); a_list l_int({1, 2, 3}, arena_allocator); a_set s_int({1, 2, 3}, std::less{}, arena_allocator); a_map m_str_int(arena_allocator); a_unordered_set us_int(arena_allocator);
auto p = std::allocate_shared(arena_allocator, 123);
#if 0 // этот код не работает в VC++ и g++ a_unordered_map um_str_int(arena_allocator); std::function f(std::allocator_arg_t{}, arena_allocator, []{}); #endif }

Комментариев нет:

Отправить комментарий