28 Fév 2023

Small String Optimization

28 Fév 2023

Small String Optimization (or Short String Optimization, SSO) is an optimization applied in the std::basic_string class template and its analogues. It allows to avoid additional dynamic memory allocations for small strings and place them inside the object itself.

To explain how the optimization works, let's consider an example of the simplest string implementation that uses characters of the char type:

class string
{
  size_t capacity;
  char *buf;
  size_t size;
  // ....
};

This inefficient string implementation stores three non-static data members: the pointer to a dynamically allocated buffer (buf), the size of the string (size), and the real size of the buffer (capacity). The latter is used to reduce the number of dynamic memory allocations when inserting a character into the buffer.

The problem is that such an implementation, even for empty strings, requires a buffer allocation and a terminal null at its beginning. This ensures that such a string can be passed without problems to functions accepting null-terminated strings (for example, strlen).

To reduce overhead, you can place characters directly inside the string object. To do this, we apply SSO and slightly modify the class:

class string
{
  size_t capacity;

  union
  {
    struct 
    {
      char *ptr;
      size_t size;
    } heapbuf;

    char stackbuf[sizeof(heapbuf)];
  };
};

In the new implementation, it is possible to place small strings inside an object in stackbuf without allocating a buffer on the heap. The number of characters stored inside the object depends on the size of the pointer and size_t. For example, on a 64-bit platform, the size of heapbuf will be 16 bytes, therefore, up to 15 characters and a terminal null can be stored inside the object. Based on the non-static capacity data member, it is determined where the characters are stored:

if the capacity exceeds the size of stackbuf, then the object manages the buffer on the heap and stores characters there;
otherwise, the characters are stored inside the object.

Many string implementations use SSO to speed up work with small strings. For example, SSO is applied in the following libraries: Microsoft STL, libstdc++, libc++, Boost, Folly.