Pregunta ¿Cuáles son los mecanismos de la 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? ¿Esto depende de la arquitectura de destino?

  • ¿Cómo distingue la implementación entre corto y largo cadenas de caracteres al acceder a los datos de cadena? Es tan simple como m_size <= 16 o es una bandera que es parte de alguna otra variable miembro? (YO Imagina eso m_size o parte de ella también podría ser utilizada para almacenar datos de cadena).

Hice esta pregunta específicamente para libc ++ porque sé que usa SSO, esto incluso se menciona en el 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 el _LIBCPP_ALTERNATE_STRING_LAYOUT bandera. Ambos diseños también distinguen entre las máquinas little-endian y big-endian, lo que nos deja con un total de 4 variantes diferentes. Asumiré el diseño "normal" y little-endian en lo que sigue.

Suponiendo además que size_type es de 4 bytes y eso value_type es de 1 byte, así es como 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, se debe cambiar cuando se accede a ella:

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

Del mismo modo, el captador y colocador para la capacidad de una cadena larga utiliza __long_mask para trabajar alrededor del is_long poco.

Todavía estoy buscando una respuesta a mi primera pregunta, es decir, qué valor tendría __min_cap, la capacidad de cuerdas cortas, tomar para diferentes arquitecturas?

Otras implementaciones de bibliotecas estándar

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


76
2018-02-11 06:01


origen


Respuestas:


La libc ++ basic_string está diseñado para tener un sizeof 3 palabras en todas las arquitecturas, donde sizeof(word) == sizeof(void*). Ha diseccionado correctamente el indicador largo / corto, y el campo de tamaño en el formulario corto.

¿qué valor tendría __min_cap, la capacidad de las cadenas cortas, para diferentes arquitecturas?

En la forma corta, hay 3 palabras para trabajar con:

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

Esto deja 3 palabras menos 2 bytes para almacenar una cadena corta (es decir, 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, 22 caracteres caben en la cadena corta. sizeof (cadena) es 24.

Un objetivo principal del diseño era minimizar sizeof(string), mientras que hace que el buffer interno sea lo más grande posible. La razón es acelerar la construcción de movimientos y mover la asignación. Cuanto mayor sea el sizeof, más palabras tiene 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, el tamaño y la capacidad de los datos. Por lo tanto, restringí el formulario corto 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 opción de diseño.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Hay un indicador de configuración llamado _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT que reorganiza los miembros de datos de modo que el "diseño largo" cambie desde:

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 __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 hacerlo un poco mejor.

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

Recomiendo que este indicador solo lo cambie un proveedor de libc ++.


89
2018-02-11 18:25



los Implementación de libc ++ es un poco complicado, voy a 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_pair es esencialmente un par optimizado para el Optimización de base vacía, aka template <T1, T2> struct __compressed_pair: T1, T2 {};; para todos los efectos, puedes considerarlo un par regular. Su importancia simplemente surge porque std::allocator es sin estado y, por lo tanto, está vacío.

De acuerdo, esto es bastante crudo, así que vamos a revisar la mecánica. Internamente, muchas funciones llamarán __get_pointer() que a su vez llama __is_long para determinar si la cadena está usando el __long o __short representación:

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 sincero, no estoy muy seguro de que esto sea el estándar C ++ (sé la disposición de subsecuencia inicial en union pero no se sabe cómo encaja con una unión anónima y aliasing juntos), pero una Biblioteca Estándar puede aprovechar el comportamiento definido de implementación de todos modos.


16
2018-02-11 08:30