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

9 minutos de lectura

Significado del acronimo SSO en el contexto de stdstring
Raedwald

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

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

  • Eso es solo un duplicado de la misma manera que “lo que es 2+2” es un duplicado de “cuál es el resultado de 200/50”. La respuesta es la misma. La pregunta es completamente diferente. “Cerrar como duplicado” está diseñado para usarse cuando varias personas hacen la misma pregunta*. Cuando una persona pregunta “¿cómo es std::string implementado”, y otro pregunta “¿qué significa SSO?”, tienes que estar absolutamente loco para considerar que son la misma pregunta

    – jalf

    25 de abril de 2012 a las 11:59


  • @jalf: si hay una Q+A existente que abarca exactamente el alcance de esta pregunta, la consideraría un duplicado (no digo que el OP debería haber buscado esto él mismo, simplemente que cualquier respuesta aquí cubrirá el terreno que es ya ha sido cubierto.)

    –Oliver Charlesworth

    25 de abril de 2012 a las 12:01


  • Efectivamente, le está diciendo al OP que “su pregunta es incorrecta. Pero necesitaba saber la respuesta para saber lo que deberían han preguntado”. Es una buena manera de hacer que la gente se desanime. También hace que sea innecesariamente difícil encontrar la información que necesitabas. Si la gente no hace preguntas (y el cierre es efectivamente decir “esta pregunta no debería haberse hecho”), entonces no habría manera posible para las personas que no ya sabes la respuesta, para obtener la respuesta a esta pregunta

    – jalf

    25 de abril de 2012 a las 12:06


  • @jalf: En absoluto. En mi opinión, “votar para cerrar” no implica “mala pregunta”. Yo uso votos negativos para eso. Lo considero un duplicado en el sentido de que todas las innumerables preguntas (i = i ++, etc.) cuya respuesta es “comportamiento indefinido” son duplicados entre sí. En una nota diferente, ¿por qué nadie respondió la pregunta si no es un duplicado?

    –Oliver Charlesworth

    25 de abril de 2012 a las 12:44


  • @jalf: Estoy de acuerdo con Oli, la pregunta no es un duplicado, pero la respuesta sí lo sería, por lo tanto, redirigiendo a otra pregunta donde las respuestas ya se encuentran parecen apropiadas. Las preguntas cerradas como duplicados no desaparecen, sino que actúan como punteros hacia otra pregunta donde se encuentra la respuesta. La próxima persona que busque SSO terminará aquí, seguirá la redirección y encontrará su respuesta.

    – Matthieu M.

    25 de abril de 2012 a las 12:59


Significado del acronimo SSO en el contexto de stdstring
david piedra

Antecedentes / Descripción general

Operaciones en variables automáticas (“desde la pila”, que son variables que creas sin llamar malloc / new) son generalmente mucho más rápidos que los que involucran 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 el momento de la compilación, pero el tamaño de las matrices de la tienda gratuita no lo es. Además, el tamaño de la pila es limitado (normalmente unos pocos MiB), mientras que el almacenamiento gratuito solo está limitado por la memoria de su sistema.

SSO es la optimización de cadenas cortas/pequeñas. A std::string generalmente almacena la cadena como un puntero a la tienda libre (“el montón”), lo que brinda características de rendimiento similares a las de llamar new char [size]. Esto evita un desbordamiento de pila para cadenas muy grandes, pero puede ser más lento, especialmente con operaciones de copia. Como optimización, muchas implementaciones de std::string crear 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), la almacena directamente en esa matriz. Esto evita la necesidad de llamar new en absoluto, lo que acelera un poco las cosas.

EDITAR:

No esperaba que esta respuesta fuera tan popular, pero como 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, un std::string necesita almacenar la siguiente información:

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

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

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<char[]> m_data;
    size_type m_size;
    size_type m_capacity;
    std::array<char, 16> 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 los 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 <= 16luego 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 > 16entonces no necesito m_sso. No hay absolutamente ninguna superposición donde los necesito a todos. Una solución más inteligente que no desperdicie espacio se vería un poco más como esto (no probado, 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<char[]> m_data;
            size_type m_capacity;
        } m_large;
        std::array<char, sizeof(m_large)> m_small;
    };
};

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

  • Aquí hay una buena explicación de algunas implementaciones reales: stackoverflow.com/a/28003328/203044

    – BillT

    12/09/2015 a las 14:15

  • ¿Es SSO realmente práctico cuando la mayoría de los desarrolladores pasan std::string usando referencias const?

    – Gupta

    24 de mayo de 2019 a las 8:13

  • SSO tiene dos beneficios además de abaratar la copia. La primera es que si el tamaño de su cadena se ajusta al tamaño pequeño del búfer, no necesita asignar en la construcción inicial. La segunda es que cuando una función acepta una std::string const &, llegar a los datos es una sola indirección de memoria, porque los datos se almacenan en la ubicación de la referencia. Si no hubiera optimización de cadenas pequeñas, el acceso a los datos requeriría dos indireccionamientos de memoria (primero para cargar la referencia a la cadena y leer su contenido, luego el segundo para leer el contenido del puntero de datos en la cadena).

    –David Piedra

    2 jun 2019 a las 17:31

SSO es la abreviatura de “Optimización de cadenas pequeñas”, una técnica en la que las cadenas pequeñas se incrustan en el cuerpo de la clase de cadena en lugar de utilizar un búfer 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 cadenas más largas.

Como explicó David Stone en su respuesta anterior, el std::string La clase usa un búfer interno para almacenar contenido hasta una longitud dada, y esto elimina la necesidad de asignar memoria dinámicamente. Esto hace que el código 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 std::string implementación, que varía de una plataforma a otra (consulte los resultados de referencia a continuación).

Puntos de referencia

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

#include <string>
#include <iostream>
#include <vector>
#include <chrono>

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<std::string>& 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<std::chrono::milliseconds>(t2 - t1).count();
    std::cerr << list[0].length() << ',' << duration << '\n';
}

void addRandomString(std::vector<std::string>& 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<std::string> list;
        for (int i = 0; i < BENCHMARK_SIZE; i++) {
            addRandomString(list, length);
        }
        benchmark(list);
    }

    return 0;
}

Si desea ejecutar este programa, 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 stderrpor 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 cadenas ya no caben en el búfer interno y se debe usar la asignación de memoria.

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

ubuntu
Punto de referencia de SSO en Ubuntu

Macbook Pro
Punto de referencia de SSO en Macbook Pro

  • Reduje el tiempo de casi 4 minutos a casi 1 minuto eliminando menos opciones de diseño de las necesarias. ideone.com/KJCh2H

    usuario10063119

    17 de agosto de 2020 a las 16:23


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad