Каков механизм оптимизации коротких строк в libc ++?

Этот ответ дает хороший общий обзор оптимизации коротких строк (SSO). Однако хотелось бы подробнее узнать, как это работает на практике, в частности в реализации libc ++:

• Насколько короткой должна быть строка, чтобы иметь право на SSO? Это зависит от целевой архитектуры?

• Как реализация различает короткие и длинные строки при доступе к строковым данным? Это так просто, m_size <= 16или это флаг, являющийся частью какой-либо другой переменной-члена? (Я полагаю, что это m_sizeили его часть также может использоваться для хранения строковых данных).

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

Вот некоторые наблюдения после просмотра источника :

libc ++ может быть скомпилирован с двумя немного разными схемами памяти для строкового класса, это регулируется _LIBCPP_ALTERNATE_STRING_LAYOUTфлагом. Обе схемы также различают машины с прямым порядком байтов и обратным порядком байтов, что оставляет нам в общей сложности 4 различных варианта. В дальнейшем я буду предполагать "нормальную" раскладку и прямой порядок байтов.

Если предположить, что size_typeэто 4 байта, а это value_type1 байт, первые 4 байта строки будут выглядеть в памяти следующим образом:

// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
       ^- is_long = 0

// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
       ^- is_long = 1

Поскольку размер короткой строки находится в верхних 7 битах, при доступе к ней ее нужно сместить:

size_type __get_short_size() const {
    return __r_.first().__s.__size_ >> 1;
}

Точно так же геттер и сеттер емкости длинной строки используются __long_maskдля обхода is_longбита.

Я все еще ищу ответ на свой первый вопрос, т.е. какое значение будет __min_capиметь емкость коротких строк для разных архитектур?

Другие реализации стандартной библиотеки

Этот ответ дает хороший обзор std::stringмакетов памяти в других реализациях стандартной библиотеки.

Библиотека libc ++ basic_stringразработана так, чтобы иметь sizeofтри слова для всех архитектур, где sizeof(word) == sizeof(void*). Вы правильно рассекли длинный / короткий флажок и поле размера в краткой форме.

какое значение __min_cap, емкость коротких строк, принимает для разных архитектур?

В краткой форме нужно работать с тремя словами:

• 1 бит переходит к длинному / короткому флагу.
• На размер идет 7 бит.
• Предполагая char, что 1 байт идет до конечного нуля (libc ++ всегда будет хранить конечный null за данными).

Это оставляет 3 слова минус 2 байта для хранения короткой строки (т. Е. Самой большой строки capacity()без распределения).

На 32-битной машине в короткую строку уместится 10 символов. sizeof (строка) - 12.

На 64-битной машине в короткую строку уместится 22 символа. sizeof (строка) - 24.

Основная цель дизайна заключалась в том, чтобы свести к минимуму sizeof(string), но сделать внутренний буфер как можно большим. Обоснование состоит в том, чтобы ускорить строительство и переместить назначение. Чем больше sizeof, тем больше слов вам нужно переместить во время построения перемещения или задания перемещения.

В полной форме требуется как минимум 3 слова для хранения указателя данных, размера и емкости. Поэтому я ограничил краткую форму теми же тремя словами. Было высказано предположение, что размер слова 4 может быть лучше. Я не тестировал этот выбор дизайна.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Называется флаг конфигурации, _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTкоторый переупорядочивает элементы данных таким образом, что "длинный макет" изменяется с:

struct __long
{
    size_type __cap_;
    size_type __size_;
    pointer   __data_;
};

кому:

struct __long
{
    pointer   __data_;
    size_type __size_;
    size_type __cap_;
};

Мотивом для этого изменения является вера в то, что ставка на __data_первое место даст некоторые преимущества в производительности за счет лучшего согласования. Была сделана попытка измерить преимущества производительности, и это было трудно измерить. Это не ухудшит производительность, а может немного улучшить.

Флаг следует использовать осторожно. Это другой ABI, и если его случайно смешать с libc ++, std::stringскомпилированным с другим параметром _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT, возникнут ошибки времени выполнения.

Я рекомендую изменять этот флаг только поставщикам libc ++.

Реализация libc ++ немного сложна, я проигнорирую ее альтернативный дизайн и предположу, что это маленький компьютер с порядком байтов:

template <...>
class basic_string {
/* many many things */

    struct __long
    {
        size_type __cap_;
        size_type __size_;
        pointer   __data_;
    };

    enum {__short_mask = 0x01};
    enum {__long_mask  = 0x1ul};

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short
    {
        union
        {
            unsigned char __size_;
            value_type __lx;
        };
        value_type __data_[__min_cap];
    };

    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw
    {
        size_type __words[__n_words];
    };

    struct __rep
    {
        union
        {
            __long  __l;
            __short __s;
            __raw   __r;
        };
    };

    __compressed_pair<__rep, allocator_type> __r_;
}; // basic_string

Примечание: __compressed_pairпо сути, это пара, оптимизированная для оптимизации пустой базы , иначе template <T1, T2> struct __compressed_pair: T1, T2 {};; во всех смыслах и целях вы можете считать его обычной парой. Его важность возникает только потому, что он не std::allocatorимеет состояния и, следовательно, пуст.

Ладно, это довольно сыро, поэтому давайте проверим механику! Внутри многие функции будут вызывать, __get_pointer()который сам вызывает, __is_longчтобы определить, использует ли строка представление __longили __short:

bool __is_long() const _NOEXCEPT
    { return bool(__r_.first().__s.__size_ & __short_mask); }

// __r_.first() -> __rep const&
//     .__s     -> __short const&
//     .__size_ -> unsigned char

Честно говоря, я не слишком уверен, что это Стандартный C ++ (я знаю исходное положение подпоследовательности, unionно не знаю, как оно сочетается с анонимным объединением и псевдонимом, брошенными вместе), но Стандартной библиотеке разрешено использовать преимущества определенной реализации поведение в любом случае.