Значение аббревиатуры SSO в контексте std :: string

В вопросе C ++ об оптимизации и стиле кода в нескольких ответах упоминается «SSO» в контексте оптимизации копий std::string. Что SSO означает в этом контексте?

Ясно, что не «единый вход». «Оптимизация общей строки», возможно?

Фон / Обзор

Операции с автоматическими переменными («из стека», которые являются переменными, которые вы создаете без вызова malloc/ new), как правило, выполняются намного быстрее, чем операции с бесплатным хранилищем («куча», которые являются переменными, которые создаются с использованием new). Однако размер автоматических массивов фиксируется во время компиляции, а размер массивов из бесплатного хранилища - нет. Кроме того, размер стека ограничен (обычно несколько мегабайт), тогда как свободное хранилище ограничено только памятью вашей системы.

SSO - это оптимизация коротких / маленьких строк. A std::stringобычно хранит строку как указатель на свободное хранилище («куча»), которое дает характеристики производительности, аналогичные тем, которые вы вызываете new char [size]. Это предотвращает переполнение стека для очень больших строк, но это может быть медленнее, особенно при операциях копирования. В качестве оптимизации многие реализации std::stringсоздают небольшой автоматический массив, что-то вроде char [20]. Если у вас есть строка длиной не более 20 символов (в данном примере фактический размер меняется), она будет сохранена непосредственно в этом массиве. Это избавляет от необходимости newвообще звонить , что немного ускоряет процесс.

РЕДАКТИРОВАТЬ:

Я не ожидал, что этот ответ будет настолько популярен, но, поскольку он есть, позвольте мне дать более реалистичную реализацию с оговоркой, что я никогда не читал ни одной реализации SSO «в дикой природе».

Детали реализации

Как минимум, std::stringнеобходимо хранить следующую информацию:

• Размер
• Емкость
• Расположение данных

Размер может быть сохранен как std::string::size_typeили как указатель на конец. Разница лишь в том, хотите ли вы вычесть два указателя при вызове пользователя sizeили добавить size_typeк указателю при вызове пользователя end. Емкость может быть сохранена в любом случае.

Вы не платите за то, что не используете.

Сначала рассмотрим наивную реализацию, основанную на том, что я изложил выше:

class string {
public:
    // all 83 member functions
private:
    std::unique_ptr<char[]> m_data;
    size_type m_size;
    size_type m_capacity;
    std::array<char, 16> m_sso;
};

Для 64-битной системы это обычно означает, что в std::stringкаждой строке содержится 24 байта служебных данных плюс еще 16 для буфера SSO (здесь выбрано 16 вместо 20 из-за требований заполнения). На самом деле не имеет смысла хранить эти три элемента данных плюс локальный массив символов, как в моем упрощенном примере. Если m_size <= 16, тогда я добавлю все данные m_sso, так что я уже знаю емкость и мне не нужен указатель на данные. Если m_size > 16, тогда мне не нужно m_sso. Там нет абсолютно никаких совпадений, где мне все они нужны. Разумное решение, которое не тратит впустую пространство, выглядело бы как-то так (непроверено, только для примера):

class string {
public:
    // all 83 member functions
private:
    size_type m_size;
    union {
        class {
            // This is probably better designed as an array-like class
            std::unique_ptr<char[]> m_data;
            size_type m_capacity;
        } m_large;
        std::array<char, sizeof(m_large)> m_small;
    };
};

Я бы предположил, что большинство реализаций выглядят больше так.

SSO - это сокращение от «Оптимизация малых строк», метод, при котором небольшие строки внедряются в тело класса строк, а не в отдельный буфер.

Как уже объяснялось в других ответах, SSO означает оптимизацию малых / коротких строк . Мотивация этой оптимизации является неопровержимым доказательством того, что приложения в целом обрабатывают намного более короткие строки, чем более длинные строки.

Как объяснил Дэвид Стоун в своем ответе выше , std::stringкласс использует внутренний буфер для хранения содержимого до заданной длины, что исключает необходимость динамического выделения памяти. Это делает код более эффективным и быстрым .

Этот другой связанный ответ ясно показывает, что размер внутреннего буфера зависит от std::stringреализации, которая варьируется от платформы к платформе (см. Результаты тестов ниже).

Ориентиры

Вот небольшая программа, которая тестирует операцию копирования множества строк одинаковой длины. Он начинает печатать время для копирования 10 миллионов строк с длиной = 1. Затем он повторяется со строками длины = 2. Он продолжает работать, пока длина не станет 50.

#include <string>
#include <iostream>
#include <vector>
#include <chrono>

static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static const int ARRAY_SIZE = sizeof(CHARS) - 1;

static const int BENCHMARK_SIZE = 10000000;
static const int MAX_STRING_LENGTH = 50;

using time_point = std::chrono::high_resolution_clock::time_point;

void benchmark(std::vector<std::string>& list) {
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();

    // force a copy of each string in the loop iteration
    for (const auto s : list) {
        std::cout << s;
    }

    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
    const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    std::cerr << list[0].length() << ',' << duration << '\n';
}

void addRandomString(std::vector<std::string>& list, const int length) {
    std::string s(length, 0);
    for (int i = 0; i < length; ++i) {
        s[i] = CHARS[rand() % ARRAY_SIZE];
    }
    list.push_back(s);
}

int main() {
    std::cerr << "length,time\n";

    for (int length = 1; length <= MAX_STRING_LENGTH; length++) {
        std::vector<std::string> list;
        for (int i = 0; i < BENCHMARK_SIZE; i++) {
            addRandomString(list, length);
        }
        benchmark(list);
    }

    return 0;
}

Если вы хотите запустить эту программу, вы должны сделать это ./a.out > /dev/nullтак, чтобы время печати строк не учитывалось. Цифры, которые имеют значение, печатаются stderr, поэтому они будут отображаться в консоли.

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

Также обратите внимание, что на машине linux переход происходит, когда длина строки достигает 16. В macbook переход происходит, когда длина достигает 23. Это подтверждает, что SSO зависит от реализации платформы.

Ubuntu

MacBook Pro