Честно говоря, не думал, что пообщаюсь в живую с мастодонтами своего дела.
А именно такими мне казались дорогие форумчане, когда что-то искал по теме.
Но, похоже, время пришло.
На cyberforum мне не ответили. Теперь надежда на Вас.
Что было сделано:
Собственный аллокатор, который нормально сработал с std::vector.
Что хочется сделать:
Прокачать аллокатор для использования с std::map(и в будущем для собственного list'a), с имитацией поведения метода reserve(), который есть у std::vector.
I. Пример использования std::vector со своим аллокатором.
Здравствуйте, avovana, Вы писали:
A>Дорогие форумчане!
И тебе привет, дорогой
A>Честно говоря, не думал, что пообщаюсь в живую с мастодонтами своего дела.
Мастодонты вымерли примерно тогда же, когда и мамонты, а тут пока еще все живы, и отвечают
A>А именно такими мне казались дорогие форумчане, когда что-то искал по теме. A>Но, похоже, время пришло.
Всё когда-то бывает в первый раз
A>
Что было сделано:
A>Собственный аллокатор, который нормально сработал с std::vector.
A>
Что хочется сделать:
A>Прокачать аллокатор для использования с std::map(и в будущем для собственного list'a), с имитацией поведения метода reserve(), который есть у std::vector.
А в чем проблема? Я, допустим, аллокаторы давно писал, и проблематики на вскидку не помню. Вроде все работало
A>Вызов c заданием параметра — 5: A>
A>int main()
A>{
A> auto m = std::map<int, int, std::less<int>, AllocatorLogger<std::pair<const int, int>, 5>>{};
A> for(size_t i = 0; i < 5; ++i)
A> {
A> m[i] = i;
A> }
A>}
A>
A>Но... ругается. Не пойму, что ему надо. Помогите, пожалуйста, разобраться.
На что ругается-то?
По идее, аллокатор для map вызывается для аллокации памяти для каждого узла. Не совсем понятен фокус с выделением куска памяти *Size
Можно описать, чего хотелось и что получилось или не получилось?
A>Прокачать аллокатор для использования с std::map(и в будущем для собственного list'a), с имитацией поведения метода reserve(), который есть у std::vector.
А знаешь почему у std::vector есть метод reserve, а у std::map его нет? Ведь про него не забыли — существует причина по которой он отсутствует
A>Вот что я пробовал, но у меня не получилось.
Так и не получится. std::map будет всегда запрашивать у аллокатора память для одного узла дерева за раз.
Но выделять память блоками, конечно можно. Просто для этого тебе нужно использовать stateful-аллокатор.
То есть твой пользовательский аллокатор, который передаётся в std::map, должен хранить указатель (или ссылку) на родительский аллокатор или, как его лучше назвать, memory pool.
И в методе allocate не выделять память вызовом malloc, а отдавать указатель на уже выделенную память в родительском пуле. А если её там не хватает, то пусть уже родительский пул аллоцирует очередной большой блок памяти.
Re[2]: Собственный аллокатор с задаваемым выделением памяти
Спасибо за ответы!
M>Всё когда-то бывает в первый раз
Представляю, что разобраться будет не просто
Уже порядочно запутался, т.к. не могу найти простого мануала, а везде какие-то куски.
M>По идее, аллокатор для map вызывается для аллокации памяти для каждого узла. Не совсем понятен фокус с выделением куска памяти *Size
M>Можно описать, чего хотелось и что получилось или не получилось?
Сейчас есть такое задание — чтобы саллоцироватьп память заранее для последующего конструирования элементов.
Вот и хотелось как-нибудь(к примеру параметром) передать под сколько элементов нужно заранее саллоцировать память.
Как в std::vector::reserve(Size).
Теперь мне понимаю, что метод allocate у аллокатора std::map будет вызывать каждый раз.
M>А знаешь почему у std::vector есть метод reserve, а у std::map его нет? Ведь про него не забыли — существует причина по которой он отсутствует
No...
M>Так и не получится. std::map будет всегда запрашивать у аллокатора память для одного узла дерева за раз. M>Но выделять память блоками, конечно можно. Просто для этого тебе нужно использовать stateful-аллокатор. M>То есть твой пользовательский аллокатор, который передаётся в std::map, должен хранить указатель (или ссылку) на родительский аллокатор или, как его лучше назвать, memory pool. M>И в методе allocate не выделять память вызовом malloc, а отдавать указатель на уже выделенную память в родительском пуле. А если её там не хватает, то пусть уже родительский пул аллоцирует очередной большой блок памяти.
Прочитал статью arena allocator.
Мне кажется, Вы говорите примерно об этом.
Сложно она у меня пошла. Такое чувство, что авторы, пишущие на данную тему уже подразумевают, что читатель знает это, это и это + основную логику работы аллокатора.
А для новичка(для меня) очень сложно.
Самое простое, что нашел из книги Джосатиса — myalloc.cpp.
1. Правильно ли я понимаю, что в аллокатор:
template <typename T>
struct Allocator {
...
}
нужно будет добавить объект pool?
2. Правильно ли я понимаю, что:
стоит реализовать метод pointer allocate(size_type n) не так:
А использовать внутри этот самый pool вместо malloc'a внутри которого и будет реализована логика выделения памяти и предоставления указателя void *ptr наверх(в allocate).
Т.е. фактически строчка: void *ptr = malloc(sizeof(value_type) * n);
замениться на: void *ptr = pool.getMemory(sizeof(value_type) * n);
?
Здравствуйте, avovana, Вы писали:
A>Прочитал статью arena allocator.
Да, это правильное направление. В этой статье как раз за операции по выделению памяти отвечают пара сущностей. Arena отвечает за выделение больших блоков (в статье их число, правда, ограничено ровно одним на одну арену), а аллокатор только содержит указатель на его арену и лишь нарезает её память на мелкие куски запрашиваемого объёма.
A>1. Правильно ли я понимаю, что в аллокатор: A>нужно будет добавить объект pool?
Скорее не сам pool, а указатель на него. Ведь аллокаторы можно и нужно уметь копировать. А обычно в этом случае ведь не нужно копировать саму выделенную память, которую держит объект pool.
A>Т.е. фактически строчка: A> void *ptr = malloc(sizeof(value_type) * n); A>замениться на: A> void *ptr = pool.getMemory(sizeof(value_type) * n); A>?
Ну можно так, да.
А внутри функции pool::getMemory можно выделить больше памяти, чем запрошено. И информацию об этом сохранить в объекте pool, тогда при последующих вызовах getMemory можно не выделять новые блоки, а использовать остатки от уже выделенного.
Re[4]: Собственный аллокатор с задаваемым выделением памяти
W>А внутри функции pool::getMemory можно выделить больше памяти, чем запрошено. И информацию об этом сохранить в объекте pool, тогда при последующих вызовах getMemory можно не выделять новые блоки, а использовать остатки от уже выделенного.
#include <iostream>
class Arena
{
unsigned char * const data;
std::size_t const size;
std::size_t offset;
public:
explicit Arena(std::size_t s)
: data(static_cast<unsigned char *>(::operator new(s)))
, size(s)
, offset(0)
{
std::cout << "arena[" << this << "] of size " << size << " created.\n";
}
Arena(Arena const &) = delete;
Arena & operator=(Arena const &) = delete;
~Arena()
{
std::cout << "arena[" << this << "] destroyed; final fill level was: " << offset << "\n";
::operator delete(data);
}
void * allocate(std::size_t n, std::size_t a)
{
std::cout << __PRETTY_FUNCTION__ << std::endl;
std::cout << " " << "size is: " << n << std::endl;
std::cout << " " << "align is: " << a << std::endl;
offset = (offset + a - 1) / a * a;
std::cout << "arena[" << this << "] allocating " << n << " bytes at offset " << offset << ".\n";
if (offset + n > size)
{
throw std::bad_alloc();
}
void * result = data + offset;
offset += n;
return result;
}
void deallocate(void *, std::size_t n)
{
std::cout << "arena[" << this << "] may deallocate " << n << " bytes.\n";
}
};
В следующей итерации собираюсь:
1) перенести функциональность помощника аллокатора(Arena) в класс аллокатора.
2) реализовать собственному аллокатору возможность задавать начальное кол-во выделяемой памяти путем передачи шаблонного параметра.
Re[5]: Собственный аллокатор с задаваемым выделением памяти
Здравствуйте, avovana, Вы писали:
A>Прокачать аллокатор для использования с std::map(и в будущем для собственного list'a), с имитацией поведения метода reserve(), который есть у std::vector.
Это для производительности нужно?
Если да, возьми мой готовый: https://github.com/Const-me/CollectionMicrobench
Тестировал немного, но на венде с msvc и линупсе с clang и libc++ оно у меня работало OK.
Только связные списки с ним сломаются, если делить списки надвое, или перемещать ноды между списками.
Re[2]: Собственный аллокатор с задаваемым выделением памяти
Здравствуйте, Константин, Вы писали:
К>Это для производительности нужно?
Очень интересный пример, посмотрел. Мощный.
Но у меня свой маленький проект.
Сейчас прохожу курс С++ программиста.
После очередной лекции было такое дз по созданию собственного аллокатора и list'a.
Здравствуйте, watchmaker, Вы писали: w>Ну назвать этот код работающим можно весьма условно
Решил уйти от Arena.
Ситуация на данный момент следующая.
Пока list отложил в сторону, занят аллокатором.
На данный момент сделано задание выделяемой памяти аллокатору с помощью параметра.
Раньше был голый указатель на выделяемую память и выделялось всё отлично:
template <typename T, size_t Size = 400>
struct Allocator {
using value_type = T;
using pointer = T *;
unsigned char * const data;
std::size_t const size;
std::size_t offset;
Allocator()
: data(static_cast<unsigned char *>(::operator new(Size)))
, size(Size)
, offset(0)
{ }
pointer allocate(std::size_t n)
{
if (offset + n > size)
{
throw std::bad_alloc();
}
void * result = data + offset;
offset += n;
return static_cast<pointer>(result);
}
...
}
Но освобождение памяти, я так понимаю, не происходило. Надо было обернуть data в unique_ptr, что было сделано(про что писали — RAII).
Но полетели ошибки.
В основном файле создается std::map с собственным аллокатором. std::map заполняется элементами.
В файле allocatorarena.h реализация аллокатора. Функционал arena'ы уже выброшен. Есть просто аллокатор.
Вспомогательные файлы newdelete.h и newdelete.cc помогают сделать видимыми выделение и освобождение памяти.
В файле forward_list.h реализация контейнера, что пока не нужно.
Сам немного запутался и не могу понять что не так делается.
Помогите, пожалуйста, разобраться.
