Строки в игровых движках

Исторически потребность в строках и их использование в игровых движках было довольно ограниченое, кроме, разве что, локализации ресурсов, где была необходимость полноценной поддержки чего-то отличного от набора ASCII символов. Но, при желании, даже эти ресуры разработчики умудрялись упаковать в доступные 200 элементов набора ASCII, а учитывая что игра обычно запускается только в одной локали, то никаких потребностей в конвертации не было. Но есть тут и отличия от стандарта, стараниями Sony практически с начала нулевых, еще до 20 стандарта разработчикам игр были доступны несколько моделей символьных литералов. Стандартый ASCII на PS1 и частичная поддержка Unicode (ISO 10646), с выпуском сдк для второй плойки добавили поддержку UTF-16 и UTF-32, а после выхода PS3 добавили поддержку UTF-8.

int main()
{
  char     c1{ 'a' };       // 'narrow' char
  char8_t  c2{ u8'a' };     // UTF-8  - (PS3 and later)
  char16_t c3{ u'貓' };     // UTF-16 - (PS2)
  char32_t c4{ U'????' };   // UTF-32 - (PS2 limited)
  wchar_t  c5{ L'β' };      // wide char - wchar_t
}

C-Style строки (NTBS)

Любая байтовая последовательность с завершающим нулем (NTBS), которая представляет собой цепочку ненулевых байтов и завершающий нулевой символ (символьным литералом '\0').

Длина NTBS — это количество элементов, предшествующих завершающему нулевому символу. Пустая NTBS имеет длину ноль.

Строковый литерал — это последовательность символов, окруженная двойными кавычками (" ").

int main(void)
{
  char string_literal[] = "Hello World";     

  std::cout << sizeof(string_literal) << '\n';  // 12
  std::cout << strlen(string_literal) << '\n';  // 11
}

В C/C++ одиночные кавычки (') используются для обозначения символьных литералов. Одиночные кавычки (' ') не могут использоваться для представления строк, но первые SDK от Sony позволяли таким же образом размещать и строки, эту же роль выполнял символ '`' ("гравис" или "backtick"), обратная кавычка. В этом случае компилятор размещал эти строки ближе к началу ".rodata", если это переносить на современный exe, что имело определенные особенности при использовании.

char string_literal[] = `Hello World`;  // тоже строка, расположенная в начале rodata
char another_string_literal[] = 'Hello World'; // так тоже можно было

C-строки и строковые литералы

В чем разница между следующими двумя определениями строк? (godbolt)

int main()
{
   char message[] = "this is a string";
   printf("%u\n", sizeof(message));

   const char *msg_ptr = "this is a string";
   printf("%u", sizeof(msg_ptr));
}

Скрытый текст

main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 48
        mov     rax, qword ptr [rip + .L__const.main.message]
        mov     qword ptr [rbp - 32], rax
        mov     rax, qword ptr [rip + .L__const.main.message+8]
        mov     qword ptr [rbp - 24], rax
        mov     al, byte ptr [rip + .L__const.main.message+16]
        mov     byte ptr [rbp - 16], al
        lea     rdi, [rip + .L.str]
        mov     esi, 17
        mov     al, 0
        call    printf@PLT
        lea     rax, [rip + .L.str.1]
        mov     qword ptr [rbp - 40], rax
        lea     rdi, [rip + .L.str.2]
        mov     esi, 8
        mov     al, 0
        call    printf@PLT
        xor     eax, eax
        add     rsp, 48
        pop     rbp
        ret

.L__const.main.message:
        .asciz  "this is a string"

.L.str:
        .asciz  "%u\n"

.L.str.1:
        .asciz  "this is a string"

.L.str.2:
        .asciz  "%u"

Первое сообщение на выходе покажет 17, то есть количество символов в строке (включая нулевой символ). Второе сообщение покажет размер указателя. Приведенные выше строки визуально идентичны, но:

1. Для message память выделяется на стеке во время выполнения. С точки зрения компилятора это массив байтов, который заполняется из строкового литерала. Эти данные можно изменить без проблем.

2. Для msg_ptr на стеке хранится только адрес строкового литерала, который хранится в сегменте .rodata, и копирование строкового литерала не выполняется. Эти данные обычно поменять нельзя, но при желании тоже можно.

3. Первой особенностью вот тех строк с грависом было, что одинаковые строки "объединялись" для экономии памяти. Второй особенностью была возможность записи в эту секцию, чем многие разработчики пользовались например для передачи данных в обход стандартных механизмов сейва в рамках одной игровой сессии.

Доблестная компания Nintendo решила продолжить славное дело Sony, в плане подкидывания задачек разработчикам, и в последних сдк (с 2018 года) выкатила свою реализацию строк на базе отдельного пула памяти в системе. По бенчмаркам работает быстрее, но не сказал бы, чтобы она пользовалась популярностью.

C String Standard Library

Обычно SDK вендоров предоставляет библиотеку для манипуляций со строками <string.h>, оптимизированную под конкретную модель консоли, которая содержит вспомогательные функции вроде strcpy/strlen. Ну все кроме Sony. До перехода на clang, этих функций в поставке SDK не было. Но большинство разработчиков этого не замечали, потому что игровые движки уже имели самописные функции для работы со строками. Майкрософт, кстати таким наплевательским отношением не страдал и все было на месте с самых первых SDK для xbox.

copying strings         : strcpy, strncpy, strdup
concatenating strings   : strcat, strncat, strappend
comparing strings       : strcmp, strncmp
parsing strings         : strcspn, strstr, strchr, strchrrev, strupper...
tokenize                : strtok, strsplit
length                  : strlen, strempty

Все эти функции полагаются на то, что переданный указатель указывает на правильно сформированную строку с завершающим нулем, до сих пор поведение этих функций неопределено, если указатель на чтото отличное от NTBS. У Sony были попытки продвинуть строки которые начинались и заканчивались специальной последовательностью байт, причем эти блоки были за пределами блока данных, но дальше 4 и 5 версий СДК они не пошли, а сейчас вообще удалены. Причиной таких изысков была безопасность консоли, и последовавшие друг за другом взломы в PS3 Fat и PS3 Slim.

Область применения:
самая широкая, любой софт, который не требует специальных возможность для работы со строками. В игровых движках в чистом виде мало распространен в силу многословности обуслуживающего кода, проблем с безопасностью и проблем с переносимостью между платформами.

C++ строки

Стандартная библиотека C++ поддерживает заголовочный файл <string>. Базовый тип std::string можно рассматривать как массив символов переменного размера и содержит функции для работы с наиболее распространенными операцими —инициализацию из строковых литералов, конкатенацию, поиск и т. д., что однако не делает разбор строк более простым по сравнению с использованием C-cтрок, но все же снимает бОльшую часть работы с рядового программиста. Добавляя ему, впрочем, других проблем и задач, но об этом позже.

const std::string this_string { "This is" }; // initialise

int main() {
  std::string name = " string";  
  std::string concat_str =  this_string + name; // concatenation

  std::cout << concat_str;

  if (!this_string.empty()) {
    std::cout << '\n' << this_string.length() << '\n';
    std::cout << this_string[0] << ' ' << this_string.front() << '\n';
    std::cout << this_string[this_string.length()-1] << ' ' << concat_str.back() << '\n';
  }
}

<<<<<<
This is string
7
T T
s g

std::string не может использоваться напрямую там, где требуется const char*, потому что поле data не обязательно расположено первым членом класса и ссылаться на него нельзя. А многие (если не сказать все) сдк утилиты, тулзы и интерфейсы и предпочитают С-API, требующие преобразования std::string в const char*. C-API здесь тоже выбран не от хорошей жизни, внутренняя реализация ABI для классов, может отличаться не только между вендорами и компиляторами, но и внутри даже минорных версий компилятора для консоли, как это любит делать Nintendo, периодически ломая обратную совместимость между SDK. И поэтому в одном бандле могут лежать несколько бинарников, собранные подд разные таргеты, потому что пользователь не обязан обновлять консоль до последнего firmware, а может вполне сидеть на прошлой стабильной прошивке.

У std::string есть метод .c_str(), который возвращает указатель на внутреннюю строку в стиле C (const char*). Кроме того, std::string, как и большинство контейнерных типов, позволяет получить доступ к внутренним данным через метод .data() или стандартную функцию библиотеки std::data().

Область применения:
Применяются очень ограничено, больше полагаясь на собственные решения и алгоритмы работы со строками, а также из-за динамического выделения памяти.

Управление памятью

По умолчанию std::string использует дефолтный аллокатор, использующий ::new и ::delete для выделения памяти в куче, где хранит фактические данные с завершающим нулем (NTBS).

int main() {
    const char* this_is_ro_string = "literal string";    // stored in .rodata
    char this_is_stack_string[] = "literal string";      // stored on stack
    std::string this_is_heap_string = "Literal String";  // stored in .heap 
}

std::strings по стандарту содержит основные части:

class string {
  data -> размещается алокатором; доступно через .data()
  length -> может отсутствовать или вычисляться на лету/операциях
            доступно через .length() or .size()
  capacity -> доступный объем данных ( >= length); можно получить через .capacity()
}

Конкретные реализации в SDK совершенно разные, поддерживающие внутренний буфер или минимально простые, с выделенным пулом под строки или в общей памяти, все зависит от вендора. Это пожалуй основная причина, почему большинство движков, предпочитают иметь свои крос-платформенные классы для работы со строками.

Short String Optimisation (SSO)

Современные компиляторы (например, Clang) поддерживают специфичную для строки оптимизацию - оптимизацию коротких строк (Short-String Optimisation, SSO). Класс строки может содержать управляющую часть, а для некоторых реализаций там, помимо указателя на данные и размера, например, может лежать еще CRC и указатель на пул или буфер, которые тоже занимают некоторый объем памяти

class string {
  void *data; // 8bytes
  size_t size; // 8bytes
  size_t capacity; // 8Bytes
  size_t crc;  // 8bytes
}

И для небольших строк обьем этой управляющей части превышает полезную нагрузку в виде данных, что с точки зрения производительности и потребления памяти, сильно снижают преимущества использования std::string. Чтобы улучшить использование памяти и убрать ненужные алокации, когда строка содержит меньше символов чем управляющая часть, компилятор может (ключевое слово может, ибо это очень сильно зависит от включенных режимов оптимизации) сохранять строку в пространстве стека, выделенном для управляющей части, вместо выделения памяти в куче.

C++17 std::string_view

C++17 добавил новую возможность работы со строками в виде std::string_view, который описывает объект похожий на строку, и например может ссылаться на непрерывную последовательность объектов, похожих на char. Типичная реализация std::string_view содержит всего два члена: указатель на тип символа и размер. И хотя это не решает проблемы NTBS строк, std::string_view в C++17 добавил более безопасную альтернативу строк в стиле C.

template<class _T, class _Traits = char_traits<_CharT> >
class string_view {
public:
    typedef _CharT value_type;
    typedef size_t size_type;
    ...
private:
    const value_type* __data;
    size_type __size;
};

std::string_view более чем хороший кандидат для возможного рефакторинга легаси кода (где это уместно), заменяя параметры типа const char* и const std::string& на std::string_view, но проблемы присущие NTBS никуда не делись, и добавилась парочка новых:

Область применения:
Часто применяются для снижения накладных расходов, и упрощения работы со строками, но при наличии развитой кодовой базы своих решений приоритет всеже достается классам движка.

string lifetime management

Во-первых, разработчик несет ответственность за то, чтобы std::string_view не пережил массив символов, на который он ссылается, это все тот же поинтер, пусть и в красивой обертке. Чтобы допустить такую ошибку, не нужно особо стараться, но в хорошо написанном коде этого не должно происходить (godbolt). На консолях, и не только, как и любые другие баги с повисшими указателями, эта ошибка вряд ли будет обнаружена во время выполнения и может привести к трудновыявляемым багам. Если память не успели забрать под другой объект, то строка вполне еще может там располагаться и выводиться, а может выводиться частично, вообще вариантов масса.

using namespace std::string_literals; // operator""s
using namespace std::literals;        // operator""sv

int main() {   
  // OK: строковый литерал гдето в .rodata
  std::string_view ntbs{ "a string literal" };      
  // UB: rvalue строка алоцированая на куче временно в скопе
  std::string_view heap_string{ "a temporary string"s }; 
  // деалоцируем строку
  std::cout << "Address of heap_string: " << (void*)heap_string.data() << '\n'; 
  std::cout << "Data at heap_string: " << heap_string.data() << '\n';
}

non null-terminated strings

Вторая ошибка, в отличие от string::data() и строковых литералов, string_view::data() может вернуть указатель на буфер, который не завершается нулем, например подстрока. Поэтому передавать data() в функцию, которая принимает только const char* и ожидает строку, завершающуюся нулем, будет ошибкой. std::string_view вообще не гарантирует, что он указывает на строку с завершающим нулем (NTBS), или на строку вообще:

void sv_print(std::string_view str) {
  std::cout << str.length() << ' '<< reinterpret_cast<const void*>(str.data()) << '\n';
  std::cout << "cout: " << str << '\n';     // based on str.length()
  printf("stdout: %s\n",str.data());        // based on NUL
}

int main() {
    std::string      str_s  {"godbolt compiler explorer"}; 
    std::string_view str_sv {"godbolt compiler explorer"}; 
    char char_arr2[] = {
        'a',' ','c','h','a','r',' ','a','r','r','a','y'
        }; // Not null character terminated
   sv_print(str_s.substr(8,8));
   sv_print(str_sv.substr(8,8));
   sv_print(char_arr2);
}

<<<<<<<<<<<<<
  
8 0x7ffff4bf1550
cout: compiler
stdout: compiler

8 0x40201f
cout: compiler
stdout: compiler explorer

16 0x7ffff4bf1514
cout: a char array���
stdout: a char array���

Sized String

Отношение к использованию памяти строками начинает меняться в худшую сторону, когда вы вдруг решаете портировать игру/движок на консоль или мобильную платформу, где память не безгранична, и оказывается, что OOM вполне себе существует, а наступает гораздо раньше, чем вы предполагали, даже если суммарно памяти доступно еще мегабайт двести. Тогда вы начинаете разбираться куда подевалась память, почему она вся в мелкую дырочку, и почему при доступных 200 Мб мы не можем найти место под строку в килобайт. Тут на помощь приходят inplace строки, которые хоть и имеют недостаток в виде неполного использования буфера, зато отлично размещаются на стеке, не алоцируют динамическую память при использовании и имеют предсказуемое время работы, потому что почти всегда распололожены в кеше. Реализация до банальности простая, и фактически это просто удобная обертка над массивом символов. Если кому интересна полная реализация, можно посмотреть тут, ну или поискать на гитхабе более красивую, их там достаточно.

template <size_t _size>
class string_sz {
    using ref = bstring<_size>&;
    using const_ref = const sized_string<_size>&;

protected:
    char _data[_size];
    ...
};

Или можно поиграться со статическим алокатором и оставить интерфейс к классу строки из стандартной библиотеки. Основной проблемой этого и других классов будет необходимость прокидывать их через используемые интерфейсы классов и сигнатуры функций, что не всегда удобно и не всегда возможно. Еще один плюс таких строк, что их содержимое остается на стеке даже в минидампах, и это очень помогает при отладке, тогда как обычные строки на куче держат только указатель на данные.

template<size_t _size>
using string_sz = std::string<char, static_allocator<char, _size>>;
using string_sz64 = string_sz<64>;

Область применения:
Самая широкая наверно из всех представленных классов строк. Практически любое включение string можно заменить на работу с этим типом, отчего код только выигрывает. Исключение составляют разве что логи, из-за их большого объема текста.

Short Live String

Когда у вас в движке появляется собственный менеджер памяти и возможность контролировать процесс алокаций, то вы обнаружите, что большинство алокаций строк, если вы их еще не перевели на Sized String или Hybrid String живут не дольше пары тройки фреймов, а то и вообще имеют время жизни в пределах одного фрейма. Проблема таких строк в том, что коротко-живущие алокации дырявят память, увеличивая и без того немаленькое время поиска места под данные. Решается это двумя в принципе похожими способами, первый - это создание отдельного буфера для таких строк, за счет своей природы в нем с большой вероятностью будет место под новую строку, а если место все же закончилось, можно создать второй буфер. Важной особенностью такого подхода снижение фрагментации основной памяти и перенос этих проблем в контролируемую область.

using string_sl = std::string<char, custom_allocator<char>>;

Область применения:
Разные алгоритмы и части движка, которым нужна динамическая алокация, но завязывать их на стандартный менеджер памяти дорого или нельзя.

One[N] Frame String

И второй более кардинальный способ. Особняком стоит механизм сверхбыстрой алокации строк, который используется например для работы со строками в рендере. Да, там они тоже иногда нужны, но даже самые быстрые алокаторы не всегда справляются. Суть этого механизма в том, что строки размещаются в специальном буфере который очищается в конце фрейма или через каждые N фреймов, такой алокатор умеет только выделять память, и реализован простым смещением указателя в буфере на запрошеный размер. Отсутствие накладных расходов на поиск блока и освобождение делают его победителем среди других алгоритмов, но область применения очень ограниченная.

Область применения:
Обычно это рендер, свойства шейдеров и работа с ресурсами. Вообщем все то, что должно грузиться быстро, а результаты промежуточной работы никому не интересны.

Pool String

Более общей реализацией идеи избавиться от рандомного выделения памяти при использовании строк или, хотя бы, сделать её более предсказуемой и контролируемой, является использование пулов строк, который можно реализовать, опять же через перегрузку алокатора. Преимущества такого подхода я описал выше, это снижение фрагментации основной памяти и контролирование процесса алокаций и использования строк. Но такие пулы тоже подвержены фрагментации, хоть и в меньшей степени. Дальнейшим развитием этого механизма стало использование slab или arena алокаторов, которые меньше всего подвержены фрагментации. Такие Arena Pool String выделяют место под строку равномерными кусками, например по 64 байта, даже если строка занимает всего 2. На скриншоте пример заполнения арены, с блоками по 32 байта. Вероятность размещения новой строки после удаления "синего" сегмента, на том же месте, намного выше, чем если бы он занимал только запрошенный объем памяти.

Преимущество такого подхода будет в том, что чем больше блок, тем меньше внешняя фрагментация пула, а с учетом короткоживущих строк возврат блоков одинакового размера держит процент использования буфера примерно на одном уровне. Последующее профилирование таких пулов по размеру дает возможность перед релизом порезать их до нужных пределов, чтобы процент заполнения был в районк 90-95%. Еще одним преимуществом пулов строк, является возможность сделать их thread local, где это позволяет логика работы, например для того же рендера или звукового движка, еще больше развязав их с основным тредом и улучшив работу потоков.

Область применения:
Работа со строками в потоках, парсинг конфигов, где важно как можно меньше зависеть от стандартных механизмов выделения памяти.

Hybrid String

Компромисс между строками фиксированного размера и обычными, такие строки используют гибридный (pmr) алокатор, который переключается на динамическую память, если запрошеный размер превысил размер внутреннего буфера. Оправдан при использовании структур с заранее известным примерным размером строки, например имена в файловой системе или имена ресурсов. Имена файлов не будут содержать совсем уж короткие строки, и обычно хорошо поддаются прогнозированию размера. Так большинство имен файлов ресурсов не превышают размер 160 символов, и не меньше 70, что дает нам возможные потери на пустых символах не больше 15% при использовании буфера размер 128 байт (Данные были получены для имен ресурсов в проекте Metro Exodus).

Shared String

Еще одной особенностью игровых движков, является использование повторяющихся имен ресурсов: анимаций, тегов, имен свойств и всего похожего. Использовать для описания таких структур любого вида строк из представленных выше, значит просто впустую тратить память. Десять, сто и даже тысяча копий тега "velocity", которая используются в сотнях объектов вряд ли кому то понравится. Эту задачу, известную как string interning, решают не только разработчики игр, но и компиляторов, платформ и языков программирования. И пусть обычно такая строка — это не самый большой размер блока памяти, но множество копий, которые они требуют для своей работы, уже выделяет их в мемори трекере. В случае shared string память выделяется под строку только при новом размещении, позволяя нескольким объектам указывать на одну и ту же цепочку символов. А если одна из переменных меняет своё содержимое, создается новая строка (copy-on-write, CoW).

Подобная оптимизация существует также в языках со сборкой мусора в виде неизменного объекта, а присваивание a=b не создаёт новой строки, а изменяет счетчик ссылок на эту строку. Еще одним положительным моментом использования таких строк является упрощенное сравнение строк, когда мы можем опираться на некоторый признак внутри строки, а не вызывать поэлементное сравнение. Механизм shared string однозначно определяет одинаковые строки, простейшую реализацию можно посмотреть тут.

class string_shared {
   shared_value* _p;
};

inline bool operator==(xstring const& a, xstring const& b) {
  return a._p == b._p;
}

и тогда вот такой код уже не будет выглядеть как мечта профайлера (tag - это строки), тут происходят только сравнения интов, а не строк.

void npc::on_event				(const time_tag &tt) {
	if (tt.tag == event_step_left) {
		on_step(e_step_left);
	} else if (tt.tag == event_step_right) {
		on_step(e_step_right);
	} else if (tt.tag == event_step_left_hand) {
		on_step(e_step_left_hand);
	} else if (tt.tag == event_step_right_hand) {
		on_step(e_step_right_hand);
	} else if (tt.tag == event_jump_left) {
		on_step(e_jump_left);
	} else if (tt.tag == event_jump_right) {
		on_step(e_jump_right);
    ....
}

Область применения:
Свойства, теги, маркеры и так далее, все что важно видеть человеку в виде понятного текста, а движку важно чтобы этот текст был уникальным. Не подходят для логов, и разных генерируемых строк вида "Object%X_Property%Y_%Z".

Идентификаторы

Дальнейшим развитием механизма shared string являются строки-идентификаторы, те же теги анимаций не обязательно должны иметь имя. Имя тега - это удобная, хорошо воспринимаемая людьми метка ресурса или свойства, но для игрового движка существенного развиличия между строкой "animation_tag" и числом 1 нет, главное чтобы они имели уникальное представление в рамках проекта. И если на этапе инициализации движка или игры, такая переменная примет некоторое уникальное значение, то методы её использования в игре никак не изменятся, а в тех местах, где было сравнение строк или других признаков, будет просто сравнение чисел. Особенно это становится заметно в релизной сборки, когда такие метаданные дополнительно шифруются или вообще удаляются из билда.

struct string_key {
  int id;
#ifdef EDITOR
  const char *str;
#endif
}

string_key animation_tag{1, "animation_tag"};

if (animation.tag == animation_tag) {
  ...
}

Область применения:
Маркеры ресурсов, типов объектов, классов и всего, что может быть сгенерировано в компайл тайме или заранее прочитано из конфигов.

Simd Strings

Но и эти оптимизации не всегда помогают, тогда на помощь приходят изыски в виде sse адаптированных строк и алгоритмов работы с ними. Описание уровней, объектов, все конфиги в большинстве случаев лежат в виде текста, например lua/js/per таблиц. Операция парсинга 108-мегабайтного луашника уровня на обычных строках занимала порядка двух минут времени на не самом слабом процессоре. Типичные функции обрабатывают строки посимвольно, что приводит к слишком большому количеству ветвлений и зависимостей от данных, игнорируя при этом 80% мощи современных процессоров. Можно задействовать SIMD-инструкции для ускорения некоторых операций, которые часто используются при парсинге файлов, например strstr и strchr. Просто для примера скорость поиска подстроки в строке, пример конечно синтетический, надо смотреть и профилировать реальные случаи в коде.

strstr x86:  2.0 GB/s

string.findx86: 1.6 GB/s

boost.string.findx86: 1.3 GB/s

simd.findx86:  10.1 GB/s

Область применения:
В основном парсинг конфигов и работа в горячих функциях, вроде автогенерации шейдеров.

Заключение

На этом пожалуй всё, что я хотел рассказать про особенности применения строк

.

Стандартная библиотека C++ поддерживает гибкий и богатый класс для работы со строками. К сожалению, std::string не подходит для игровых движков и разработки игр из-за необходимости управления динамической памятью.

Оптимизация коротких строк позволяет при осторожном использовании безопасно управлять строками небольшой длины. Однако механизмы, предотвращающие использование кучи, имеют очень много преимуществ, которые давно и широко обкатаны в игровых движках.

Надеюсь, что в будущем у кого-то из комитета хватит смелости протащить что-то подобное в стандарт, в любом случае подвижки в сторонуstd::string_view и std::pmr::string показали что это возможно.