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

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

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

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

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

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

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

предположим далее, что size_type 4 байта и value_type это 1 байт, это то, что первые 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 обойти

2 80
c++ string optimization c++-standard-library libc++

2 ответа:

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

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

в краткой форме, есть 3 слова для работы с:

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

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

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

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

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

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

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

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

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

to:

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

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

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

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

96

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

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 но не знаю, как он взаимодействует с анонимным объединением и псевдонимами, брошенными вместе), но стандартная библиотека может использовать преимущества реализации определенного поведения в любом случае.

17