Как реализовать строку, которая размещается исключительно в стеке
В проекте около десяти лет назад мы обнаружили, что std::vectorДинамические распределения вызвали серьезную потерю производительности. В этом случае было выделено много маленьких векторов, поэтому быстрое решение состояло в том, чтобы написать вектороподобный класс, обертывающий вокруг предварительно выделенного стека char массив используется как сырое хранилище для его емкости. Результатом было static_vector<typename T, std::size_t Max>, Подобную вещь достаточно легко написать, если вы знаете несколько основ, и вы можете найти довольно много таких зверей в сети. На самом деле, Boost уже есть.
Работая над встроенной платформой сейчас, нам нужно static_basic_string, Это будет строка, которая предварительно выделяет фиксированный максимальный объем памяти в стеке и использует его в качестве своей емкости.
Сначала я подумал, что это должно быть довольно легко (это может быть основано на существующих static_vectorв конце концов), но, глядя снова на std::basic_stringВ интерфейсе я не уверен больше. Это намного сложнее, чем std::vectorИнтерфейс. Особенно реализация семьи find() функции std::basic_string приходит не просто утомительное занятие
Это заставило меня задуматься снова. В конце концов, это то, для чего были созданы распределители: заменить распределение на основе new а также delete с некоторыми другими средствами. Однако сказать, что интерфейс распределителя является громоздким, было бы преуменьшением. Есть несколько статей, объясняющих это, но есть причина, по которой я видел так мало доморощенных распределителей за последние 15 лет.
Вот мой вопрос:
Если бы вам пришлось реализовать basic_string двойник, как бы ты это сделал?
- Написать свой
static_basic_string? - Написать распределитель для передачи
std::basic_string? - Делать что-то, о чем я не думал?
- Использовать что-то от наддува я не в курсе?
Как всегда, есть довольно существенное ограничение для нас: находясь на встроенной платформе, мы привязаны к GCC 4.1.2, поэтому мы можем использовать только C++03, TR1 и boost 1.52.
7 ответов
Первый вопрос: какой дополнительный интерфейс вы используете? Большинство std::stringдополнительные интерфейсы могут быть тривиально реализованы с использованием функций в <algorithm> (напримерstd::find, std::find_if а также std::search), и во многих случаях есть большие куски, которые не будут использоваться в любом случае. Просто реализуйте его по мере необходимости.
Я не думаю, что вы можете сделать это с помощью специального распределителя. Единственный способ получить память "в стеке" - это объявить ее как член пользовательского распределителя, что создаст все виды проблем при копировании. И распределители должны быть копируемыми, а копии должны быть идемпотентными.
Возможно, вы можете найти бесплатную реализацию в сетиstd::string который использует маленькую строковую реализацию; затем измените его так, чтобы размер среза (за пределами которого он использовал динамическое размещение) был больше, чем любые строки, которые вы фактически используете. (Существует несколько реализаций стандартной библиотеки с открытым исходным кодом; в одной поставляемой с g++ все еще используется COW, но я подозреваю, что большинство других используют SSO.)
Есть много basic_string реализации, некоторые полностью основанные на динамическом размещении, другие на динамическом размещении только для строки шире, чем заданная длина (фактически, они используют свой собственный внутренний буфер, когда он подходит).
Использование распределителя, вероятно, не лучший способ, поскольку интерфейс между строкой и распределителем предполагает, что объект распределителя является частью контейнера, но выделенная память поступает извне самого контейнера. Вы можете организовать это, внедрив распределитель с помощью POSIX allocaсо всеми недостатками.
Проблема при реализации строк в стеке состоит в том, что вы не можете позволить этому динамически расти (может быть, стек в то время имеет что-то большее), но вы также должны позаботиться о таких операциях, как += это может сделать строку длиннее и длиннее.
Таким образом, в конечном итоге вы заранее выделяете (как массив или как буфер, предоставленный alloca, в своем классе или в распределителе не меняет проблему) количество байтов, которое вы будете в основном тратить впустую либо не заполняя их все, либо не используя их, если строка выросла слишком сильно и требует динамичности.
Вероятно, существует компромисс между процессом обмена данными между памятью и кэш-памятью (обычно выполняется с 128 байтами или 4 КБ), но он сильно зависит от аппаратного обеспечения, поэтому сложность, которую можно себе позволить, скорее всего не окупится.
Более доступным решением может быть распределитель, который все еще выделяет в куче, но имеет возможность сохранять и повторно использовать возвращенные блоки (до определенного предела), уменьшая необходимость запрашивать систему для выделения / освобождения.
Но производительность, в этом случае, не обязательно выиграет, если базовая система уже реализует new/delete таким образом.
Отличной отправной точкой является строковый класс на основе политики Александреску, описанный в этой статье доктора Доббса. Он включает в себя политику единого входа, которая в основном делает то, что вы хотите (поиск на странице SmallStringOpt), и его легко изменить, если / как вы считаете необходимым. Это предшествует C++11, так что у вас тоже все хорошо.
LLVM ADT имеет класс SmallString. Он также имеет SmallVector и много других полезных занятий.
В то время как текущая кодовая база LLVM движется в сторону использования C++11, (не очень) старые версии LLVM поддерживают C++03.
Это легко, написать распределитель стека, вот пример:
https://codereview.stackexchange.com/questions/31528/a-working-stack-allocator
С помощью распределителей вы можете так же легко выделить, например, из отображенного в памяти файла, то есть с диска, или из статического массива chars.
Думаю, я бы использовал комбинацию VLA, определенных для реализации, и стандартных алгоритмов.
Это рабочий код, но НЕ РЕКОМЕНДУЕМЫЙ СПОСОБ.
Этот код имеет много следов, чтобы показать, что он делает. Он не проверяет, что размер запроса на выделение не превышает буфер. Вы можете это проверить при необходимости. Обратите внимание, что std::basic_string пытается выделить больше, чем необходимо.
#include <string>
#include <iostream>
template<typename T, size_t S>
class fixed_allocator
{
typedef std::allocator<T> _base;
std::ostream& trace() const { return std::cerr << "TRACE fixed_allocator " << (void*)this ; }
public:
typedef typename _base::value_type value_type;
typedef typename _base::pointer pointer;
typedef typename _base::const_pointer const_pointer;
typedef typename _base::reference reference;
typedef typename _base::const_reference const_reference;
typedef typename _base::size_type size_type;
typedef typename _base::difference_type difference_type;
template<class C> struct rebind {
typedef fixed_allocator<C, S*sizeof(C)/sizeof(T)> other;
};
T* buffer_;
fixed_allocator(T* b) : buffer_(b) { trace() << "ctor: p=" << (void*)b << std::endl; }
fixed_allocator() : buffer_(0) { trace() << "ctor: NULL" << std::endl; };
fixed_allocator(const fixed_allocator &that) : buffer_(that.buffer_) { trace() << "ctor: copy " << (void*)buffer_ << " from " << (void*) &that << std::endl; };
pointer allocate(size_type n, std::allocator<void>::const_pointer hint=0) {
trace() << "allocating on stack " << n << " bytes" << std::endl;
return buffer_;
}
bool operator==(const fixed_allocator& that) const { return that.buffer_ == buffer_; }
void deallocate(pointer p, size_type n) {/*do nothing*/}
size_type max_size() const throw() { return S; }
};
int main()
{
char buffer_[256];
fixed_allocator<char, 256> ator(buffer_);
std::basic_string<char, std::char_traits<char>, fixed_allocator<char, 256> > str(ator);
str.assign("ipsum lorem");
std::cout << "String: '" << str << "' length " << str.size() << std::endl;
std::cout << " has 'l' at " << str.find("l") << std::endl;
str.append(" dolor sit amet");
std::cout << "String: '" << str << "' length " << str.size() << std::endl;
str.insert(0, "I say, ");
std::cout << "String: '" << str << "' length " << str.size() << std::endl;
str.insert(7, "again and again and again, ");
std::cout << "String: '" << str << "' length " << str.size() << std::endl;
str.append(": again and again and again, ");
std::cout << "String: '" << str << "' length " << str.size() << std::endl;
return 0;
}
Этот код был протестирован на GCC и LLVM и работает как ожидалось (или неожиданно).
Синтаксис громоздкий. Невозможно извлечь из basic_string и встроить буфер. Гораздо лучший способ - создать небольшой специализированный класс buffer_string с необходимым подмножеством интерфейса basic_string.