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

Question

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

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

Answer 1

Фон / Обзор

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

SSO - это оптимизация коротких / маленьких строк. 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;
    };
};

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

Answer 2

SSO - это аббревиатура для "Small String Optimization", техники, в которой небольшие строки внедряются в тело класса строк, а не в отдельный буфер.

Answer 3

Как уже объяснялось в других ответах, 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