Распределитель STL на основе стекового буфера?
Мне было интересно, возможно ли иметь стандартную библиотеку C++, совместимую allocator который использует (фиксированный размер) буфер, который живет в стеке.
Почему-то кажется, что этот вопрос еще не задавался таким образом на SO, хотя на него, возможно, неявно отвечали в другом месте.
Так что, в основном, кажется, что мои поиски позволяют создать распределитель, который использует буфер фиксированного размера. Теперь, на первый взгляд, это должно означать, что также должна быть возможность иметь распределитель, который использует буфер фиксированного размера, который "живет" в стеке, но кажется, что такой широко распространенной реализации не существует.
Позвольте мне привести пример того, что я имею в виду:
{ ...
char buf[512];
typedef ...hmm?... local_allocator; // should use buf
typedef std::basic_string<char, std::char_traits<char>, local_allocator> lstring;
lstring str; // string object of max. 512 char
}
Как это будет осуществимо?
Ответ на этот другой вопрос (спасибо Р. Мартиньо Фернандесу) связан со стековым распределителем из источников хрома: http://src.chromium.org/viewvc/chrome/trunk/src/base/stack_container.h
Тем не менее, этот класс кажется чрезвычайно своеобразным, тем более что StackAllocator не имеет ctor по умолчанию - и там я думал, что каждый класс распределителя нуждается в ctor по умолчанию.
5 ответов
По-видимому, есть соответствующий Распределитель стека от одного Howard Hinnant.
Он работает с использованием буфера фиксированного размера (через ссылку arena объект) и обратно в кучу, если запрошено слишком много места.
Этот распределитель не имеет ctor по умолчанию, и поскольку Говард говорит:
Я обновил эту статью новым распределителем, полностью соответствующим C++11.
Я бы сказал, что для распределителя не обязательно иметь ctor по умолчанию.
Определенно возможно создать полностью соответствующий C++11/C++14 распределитель стека *. Но вам нужно рассмотреть некоторые последствия реализации и семантики размещения стеков и их взаимодействия со стандартными контейнерами.
Вот полностью соответствующий C++11/C++14 распределитель стека (также размещенный на моем github):
#include <functional>
#include <memory>
template <class T, std::size_t N, class Allocator = std::allocator<T>>
class stack_allocator
{
public:
typedef typename std::allocator_traits<Allocator>::value_type value_type;
typedef typename std::allocator_traits<Allocator>::pointer pointer;
typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename std::allocator_traits<Allocator>::size_type size_type;
typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
typedef Allocator allocator_type;
public:
explicit stack_allocator(const allocator_type& alloc = allocator_type())
: m_allocator(alloc), m_begin(nullptr), m_end(nullptr), m_stack_pointer(nullptr)
{ }
explicit stack_allocator(pointer buffer, const allocator_type& alloc = allocator_type())
: m_allocator(alloc), m_begin(buffer), m_end(buffer + N),
m_stack_pointer(buffer)
{ }
template <class U>
stack_allocator(const stack_allocator<U, N, Allocator>& other)
: m_allocator(other.m_allocator), m_begin(other.m_begin), m_end(other.m_end),
m_stack_pointer(other.m_stack_pointer)
{ }
constexpr static size_type capacity()
{
return N;
}
pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
{
if (n <= size_type(std::distance(m_stack_pointer, m_end)))
{
pointer result = m_stack_pointer;
m_stack_pointer += n;
return result;
}
return m_allocator.allocate(n, hint);
}
void deallocate(pointer p, size_type n)
{
if (pointer_to_internal_buffer(p))
{
m_stack_pointer -= n;
}
else m_allocator.deallocate(p, n);
}
size_type max_size() const noexcept
{
return m_allocator.max_size();
}
template <class U, class... Args>
void construct(U* p, Args&&... args)
{
m_allocator.construct(p, std::forward<Args>(args)...);
}
template <class U>
void destroy(U* p)
{
m_allocator.destroy(p);
}
pointer address(reference x) const noexcept
{
if (pointer_to_internal_buffer(std::addressof(x)))
{
return std::addressof(x);
}
return m_allocator.address(x);
}
const_pointer address(const_reference x) const noexcept
{
if (pointer_to_internal_buffer(std::addressof(x)))
{
return std::addressof(x);
}
return m_allocator.address(x);
}
template <class U>
struct rebind { typedef stack_allocator<U, N, allocator_type> other; };
pointer buffer() const noexcept
{
return m_begin;
}
private:
bool pointer_to_internal_buffer(const_pointer p) const
{
return (!(std::less<const_pointer>()(p, m_begin)) && (std::less<const_pointer>()(p, m_end)));
}
allocator_type m_allocator;
pointer m_begin;
pointer m_end;
pointer m_stack_pointer;
};
template <class T1, std::size_t N, class Allocator, class T2>
bool operator == (const stack_allocator<T1, N, Allocator>& lhs,
const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
return lhs.buffer() == rhs.buffer();
}
template <class T1, std::size_t N, class Allocator, class T2>
bool operator != (const stack_allocator<T1, N, Allocator>& lhs,
const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
return !(lhs == rhs);
}
Этот распределитель использует предоставленный пользователем буфер фиксированного размера в качестве начального источника памяти, а затем возвращается к вторичному распределителю (std::allocator<T> по умолчанию), когда не хватает места.
Что нужно учитывать:
Прежде чем вы просто начнете использовать распределитель стека, вам необходимо рассмотреть шаблоны распределения. Во-первых, при использовании буфера памяти в стеке необходимо учитывать, что именно означает выделение и освобождение памяти.
Самый простой метод (и метод, использованный выше) состоит в том, чтобы просто увеличить указатель стека для выделений и уменьшить его для освобождения. Обратите внимание, что это сильно ограничивает возможности использования распределителя на практике. Это будет хорошо работать, скажем, для std::vector (который выделит один непрерывный блок памяти), если используется правильно, но не будет работать, скажем, std::map, который будет распределять и освобождать объекты узлов в различном порядке.
Если ваш распределитель стека просто увеличивает и уменьшает указатель стека, то вы получите неопределенное поведение, если ваши выделения и освобождения не в порядке LIFO. Даже std::vector вызовет неопределенное поведение, если сначала выделит один непрерывный блок из стека, затем выделит второй блок стека, затем освободит первый блок, что будет происходить каждый раз, когда вектор увеличивает свою емкость до значения, которое все еще меньше, чем stack_size, Вот почему вам нужно заранее зарезервировать размер стека. (Но см. Примечание ниже относительно реализации Говарда Хиннанта.)
Что подводит нас к вопросу...
Что вы действительно хотите от распределителя стека?
Действительно ли вам нужен распределитель общего назначения, который позволит вам выделять и освобождать фрагменты памяти разных размеров в разном порядке (например, malloc), за исключением того, что он рисует из предварительно выделенного стекового буфера вместо вызова sbrk? Если так, то вы в основном говорите о реализации распределителя общего назначения, который каким-то образом поддерживает свободный список блоков памяти, только пользователь может предоставить ему уже существующий буфер стека. Это гораздо более сложный проект. (А что делать, если у него заканчивается пространство? Бросить std::bad_alloc? Отступить на кучу?)
Приведенная выше реализация предполагает, что вам нужен распределитель, который будет просто использовать шаблоны выделения LIFO и использовать другой распределитель, если ему не хватит места. Это прекрасно работает для std::vector, который всегда будет использовать один непрерывный буфер, который может быть зарезервирован заранее. когда std::vector требуется больший буфер, он выделит больший буфер, скопирует (или переместит) элементы в меньший буфер, а затем освободит меньший буфер. Когда вектор запрашивает больший буфер, вышеприведенная реализация stack_allocator просто отступит к вторичному распределителю (который является std::allocator по умолчанию.)
Так, например:
const static std::size_t stack_size = 4;
int buffer[stack_size];
typedef stack_allocator<int, stack_size> allocator_type;
std::vector<int, allocator_type> vec((allocator_type(buffer))); // double parenthesis here for "most vexing parse" nonsense
vec.reserve(stack_size); // attempt to reserve space for 4 elements
std::cout << vec.capacity() << std::endl;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);
// Assert that the vector is actually using our stack
//
assert(
std::equal(
vec.begin(),
vec.end(),
buffer,
[](const int& v1, const int& v2) {
return &v1 == &v2;
}
)
);
// Output some values in the stack, we see it is the same values we
// inserted in our vector.
//
std::cout << buffer[0] << std::endl;
std::cout << buffer[1] << std::endl;
std::cout << buffer[2] << std::endl;
std::cout << buffer[3] << std::endl;
// Attempt to push back some more values. Since our stack allocator only has
// room for 4 elements, we cannot satisfy the request for an 8 element buffer.
// So, the allocator quietly falls back on using std::allocator.
//
// Alternatively, you could modify the stack_allocator implementation
// to throw std::bad_alloc
//
vec.push_back(50);
vec.push_back(60);
vec.push_back(70);
vec.push_back(80);
// Assert that we are no longer using the stack buffer
//
assert(
!std::equal(
vec.begin(),
vec.end(),
buffer,
[](const int& v1, const int& v2) {
return &v1 == &v2;
}
)
);
// Print out all the values in our vector just to make sure
// everything is sane.
//
for (auto v : vec) std::cout << v << ", ";
std::cout << std::endl;
Смотрите: http://ideone.com/YhMZxt
Опять же, это хорошо работает для вектора - но вы должны спросить себя, что именно вы собираетесь делать с распределителем стека. Если вам нужен распределитель памяти общего назначения, который просто извлекается из стекового буфера, вы говорите о гораздо более сложном проекте. Однако простой распределитель стека, который просто увеличивает и уменьшает указатель стека, будет работать для ограниченного набора вариантов использования. Обратите внимание, что для не POD-типов вам нужно использовать std::aligned_storage<T, alignof(T)> создать фактический буфер стека.
Я также хотел бы отметить, что в отличие от реализации Говарда Хиннанта, вышеупомянутая реализация явно не проверяет, что при вызове deallocate(), переданный указатель является последним выделенным блоком. Реализация Hinnant просто ничего не сделает, если переданный указатель не является LIFO-упорядоченным освобождением. Это позволит вам использовать std::vector без предварительного резервирования, потому что распределитель будет в основном игнорировать попытку вектора освободить начальный буфер. Но это также немного размывает семантику распределителя и зависит от поведения, которое довольно специфично связано с тем, как std::vector Известно, что работает. Я чувствую, что мы можем просто сказать, что передавая любой указатель на deallocate() который не был возвращен при последнем звонке allocate() приведет к неопределенному поведению и оставит все как есть.
* Наконец - следующее предостережение: представляется спорным, является ли функция, которая проверяет, находится ли указатель в границах буфера стека, даже определенным поведением по стандарту. Порядок сравнения двух указателей из разных new/malloc'буферы это, возможно, поведение, определяемое реализацией (даже с std::less), что, возможно, делает невозможным написание стандартизированной реализации распределителя стека, которая использует распределение кучи. (Но на практике это не имеет значения, если вы не используете 80286 в MS-DOS.)
** Наконец (действительно сейчас), также стоит отметить, что слово "стек" в распределителе стека является своего рода перегруженным, чтобы ссылаться как на источник памяти (массив стеков фиксированного размера), так и на метод выделения (приращение LIFO). / уменьшить указатель стека). Когда большинство программистов говорят, что им нужен распределитель стека, они думают о первом значении, не обязательно учитывая семантику последнего, и о том, как эта семантика ограничивает использование такого распределителя со стандартными контейнерами.
Начиная с C++17 это сделать довольно просто. Вся заслуга принадлежит автору самого тупого распределителя, поскольку это то, на чем он основан.
Самый тупой распределитель - это монотомный бамп-распределитель, который занимает char[]ресурс в качестве основного хранилища. В исходной версии этоchar[] помещается в кучу через mmap, но изменить его так, чтобы он указывал на char[] в стеке.
template<std::size_t Size=256>
class bumping_memory_resource {
public:
char buffer[Size];
char* _ptr;
explicit bumping_memory_resource()
: _ptr(&buffer[0]) {}
void* allocate(std::size_t size) noexcept {
auto ret = _ptr;
_ptr += size;
return ret;
}
void deallocate(void*) noexcept {}
};
Это выделяет Size байты в стеке при создании, по умолчанию 256.
template <typename T, typename Resource=bumping_memory_resource<256>>
class bumping_allocator {
Resource* _res;
public:
using value_type = T;
explicit bumping_allocator(Resource& res)
: _res(&res) {}
bumping_allocator(const bumping_allocator&) = default;
template <typename U>
bumping_allocator(const bumping_allocator<U,Resource>& other)
: bumping_allocator(other.resource()) {}
Resource& resource() const { return *_res; }
T* allocate(std::size_t n) { return static_cast<T*>(_res->allocate(sizeof(T) * n)); }
void deallocate(T* ptr, std::size_t) { _res->deallocate(ptr); }
friend bool operator==(const bumping_allocator& lhs, const bumping_allocator& rhs) {
return lhs._res == rhs._res;
}
friend bool operator!=(const bumping_allocator& lhs, const bumping_allocator& rhs) {
return lhs._res != rhs._res;
}
};
И это собственно распределитель. Обратите внимание, что было бы тривиально добавить сброс в диспетчер ресурсов, позволяющий создать новый распределитель, снова начиная с начала региона. Также можно было бы реализовать кольцевой буфер со всеми обычными рисками.
Что касается того, когда вам может понадобиться что-то вроде этого: я использую это во встроенных системах. Встроенные системы обычно плохо реагируют на фрагментацию кучи, поэтому иногда бывает удобно иметь возможность использовать динамическое распределение, которое не выполняется в куче.
Распределитель STL на основе стека имеет настолько ограниченную полезность, что я сомневаюсь, что вы найдете много предшествующего уровня техники. Даже простой пример, который вы цитируете, быстро взрывается, если позже вы решите скопировать или удлинить исходный lstring,
Для других контейнеров STL, таких как ассоциативные (основанные на дереве) или даже vector а также deque При использовании одного или нескольких смежных блоков оперативной памяти семантика использования памяти быстро становится неуправляемой в стеке практически при любом реальном использовании.
Это на самом деле чрезвычайно полезная практика, и ее довольно часто используют в разработке, такой как игры. Встраивание памяти в стек или в выделение структуры класса может иметь решающее значение для скорости и / или управления контейнером.
Чтобы ответить на ваш вопрос, речь идет о реализации контейнера stl. Если контейнер не только создает экземпляры, но и сохраняет ссылку на ваш распределитель как член, тогда вы можете приступить к созданию фиксированной кучи, я обнаружил, что это не всегда так, поскольку он не является частью спецификации. В противном случае это становится проблематичным. Одним из решений может быть обтекание контейнера, вектора, списка и т. Д. Другим классом, который содержит хранилище. Тогда вы можете использовать распределитель, чтобы извлечь из этого. Это может потребовать много магии шаблонов (тм).
Это действительно зависит от ваших требований, конечно, если вам нравится, вы можете создать распределитель, который работает только со стеком, но он будет очень ограничен, так как один и тот же объект стека не доступен из любой части программы, как объект кучи.
Я думаю, что эта статья объясняет распределителям это очень хорошо
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079