28 Фев 2023

Small String Optimization

28 Фев 2023

Small String Optimization (или Short String Optimization, SSO) – это оптимизация, применяемая в шаблоне класса std::basic_string и его аналогах. Позволяет избегать дополнительных аллокаций динамической памяти для строк небольшого размера и размещать их внутри самого объекта.

Для пояснения принципа работы оптимизации рассмотрим пример простейшей реализации строки, которая оперирует символами типа char:

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

Эта неэффективная реализация строки хранит три поля: указатель на динамически аллоцированный буфер (buf), реальный размер строки (size) и реальный размер буфера (capacity). Последнее используется для того, чтобы сократить количество аллокаций динамической памяти при вставках символа в буфер.

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

Для устранения накладных расходов можно разместить символы прямо внутри объекта строки. Для этого применим SSO и немного модифицируем класс:

class string
{
  size_t capacity;

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

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

В новой реализации можно расположить строки небольшой длины внутри объекта в stackbuf, не аллоцируя буфер на куче. Количество хранимых символов внутри объекта зависит от размера указателя и size_t. Например, на 64-битной платформе размер heapbuf будет составлять 16 байт, следовательно, внутри объекта можно хранить до 15 символов и терминальный ноль. На основе нестатического поля capacity определяется, где хранятся символы:

если capacity превышает размер stackbuf, то объект управляет буфером на куче и хранит символы там;
иначе символы хранятся внутри объекта.

Многие реализации строк используют SSO, чтобы ускорить работу с короткими строками. Например, SSO используется в следующих библиотеках: Microsoft STL, libstdc++, libc++, Boost, Folly.