Строки в геймдеве довольно больная тема, некоторые люди используют их как будто это обычный прикладной софт, другие стараются оптимизировать выполнение, третьи никаких сил не прилагают и плывут по течению.
Давайте разберёмся в чём отличительная черта использования строк (текста в целом) в геймдеве ? Назову несколько предположений (теорий подтверждённых на практике).
1) Строки нужны только для интерфейса и общения с другими модулями (сервером, библиотеками и тд), строки не нужны для имен файлов, имен ресурсов, как имен игровых объектов
почему так ? Потому что любое имя файла, ресурса, объекта и тд можно представить в виде цифрового индекса, например просто занеся имена в табличку и записать вместо имени индекс.
Такой подход вполне работает в data-driven дизайне, игра состоит из движка, ресурсов и скриптов, мы эти ресурсы и скрипты "готовим" простой заменой текстовых идентификаторов на цифровые, а потом только уже отдаём их движку.
В code-driven подходе (большинство инди движков, даже блиц3д) такой подход вводится более болезненно, но вполне реально, например вместо :
Код:
Model * model = new Model("test.3ds");
пишем
Код:
#define MODEL_TEST 1
Model * model = new Model(MODEL_TEST);
2) Исходя из первого пункта можно вывести аксиому : мы всегда знаем размер нужных нам строк. И действительно, можно ввести искусственные ограничения на размер имени игрока, на текст новостей из интернета, на имя уровня, на что угодно.
Так, теперь у нас остались строки в интерфейсе и общении с другими системами. Давайте рассмотрим архитектурный подход std::string.
std::string находится в STL и является наиболее доступным для программиста C++ контейнером строк, отличительной чертой контейнеров в целом является принцип contain - они сами содержат данные которыми оперируют, те если рассматривать их со стороны модели MVC то это модель и отображение в одном лице, хотя часть контролёров выносится наружу (итераторы снаружи, всякие вставки-удаления в этом же классе).
То что std::string является контейнером очень удобно для прикладного программного обеспечения, мы можем передавать\получать строку и всегда будем иметь возможность оперировать ей как хотим, за это мы расплачиваемся постоянными аллокациями и долгим копированием, к примеру, без применения некоторых техник внутри контейнеров, следующий код довольно медленный :
Код:
std::string foo()
{
return "abc";
}
И действительно, в данном случае нужно будет выделить кусок памяти, скопировать туда строку и тд.
Как это всё можно сделать куда вкуснее (и быстрее) ? Для этого нужно разложить по полочкам каждую архитектурную и идеологическую составляющую std::string (как и прочего подобного контейнера строк).
Начнём с того что контейнер по-сути является владельцем данных которых он хранит, из-за этого получается что когда вы хотите скопировать данные то получаете новый контейнер. Давайте подумаем какие могут быть владельцы в принципе :
1) код который сам себе резервирует место в памяти и потом сам его использует
2) код который получает данные извне, и сохраняет их для последующей модификации
3) сам бинарный код, когда вы пишете const char * foo = "123"; то "123" располагается в памяти вашей программы (откройте exe файл и проверьте)
А что же выпало из этого списка ? выпал вариант когда код получает данные, модифицирует их и возвращает результат.
Вы сейчас скажете что это просто передача по-ссылке и её можно так же применять к std::string, да, вы правы, статья называется "готовим вкуснее", а не "становимся вегетарианцами", те, я описываю механизм более простого управления владением строк, а не полной замены догмы.
И так, значит мы пришли к тому что у нас будет контейнер который является владельцем строк и он должен уметь проводить эмиссию строк.
Для простоты добавим еще одну аксиому : нам не нужно освобождать уже выделенные строки из контейнера (выпущенные деньги назад не отбираем), на первый взгляд это глупо, но если подумать это действительно можно обойти (если интересно - расскажу позже).
Представим примерно как будет выглядеть наш владелец строк :
Код:
class stringContainer
{
public:
void Reserve(size_t size); // резервирует пул размером size байт
void Clear(); // очищает весь пул
string Allocate(size_t size); // аллоцирует строку размером size байт
string Clone(const string & string); // клонирует строку и возращает клон
size_t GetPoolSize() const; // размер пула
size_t GetSize() const; // количество выделенных байт
protected:
...
};
Теперь подумаем что же является собственно строкой ? Владелец у строки уже есть, и собственно строкой становится только указатель на владельца и смещение в нём (для простоты - вместо смещения используем указатель на саму C строку). Вспомним чуть раньше, владельцем может быть не только наш контейнер, но так же и сам бинарник, для поддержки этого предлагаю ввести два указателя - один для чтения\записи, другой только для чтения, что позволит нам сематически корректно поддерживать передачу и работу со строковыми литералами.
Код:
class string
{
public:
string(const char * stringLiteral = NULL)
:rawReadOnly(stringLiteral), raw(NULL), owner(NULL), size(0), length(0)
{
size = UTF8GetSize(rawReadOnly);
length = UTF8GetLength(rawReadOnly);
}
string(char * stringData, stringContainer * setOwner, size_t setSize, size_t setLength)
:raw(stringData), rawReadOnly(stringData), owner(setOwner), size(setSize), length(setLength)
{
}
string(const string & other)
:rawReadOnly(other.rawReadOnly), raw(other.raw), owner(other.owner), size(other.size)
{
}
const char * c_str() const {return rawReadOnly;}
char * GetRaw() const {return raw;}
const char * GetRawRO() const {return rawReadOnly;}
void SetSize(size_t setSize) {size = setSize;}
size_t GetSize() const {return size;}
void SetLength(size_t setLength) {length = setLength;}
size_t GetLength() const {return length;}
bool IsEqual(const string & other) const
{
if(rawReadOnly == other.rawReadOnly)
{
assert(owner == other.owner);
return true;
}
else if(rawReadOnly && other.rawReadOnly)
return !strcmp(rawReadOnly, other.rawReadOnly);
else if(!(rawReadOnly || other.rawReadOnly))
return true;
else
return false;
}
bool operator == (const string & other) const {return IsEqual(other);}
bool operator != (const string & other) const {return !IsEqual(other);}
protected:
const char * rawReadOnly; // указатель на read-only строку
char * raw; // указатель на write-read строку
stringContainer * owner;
size_t size; // размер в байтах
size_t length; // размер в буквах (поддержка utf-8)
};
Получаем что наш класс строки, который мы используем везде где нам нужно, совершенно не содержит данных строки, он стал очень легковесным и посмотрите на этот конструктор копирования ! теперь мы можем довольно быстро обмениваться строками, сохранять их к себе, и становится владельцами когда захотим, плюс обеспечивается поддержка строковых литералов из коробки, что лишает нас кучи проблем и не нужных аллокаций.
Всю малину портит то что нам нужно конструировать и форматировать строки. Привыкшие писать :
Код:
std::string a = "1";
std::string b = "2";
std::string c = a + b;
довольно сильно обламываются. Тут мы начинаем немного кусать кактус и вспоминаем что где-то это уже видели, да, такого к примеру не было с C строками это раз, такой функционал предоставляет std::stringstream и прочие. Как можно приготовить этот кактус вкусно ? нам понадобится написать класс который форматирует строку, и пишет результат в буферную строку, для упрощения форматирования воспользуемся sprintf и производными.
Код:
class stringConcate
{
public:
stringConcate()
:freePosition(0)
{
}
stringConcate(const string & buffer)
:buf(buffer), freePosition(0)
{
}
void SetBuffer(const string & buffer)
{
buf = buffer;
freePosition = 0;
}
stringConcate & Add(const char * formatStr, ...)
{
assert((freePosition + 1) < buf.GetSize());
va_list args;
va_start(args, formatStr);
freePosition += vsprintf(buf.GetRaw() + freePosition, formatStr, args);
va_end(args);
assert((freePosition + 1) <= buf.GetSize());
return *this;
}
string BakeToString()
{
buf.GetRaw()[freePosition++] = '\0';
string result(buf);
result.SetSize(freePosition);
result.SetLength(UTF8GetLength(result.GetRawRO()));
freePosition = 0;
return result;
}
private:
stringConcate(const stringConcate & other) {}
protected:
string buf;
size_t freePosition;
};
Вроде как всё не так уж и плохо ? А позже кажется что даже и хорошо ! код становится более детерминированным, и не делает какой либо скрытой фигни, пример использования :
Код:
stringContainer container;
container.Reserve(16);
stringConcate concate(container.Allocate(16));
string a = "1";
string b = "2";
string c = concate.Add("%s%s", a.c_str(), b.c_str()).Add("temp").BakeToString(); // привычное нам C-форматирование
Add можно вызывать сколько хочется раз, а результат потом получать с помощью BakeToString.
У всего этого есть один нюанс, бесплатного сыра не бывает, но бывает магия, пример нюанса :
Код:
stringContainer container;
container.Reserve(16);
stringConcate concate(container.Allocate(16));
string a = concate.Add("1").BakeToString();
string b = concate.Add("2").BakeToString();
// вообще вот чисто технически, буфер перезаписан, строка a уже не валидна для чтения, ибо этот код не стал её владельцем
bool c = (a == b); // вернёт true, смотрите в реализацию IsEqual
Если вы внимательно следили, то поймете что это ошибка by-design ! Давайте подумаем как это можно обойти не выкинув при этом всё, скажем первое что бросается на ум - хранить с поинтером хеш строки, вполне разумная идея в общем-то, даже потом можем сравнивать хеши строк при различии указателей, только вот ... одинаковые строки с разными указателями бывают ОЧЕНЬ РЕДКО, конечно синтетические тесты могут быть любыми, но часто ли вы такое видели в реальной игре ? Перед нами стоит проблема того что мы имеем разные строки с одинаковым поинтером.
А теперь магия ! :crazy: :cool:
сверх быстрая хеш-функция для нашего случая :
Код:
size_t hash(const char * str)
{
static size_t i = 0;
assert(i < SIZE_T_MAX);
return i++;
}
Немного дзена, и мы начинаем понимать всю суть оптимизации. Поскольку 4 млрда хешей на сессию (для 32 бит) это немного самонадеянно (прям как 1 гиг памяти алочить), то давайте сделаем хеш для каждого экземпляра string, это не космические технологии, дзен нам позволяет, и это крутой trade-off скорости на ассерт через 100-200 лет.
Каждый BakeToString мы просто будем увеличивать внутренний хеш буфер-строки, и всё, в итоге суммируя всё представленное выше получаем такую заготовку :
Код:
size_t UTF8GetSize(const char * str) { return strlen(str); }
size_t UTF8GetLength(const char * str) { ... }
class stringContainer
{
public:
void Reserve(size_t size); // резервирует пул размером size байт
void Clear(); // очищает весь пул
string Allocate(size_t size); // аллоцирует строку размером size байт
string Clone(const string & string); // клонирует строку и возращает клон
size_t GetPoolSize() const; // размер пула
size_t GetSize() const; // количество выделенных байт
protected:
...
};
class string
{
public:
string(const char * stringLiteral = NULL)
:rawReadOnly(stringLiteral), raw(NULL), owner(NULL), size(0), length(0), hash(0)
{
size = UTF8GetSize(rawReadOnly);
length = UTF8GetLength(rawReadOnly);
}
string(char * stringData, stringContainer * setOwner, size_t setSize, size_t setLength)
:raw(stringData), rawReadOnly(stringData), owner(setOwner), size(setSize), length(setLength), hash(0)
{
}
string(const string & other)
:rawReadOnly(other.rawReadOnly), raw(other.raw), owner(other.owner), size(other.size), hash(other.hash)
{
}
const char * c_str() const {return rawReadOnly;}
char * GetRaw() const {return raw;}
const char * GetRawRO() const {return rawReadOnly;}
void SetSize(size_t setSize) {size = setSize;}
size_t GetSize() const {return size;}
void SetLength(size_t setLength) {length = setLength;}
size_t GetLength() const {return length;}
void PushHash() {++hash;}
size_t GetHash() const {return hash;}
bool IsEqual(const string & other) const
{
if(rawReadOnly == other.rawReadOnly)
{
assert(owner == other.owner);
return hash == other.hash;
}
else if(rawReadOnly && other.rawReadOnly)
return !strcmp(rawReadOnly, other.rawReadOnly);
else if(!(rawReadOnly || other.rawReadOnly))
return true;
else
return false;
}
bool operator == (const string & other) const {return IsEqual(other);}
bool operator != (const string & other) const {return !IsEqual(other);}
protected:
const char * rawReadOnly; // указатель на read-only строку
char * raw; // указатель на write-read строку, если не 0 то совпадает с rawReadOnly
stringContainer * owner;
size_t size; // размер в байтах
size_t length; // размер в буквах (поддержка utf-8)
size_t hash; // хеш строки, возможно сравнивать только если указатели совпадают
};
class stringConcate
{
public:
stringConcate()
:freePosition(0)
{
}
stringConcate(const string & buffer)
:buf(buffer), freePosition(0)
{
}
void SetBuffer(const string & buffer)
{
buf = buffer;
freePosition = 0;
}
stringConcate & Add(const char * formatStr, ...)
{
assert((freePosition + 1) < buf.GetSize());
va_list args;
va_start(args, formatStr);
freePosition += vsprintf(buf.GetRaw() + freePosition, formatStr, args);
va_end(args);
assert((freePosition + 1) <= buf.GetSize());
return *this;
}
string BakeToString()
{
buf.GetRaw()[freePosition++] = '\0';
buf.PushHash();
string result(buf);
result.SetSize(freePosition);
result.SetLength(UTF8GetLength(result.GetRawRO()));
freePosition = 0;
return result;
}
private:
stringConcate(const stringConcate & other) {}
protected:
string buf;
size_t freePosition;
};
class foo // класс который принимает строку, сетапит по ней данные, но не владеет строкой
{
public:
void SetString(const string & newString)
{
if(set != newString)
{
set = newString;
SetupData(set);
}
}
protected:
string set;
void SetupData(const string & str)
{
...
}
};
void test()
{
stringContainer container;
container.Reserve(16);
stringConcate concate(container.Allocate(16));
foo test;
string a = concate.Add("1").BakeToString();
test.SetString(a);
string b = concate.Add("2").BakeToString();
test.SetString(b); // вызовется SetupData, хотя foo::set уже не валидный
bool c = (a == b); // вернёт false
}
class foo2 // а этот класс уже владеет строкой
{
public:
foo2()
{
container.Reserve(256);
}
void Setup(const string & name)
{
ownName = container.Clone(name);
}
protected:
stringContainer container;
string ownName;
};
void test2()
{
foo2 a;
a.Setup("test_test");
}
Вот и всё, резюмируя : мы получили довольно дешевый, быстрый, хорошо управляемый подход в реализации строк, требующий немного сноровки и дзена.
