Вебинар: C# разработка и статический анализ: в чем практическая польза? - 18.11
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 определяется, где хранятся символы:
Многие реализации строк используют SSO, чтобы ускорить работу с короткими строками. Например, SSO используется в следующих библиотеках: Microsoft STL, libstdc++, libc++, Boost, Folly.
0