¿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 <= 16o es una bandera que forma parte de alguna otra variable miembro? (Me imagino que esom_sizeo parte de él también podría usarse para almacenar datos de cadenas).
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 little-endian en lo que sigue.
Suponiendo además que size_typeson 4 bytes y value_type1 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, es necesario desplazarla al acceder a ella:
size_type __get_short_size() const {
return __r_.first().__s.__size_ >> 1;
}
De manera similar, el captador y definidor de la capacidad de una cadena larga suele __long_masksolucionar el is_longbit.
Todavía estoy buscando una respuesta a mi primera pregunta, es decir, ¿qué valor tomaría __min_cap, la capacidad de cadenas cortas, para diferentes arquitecturas?
Otras implementaciones de biblioteca estándar
Esta respuesta ofrece una buena descripción general de std::stringlos diseños de memoria en otras implementaciones de bibliotecas estándar.
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 el formulario corto.
¿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 corresponden al tamaño.
- Suponiendo
charque 1 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 asignación).
En una máquina de 32 bits, caben 10 caracteres en la cadena corta. El tamaño de (cadena) es 12.
En una máquina de 64 bits, caben 22 caracteres en la cadena corta. El tamaño de (cadena) es 24.
Un objetivo principal del diseño era minimizar sizeof(string)y al mismo tiempo hacer que el búfer interno fuera lo más grande posible. La razón es acelerar la construcción y asignación de mudanzas. Cuanto más grande sea sizeof, más palabras tendrás que mover durante la construcción o asignación de un movimiento.
El formato largo necesita un mínimo de 3 palabras para almacenar los 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 modo que el "diseño largo" cambie 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, pero fue difícil medirlas. No empeorará el rendimiento y puede mejorarlo ligeramente.
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, se _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTcrearán 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 supondré 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 conocido como template <T1, T2> struct __compressed_pair: T1, T2 {};; para todos los efectos, puedes considerarlo un par normal. Su importancia simplemente surge porque std::allocatorno tiene estado y, por lo tanto, está vacío.
Bien, esto es bastante crudo, ¡así que revisemos la mecánica! Internamente, muchas funciones llamarán __get_pointer()a la cual a su vez 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 esto sea C++ estándar (conozco la disposición de la subsecuencia inicial, unionpero no sé cómo se combina con una unión anónima y un alias juntos), pero se permite que una biblioteca estándar aproveche la implementación definida. comportamiento de todos modos.
