¿Cuáles son los mecanismos de optimización de cadenas cortas en libc ++?

Esta respuesta ofrece una buena descripción general de alto nivel de la optimización de cadenas cortas (SSO). Sin embargo, me gustaría saber con más detalle cómo funciona en la práctica, específicamente en la implementación de libc ++:

• ¿Qué tan corta debe ser la cadena para calificar para SSO? ¿Depende esto de la arquitectura de destino?

• ¿Cómo distingue la implementación entre cadenas cortas y largas al acceder a los datos de la cadena? ¿Es tan simple como m_size <= 16una bandera que forma parte de alguna otra variable miembro? (Me imagino que m_sizeo parte de él también podría usarse para almacenar datos de cadena).

Hice esta pregunta específicamente para libc ++ porque sé que usa SSO, esto incluso se menciona en la página de inicio de libc ++ .

Aquí hay algunas observaciones después de mirar la fuente :

libc ++ se puede compilar con dos diseños de memoria ligeramente diferentes para la clase de cadena, esto se rige por la _LIBCPP_ALTERNATE_STRING_LAYOUTbandera. Ambos diseños también distinguen entre máquinas little-endian y big-endian, lo que nos deja con un total de 4 variantes diferentes. Asumiré el diseño "normal" y el little-endian en lo que sigue.

Suponiendo además que size_typeson 4 bytes y que value_typees 1 byte, así se verían los primeros 4 bytes de una cadena en la memoria:

// 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

Dado que el tamaño de la cadena corta está en los 7 bits superiores, debe cambiarse al acceder a ella:

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

De manera similar, el captador y el configurador de la capacidad de una cadena larga se utilizan __long_maskpara trabajar alrededor de la is_longbroca.

Todavía estoy buscando una respuesta a mi primera pregunta, es decir, ¿qué valor tomaría __min_capla capacidad de cadenas cortas para diferentes arquitecturas?

Otras implementaciones de bibliotecas estándar

Esta respuesta ofrece una buena descripción general de std::stringlos diseños de memoria en otras implementaciones de bibliotecas estándar.

El libc ++ basic_stringestá diseñado para tener sizeof3 palabras en todas las arquitecturas, donde sizeof(word) == sizeof(void*). Ha diseccionado correctamente la bandera larga / corta y el campo de tamaño en forma corta.

¿Qué valor tomaría __min_cap, la capacidad de cadenas cortas, para diferentes arquitecturas?

En la forma corta, hay 3 palabras con las que trabajar:

• 1 bit va a la bandera larga / corta.
• 7 bits va al tamaño.
• Suponiendo que char1 byte va al nulo final (libc ++ siempre almacenará un nulo final detrás de los datos).

Esto deja 3 palabras menos 2 bytes para almacenar una cadena corta (es decir, la más grande capacity()sin una asignación).

En una máquina de 32 bits, caben 10 caracteres en la cadena corta. sizeof (cadena) es 12.

En una máquina de 64 bits, caben 22 caracteres en la cadena corta. sizeof (cadena) es 24.

Uno de los principales objetivos del diseño era minimizar sizeof(string), mientras que el búfer interno era lo más grande posible. La razón es acelerar la construcción y la asignación de movimientos. Cuanto más grande sea sizeof, más palabras tendrá que mover durante una construcción de movimiento o una asignación de movimiento.

La forma larga necesita un mínimo de 3 palabras para almacenar el puntero de datos, el tamaño y la capacidad. Por lo tanto, restringí la forma corta a esas mismas 3 palabras. Se ha sugerido que un tamaño de 4 palabras podría tener un mejor rendimiento. No he probado esa elección de diseño.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Hay un indicador de configuración llamado _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTque reorganiza los miembros de datos de manera que el "diseño largo" cambia de:

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

a:

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

La motivación para este cambio es la creencia de que poner __data_primero tendrá algunas ventajas de rendimiento debido a una mejor alineación. Se intentó medir las ventajas de rendimiento y fue difícil de medir. No empeorará el rendimiento y puede que lo mejore un poco.

La bandera debe usarse con cuidado. Es una ABI diferente, y si se mezcla accidentalmente con una libc ++ std::stringcompilada con una configuración diferente de _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTcreará errores de tiempo de ejecución.

Recomiendo que esta bandera solo la cambie un proveedor de libc ++.

La implementación de libc ++ es un poco complicada, ignoraré su diseño alternativo y supongo que una pequeña computadora 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

Nota: __compressed_paires esencialmente un par optimizado para la optimización de base vacía , también conocida como template <T1, T2> struct __compressed_pair: T1, T2 {};; para todos los efectos, puede considerarlo un par normal. Su importancia surge simplemente porque std::allocatores apátrida y, por lo tanto, está vacía.

De acuerdo, esto es bastante crudo, ¡así que revisemos la mecánica! Internamente, muchas funciones llamarán a lo __get_pointer()que él mismo llama __is_longpara determinar si la cadena está usando la representación __longo __short:

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

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

Para ser honesto, no estoy muy seguro de que sea C ++ estándar (conozco la disposición de subsecuencia inicial en unionpero no sé cómo se combina con una unión anónima y un aliasing juntos), pero una biblioteca estándar puede aprovechar la implementación definida comportamiento de todos modos.