Strings in game engines

Historically, the need for strings and their use in game engines was quite limited, except, perhaps, for resource localization, where there was a need for full support for something different from the ASCII character set. But, if desired, even these resources were managed by developers to pack into the available 200 elements of the ASCII set, and given that the game is usually launched only in one locale, there was no need for conversion. But there are also differences from the standard, thanks to Sony's efforts, almost from the beginning of the 2000s, even before the 20th standard, several models of character literals were available to game developers. Standard ASCII on PS1 and partial support for Unicode (ISO 10646), with the release of the SDK for the second console, support for UTF-16 and UTF-32 was added, and after the release of the PS3, support for UTF-8 was added.

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 Strings (NTBS)

Any null-terminated byte sequence (NTBS), which is a string of non-zero bytes and a terminating null character (the character literal '\0').

NTBS length — is the number of elements preceding the terminating null character. An empty NTBS has length zero.

String literal — is a sequence of characters surrounded by double quotes (” “).

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

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

In C/C++, single quotes (') are used to denote character literals. Single quotes (' ') cannot be used to represent strings, but early Sony SDKs allowed strings to be placed in the same way, with the '`' ('gravis' or 'backtick') character performing the same role. In this case, the compiler placed these strings closer to the beginning of “.rodata” if this was transferred to a modern exe, which had certain peculiarities when used.

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

C-strings and string literals

What is the difference between the following two string definitions? (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"

The first output message will show 17, which is the number of characters in the string (including the null character). The second message will show the size of the pointer. The above lines are visually identical, but:

1. For message memory is allocated on the stack at runtime. From the compiler's point of view, it is an array of bytes that is filled from a string literal. This data can be modified without problems.

2. For msg_ptr the stack only stores the address of the string literal, which is stored in the segment .rodataand copying of the string literal is not performed. This data usually cannot be changed, but it is possible if desired.

3. The first feature of those lines with grav was that identical lines were “combined” to save memory. The second feature was the ability to write to this section, which many developers used, for example, to transfer data bypassing standard save mechanisms within one game session.

The valiant company Nintendo decided to continue the glorious work of Sony, in terms of throwing tasks to developers, and in the latest SDK (since 2018) rolled out its implementation of strings based on a separate memory pool in the system. According to benchmarks, it works faster, but I would not say that it is popular.

C String Standard Library

Typically vendor SDKs provide a library for string manipulation. <string.h>optimized for a specific console model, which contains auxiliary functions like strcpy/strlen. Well, everyone except Sony. Before switching to clang, these functions were not included in the SDK delivery. But most developers did not notice this, because game engines already had self-written functions for working with strings. Microsoft, by the way, did not suffer from such a careless attitude and everything was in place from the very first SDKs for 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

All of these functions rely on the passed pointer pointing to a well-formed null-terminated string, and so far the behavior of these functions is undefined if the pointer points to something other than NTBS. Sony had some attempts to push strings that started and ended with a special byte sequence, and these blocks were outside the data block, but they didn't go beyond SDK versions 4 and 5, and have now been removed altogether. The reason for such refinements was the console's security, and the subsequent hacks in PS3 Fat And PS3 Slim.

Application area:
the broadest, any software that does not require special capabilities for working with strings. In game engines in its pure form it is not widely used due to the verbosity of the supporting code, security issues and portability issues between platforms.

C++ strings

The C++ standard library supports a header file <string>. Basic type std::string can be considered as a variable-size character array and contains functions for handling the most common operations – initialization from string literals, concatenation, searching, etc., which, however, does not make parsing strings any easier than using C-strings, but still removes most of the work from the average programmer. Adding, however, other problems and tasks to him, but more on that later.

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 cannot be used directly where required const char*because the data field is not necessarily located as the first member of the class and cannot be referenced. And many (if not all) SDK utilities, tools and interfaces prefer C-APIs that require conversion std::string V const char*. C-API here is also not chosen for a good life, the internal implementation of ABI for classes may differ not only between vendors and compilers, but also within even minor versions of the compiler for the console, as Nintendo likes to do, periodically breaking backward compatibility between SDKs. And therefore, in one bundle there may be several binaries, compiled for different targets, because the user is not obliged to update the console to the latest firmware, but can sit on the previous stable firmware.

U std::string there is a method .c_str()which returns a pointer to an internal C-style string (const char*). Besides, std::stringlike most container types, allows access to internal data via the method .data() or a standard library function std::data().

Application area:
They are used very limitedly, relying more on their own solutions and algorithms for working with strings, and also due to dynamic memory allocation.

Memory management

By default std::string uses the default allocator, which uses ::new And ::delete to allocate memory on the heap where the actual zero-terminated (NTBS) data is stored.

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 according to the standard contains the main parts:

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

Specific implementations in the SDK are completely different, supporting an internal buffer or minimally simple, with a dedicated pool for strings or in shared memory, it all depends on the vendor. This is probably the main reason why most engines prefer to have their own cross-platform classes for working with strings.

Short String Optimization (SSO)

Modern compilers (e.g. Clang) support a string-specific optimization called Short-String Optimization (SSO). A string class can contain a control part, and for some implementations, in addition to a pointer to the data and the size, for example, there can also be a CRC and a pointer to a pool or buffer, which also take up some memory.

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

And for small strings, the volume of this control part exceeds the payload in the form of data, which, from the point of view of performance and memory consumption, greatly reduces the benefits of using std::string. To improve memory usage and avoid unnecessary allocations when the string contains fewer characters than the control part, the compiler may (the keyword may, because it very much depends on the optimization modes enabled) store the string in the stack space allocated for the control part, instead of allocating memory on the heap.

C++17 std::string_view

C++17 added a new feature to work with strings in the form std::string_viewwhich describes a string-like object, and can for example refer to a continuous sequence of objects similar to char. Typical implementation std::string_view contains only two members: a pointer to the character type and a size. And while this doesn't solve the NTBS problem of strings, std::string_view C++17 added a safer alternative to C-style strings.

template<class _CharT, 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 more than a good candidate for possible refactoring of legacy code (where appropriate), replacing type parameters const char* And const std::string& on std::string_viewbut the problems inherent to NTBS have not gone away, and a couple of new ones have been added:

Application area:
Often used to reduce overhead and simplify work with strings, but if you have a developed code base of your own solutions, priority still goes to engine classes.

string lifetime management

First, the developer is responsible for ensuring that std::string_view did not survive the array of characters it refers to, it is still the same pointer, albeit in a beautiful wrapper. It does not take much effort to make such a mistake, but in well-written code it should not happen (godbolt). On consoles, and not only, like any other bugs with dangling pointers, this error is unlikely to be detected during execution and can lead to hard-to-detect bugs. If the memory has not been taken for another object, then the string may still be located there and output, or it may be output partially, in general there are a lot of options.

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

The second mistake, unlike string::data() and string literals, string_view::data() may return a pointer to a buffer that is not null-terminated, such as a substring. Therefore, passing data() into a function that only accepts const charT* and expects a null-terminated string will be an error. std::string_view does not guarantee at all that it points to a null-terminated (NTBS) string, or to a string at all:

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

The attitude towards memory usage by strings starts to change for the worse when you suddenly decide to port a game/engine to a console or mobile platform where memory is not unlimited, and it turns out that OOM is quite real, and it occurs much earlier than you expected, even if the total memory available is still 200 megabytes. Then you start to figure out where the memory went, why it is all in a small hole, and why with 200 MB available we can't find space for a kilobyte string. This is where inplace strings, which, although they have the disadvantage of not using the entire buffer, are perfectly placed on the stack, do not allocate dynamic memory when used, and have a predictable running time, because they are almost always located in the cache. The implementation is trivially simple, and in fact it is just a convenient wrapper over an array of characters. If anyone is interested in the full implementation, you can take a look hereor look for a more beautiful one on github, there are plenty of them there

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

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

Or you can play with a static allocator and leave the interface to the string class from the standard library. The main problem with this and other classes will be the need to pass them through the used class interfaces and function signatures, which is not always convenient and not always possible. Another advantage of such strings is that their contents remain on the stack even in minidumps, and this is very helpful when debugging, while regular strings on the heap only hold a pointer.

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

Application area:
Probably the widest of all the presented string classes. Almost any string inclusion can be replaced with work with this type, which only benefits the code. The only exception is logs, due to their large volume of text.

Short Live String

When you have your own memory manager in the engine and the ability to control the allocation process, you will find that most string allocations, if you have not yet converted them to Sized String or Hybrid String, live no longer than a couple of frames, or even have a lifetime within one frame. The problem with such strings is that short-lived allocations leak memory, increasing the already considerable time it takes to find space for data. This can be solved in two basically similar ways, the first is to create a separate buffer for such strings, due to its nature it will most likely have space for a new string, and if the space is over, you can create a second buffer. An important feature of this approach is reducing fragmentation of the main memory and transferring these problems to a controlled area.

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

Application area:
Various algorithms and engine parts that need dynamic allocation, but tying them to a standard memory manager is expensive or impossible.

One[N] Frame String

And the second more radical method. The mechanism of ultra-fast row allocation stands apart, which is used, for example, to work with rows in the renderer. Yes, they are sometimes needed there too, but even the fastest allocators do not always cope. The essence of this mechanism is that the rows are placed in a special buffer that is cleared at the end of the frame or every N frames, such an allocator can only allocate memory, and is implemented by simply shifting the pointer in the buffer to the requested size. The absence of overhead costs for block search and release makes it a winner among other algorithms, but the scope of application is very limited.

Application area:
Usually it's rendering, shader properties and working with resources. Basically, everything that should load quickly, and the results of intermediate work are of no interest to anyone.

Pool String

A more general implementation of the idea to get rid of random memory allocation when using strings, or at least make it more predictable and controllable, is the use of string pools, which can be implemented, again, through overloading the allocator. The advantages of this approach I described above are a reduction in fragmentation of the main memory and control over the process of allocations and use of strings. But such pools are also subject to fragmentation, although to a lesser extent. A further development of this mechanism was the use of slab or arena allocators that are least susceptible to fragmentation. Such Arena Pool Strings allocate space for a string in uniform chunks, for example 64 bytes, even if the string takes up only 2. The screenshot shows an example of filling an arena, with 32-byte blocks. The probability of placing a new string after deleting a “blue” segment, in the same place, is much higher than if it occupied only the requested amount of memory.

The advantage of this approach is that the larger the block, the less external fragmentation of the pool, and taking into account short-lived rows, the return of blocks of the same size. Another advantage of row pools is the ability to make them thread localwhere the logic of the work allows it, for example for the same renderer or sound engine, further decoupling them from the main thread and improving the work of the threads.

Application area:
Working with strings in streams, parsing configs, where it is important to depend as little as possible on standard memory allocation mechanisms.

Hybrid String

A compromise between fixed-size and regular strings, such strings use a hybrid (pmr) allocator that switches to dynamic memory if the requested size exceeds the internal buffer size. Justified when using structures with a known approximate string size, such as file system names or resource names. File names will not contain very short strings, and are usually well predictable in size. So most resource file names do not exceed 160 characters, and are not less than 70, which gives us a possible loss on empty characters of no more than 15% when using a 128-byte buffer (The data was obtained for resource names in the Metro Exodus project).

Shared String

Another feature of game engines is the use of repeated resource names: animations, tags, property names and everything similar. Using any of the above strings to describe such structures is simply a waste of memory. Ten, a hundred or even a thousand copies of the “velocity” tag, which are used in hundreds of objects, is unlikely to please anyone. This task, known as string interningare decided not only by game developers, but also by compilers, platforms and programming languages. And although such a line is usually not the largest memory block size, the number of copies they require for their work already allocates them in the memory tracker. In the case of shared string memory is allocated for the string only when it is re-allocated, allowing multiple objects to point to the same string of characters. And if one of the variables changes its contents, a new string is created.

A similar optimization also exists in languages ​​with garbage collection in the form of an immutable object, and assignment a=b does not create a new string, but changes the reference counter to this string. Another positive aspect of using such strings is the simplified comparison of strings, when we can rely on some feature inside the string, rather than calling element-by-element comparison. The shared string mechanism uniquely identifies identical strings, the simplest implementation can be see here

class string_shared {
   shared_value* _p;
};

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

and then such code will no longer look like a profiler's dream (tags are strings), only comparisons of ints occur here, not strings.

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);
    ....
}

Application area:
Properties, tags, markers, etc., everything that is important for a person to see in the form of understandable text, and it is important for the engine that this text is unique. Not suitable for logs, and various generated strings like “Object%X_Property%Y_%Z”.

Identifiers

Further development of the mechanism shared string are string identifiers, the same animation tags do not necessarily have to have a name. The tag name is a convenient, well-perceived label of a resource or property, but for a game engine there is no significant difference between the strings “animation_tag” and the number 1 is not, the main thing is that they have a unique representation within the project. And if at the initialization stage of the engine or game, such a variable takes on some unique value, then the methods of its use in the game will not change in any way, and in those places where there was a comparison of strings or other features, there will simply be a comparison of numbers. This becomes especially noticeable in the release assembly, when such metadata is additionally encrypted or completely removed from the build.

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

string_key animation_tag{1, "animation_tag"};

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

Application area:
Markers of resources, object types, classes and everything that can be generated at compile time or read from configs in advance.

Simd Strings

But even these optimizations do not always help, then refinements in the form of sse adapted strings and algorithms for working with them come to the rescue. Description of levels, objects, all configs in most cases are in the form of text, for example lua/js/per tables. The operation of parsing 108 MB of lua level on regular strings took about 2 minutes of time, on a not very weak processor. Typical functions process strings character by character, which leads to too many branches and data dependencies, while ignoring 80% of the power of modern processors. You can use SIMD instructions to speed up some operations that are often used when parsing files, for example strstr And strchr. Just for example, the speed of searching for a substring in a string, the example is of course synthetic, you need to look at and profile real cases in the code.

Application area:
Mainly parsing configs and working in hot functions, like auto-generation of shaders.

Conclusion

That's probably all I wanted to tell you about the specifics of using lines.

.

The C++ standard library supports a flexible and rich class for working with strings. Unfortunately, std::string Not suitable for game engines and game development due to the need to manage dynamic memory.

Optimizing short strings allows safe handling of short strings when used carefully. However, mechanisms that prevent heap usage have many advantages that have long been widely tested in game engines.

I hope that in the future someone from the committee will have the courage to push something like this into the standard, in any case, a move in the directionstd::string_view And std::pmr::string showed that it is possible.