Как написать свой аллокатор?
1,00
р.
Часто пишут что с не-стандартным аллокатором код может работать быстрее, а как вообще написать свой аллокатор?
Ответ
Требования к аллокаторам, и их значения по-умолчанию приведены в главе "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
Ответ
Требования к аллокаторам, и их значения по-умолчанию приведены в главе "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 }
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 }
