Significado del acrónimo SSO en el contexto de std :: string

En una pregunta de C ++ sobre la optimización y el estilo del código , varias respuestas se referían a “SSO” en el contexto de la optimización de copias de std::string . ¿Qué significa SSO en ese contexto?

Claramente no “inicio de sesión único”. “Optimización de cadenas compartidas”, tal vez?

Fondo / Descripción general

Las operaciones en variables automáticas (“desde la stack”, que son variables que se crean sin llamar a malloc / new ) son generalmente mucho más rápidas que las que implican la tienda gratuita (“el montón”, que son variables que se crean usando new ). Sin embargo, el tamaño de las matrices automáticas se fija en tiempo de comstackción, pero el tamaño de las matrices de la tienda gratuita no lo está. Además, el tamaño de la stack es limitado (normalmente unos pocos MiB), mientras que la tienda gratuita solo está limitada por la memoria de su sistema.

SSO es la optimización de cadenas cortas / pequeñas. Una std::string normalmente almacena la cadena como un puntero a la tienda gratuita (“the heap”), que proporciona características de rendimiento similares a las de un new char [size] . Esto evita un desbordamiento de stack para cadenas muy grandes, pero puede ser más lento, especialmente con operaciones de copia. Como una optimización, muchas implementaciones de std::string crean una pequeña matriz automática, algo así como char [20] . Si tiene una cadena de 20 caracteres o menos (dado este ejemplo, el tamaño real varía), lo almacena directamente en esa matriz. Esto evita la necesidad de llamar a algo new , lo que acelera un poco las cosas.

EDITAR:

No esperaba que esta respuesta fuera tan popular, pero dado que lo es, permítanme dar una implementación más realista, con la advertencia de que nunca he leído ninguna implementación de SSO “en la naturaleza”.

Detalles de implementacion

Como mínimo, std::string necesita almacenar la siguiente información:

  • El tamaño
  • La capacidad
  • La ubicación de los datos

El tamaño se puede almacenar como std::string::size_type o como un puntero al final. La única diferencia es si desea restar dos punteros cuando el usuario llama al size o agrega un size_type a un puntero cuando el usuario llama a end . La capacidad se puede almacenar de cualquier manera también.

No pagas por lo que no usas.

Primero, considere la implementación ingenua basada en lo que describí anteriormente:

 class string { public: // all 83 member functions private: std::unique_ptr m_data; size_type m_size; size_type m_capacity; std::array m_sso; }; 

Para un sistema de 64 bits, eso generalmente significa que std::string tiene 24 bytes de ‘sobrecarga’ por cadena, más otros 16 para el búfer SSO (16 elegidos aquí en lugar de 20 debido a requisitos de relleno). Realmente no tendría sentido almacenar esos tres miembros de datos más una matriz local de caracteres, como en mi ejemplo simplificado. Si m_size <= 16 , pondré todos los datos en m_sso , por lo que ya conozco la capacidad y no necesito el puntero a los datos. Si m_size > 16 , entonces no necesito m_sso . No hay absolutamente ninguna superposición cuando los necesito a todos. Una solución más inteligente que no desperdicie espacio se vería algo más parecido a esto (sin probar, solo con fines de ejemplo):

 class string { public: // all 83 member functions private: size_type m_size; union { class { // This is probably better designed as an array-like class std::unique_ptr m_data; size_type m_capacity; } m_large; std::array m_small; }; }; 

Supongo que la mayoría de las implementaciones se parecen más a esto.

SSO es la abreviatura de “Small String Optimization”, una técnica donde las cadenas pequeñas están incrustadas en el cuerpo de la clase de cadena en lugar de usar un buffer asignado por separado.

Como ya se explicó en las otras respuestas, SSO significa optimización de cadena pequeña / corta . La motivación detrás de esta optimización es la evidencia innegable de que las aplicaciones en general manejan cadenas mucho más cortas que las cadenas más largas.

Como explicó David Stone en su respuesta anterior , la clase std::string utiliza un búfer interno para almacenar contenidos hasta una longitud determinada, y esto elimina la necesidad de asignar dinámicamente la memoria. Esto hace que el código sea más eficiente y más rápido .

Esta otra respuesta relacionada muestra claramente que el tamaño del búfer interno depende de la implementación de std::string , que varía de una plataforma a otra (consulte los resultados del índice de referencia a continuación).

Puntos de referencia

Aquí hay un pequeño progtwig que compara la operación de copia de muchas cadenas con la misma longitud. Comienza a imprimir el tiempo para copiar 10 millones de cadenas con longitud = 1. Luego se repite con cadenas de longitud = 2. Continúa hasta que la longitud sea 50.

 #include  #include  #include  #include  static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; static const int ARRAY_SIZE = sizeof(CHARS) - 1; static const int BENCHMARK_SIZE = 10000000; static const int MAX_STRING_LENGTH = 50; using time_point = std::chrono::high_resolution_clock::time_point; void benchmark(std::vector& list) { std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); // force a copy of each string in the loop iteration for (const auto s : list) { std::cout << s; } std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); const auto duration = std::chrono::duration_cast(t2 - t1).count(); std::cerr << list[0].length() << ',' << duration << '\n'; } void addRandomString(std::vector& list, const int length) { std::string s(length, 0); for (int i = 0; i < length; ++i) { s[i] = CHARS[rand() % ARRAY_SIZE]; } list.push_back(s); } int main() { std::cerr << "length,time\n"; for (int length = 1; length <= MAX_STRING_LENGTH; length++) { std::vector list; for (int i = 0; i < BENCHMARK_SIZE; i++) { addRandomString(list, length); } benchmark(list); } return 0; } 

Si desea ejecutar este progtwig, debe hacerlo como ./a.out > /dev/null para que no se cuente el tiempo para imprimir las cadenas. Los números que importan están impresos en stderr , por lo que aparecerán en la consola.

He creado gráficos con la salida de mis máquinas MacBook y Ubuntu. Tenga en cuenta que hay un gran salto en el tiempo para copiar las cadenas cuando la longitud alcanza un punto determinado. Ese es el momento en que las cuerdas ya no caben en el búfer interno y la asignación de memoria debe ser utilizada.

Tenga en cuenta también que en la máquina de Linux, el salto ocurre cuando la longitud de la cadena alcanza 16. En el macbook, el salto ocurre cuando la longitud alcanza 23. Esto confirma que el SSO depende de la implementación de la plataforma.

Ubuntu Referencia de SSO en Ubuntu

Macbook Pro Referencia de SSO en Macbook Pro