c++ - ¿Por qué las operaciones std:: string funcionan mal?

python performance

Question

Hice una prueba para comparar operaciones de cadena en varios idiomas para elegir un idioma para la aplicación del lado del servidor. Los resultados parecían normales hasta que finalmente probé con C ++, lo que me sorprendió mucho. Entonces me pregunto si me había perdido alguna optimización y vine a buscar ayuda.

La prueba son principalmente operaciones intensivas de cadenas, que incluyen concatenación y búsqueda. La prueba se realiza en Ubuntu 11.10 amd64, con la versión 4.6.1 de GCC. La máquina es Dell Optiplex 960, con 4G RAM y CPU de cuatro núcleos.

en Python (2.7.2):

def test():
    x = ""
    limit = 102 * 1024
    while len(x) < limit:
        x += "X"
        if x.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0:
            print("Oh my god, this is impossible!")
    print("x''s length is : %d" % len(x))

test()

que da resultado:

x''s length is : 104448

real    0m8.799s
user    0m8.769s
sys     0m0.008s

en Java (OpenJDK-7):

public class test {
    public static void main(String[] args) {
        int x = 0;
        int limit = 102 * 1024;
        String s="";
        for (; s.length() < limit;) {
            s += "X";
            if (s.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ") > 0)
            System.out.printf("Find!/n");
        }
        System.out.printf("x''s length = %d/n", s.length());
    }
}

que da resultado:

x''s length = 104448

real    0m50.436s
user    0m50.431s
sys     0m0.488s

en Javascript (Nodejs 0.6.3)

function test()
{
    var x = "";
    var limit = 102 * 1024;
    while (x.length < limit) {
        x += "X";
        if (x.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0)
            console.log("OK");
    }
    console.log("x''s length = " + x.length);
}();

que da resultado:

x''s length = 104448

real    0m3.115s
user    0m3.084s
sys     0m0.048s

en C ++ (g ++ -Ofast)

No es sorprendente que Nodejs se desempeñe mejor que Python o Java. Pero esperaba que libstdc ++ daría mucho mejor rendimiento que Nodejs, cuyo resultado realmente me sorprendió.

#include <iostream>
#include <string>
using namespace std;
void test()
{
    int x = 0;
    int limit = 102 * 1024;
    string s("");
    for (; s.size() < limit;) {
        s += "X";
        if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != string::npos)
            cout << "Find!" << endl;
    }
    cout << "x''s length = " << s.size() << endl;
}

int main()
{
    test();
}

que da resultado:

x length = 104448

real    0m5.905s
user    0m5.900s
sys     0m0.000s

Breve resumen

OK, ahora veamos el resumen:

• javascript en Nodejs (V8): 3.1s
• Python en CPython 2.7.2: 8.8s
• C ++ con libstdc ++: 5.9s
• Java en OpenJDK 7: 50.4s

¡Asombrosamente! Intenté "-O2, -O3" en C ++ pero noté que me ayudó. C ++ parece tener solo un 50% de rendimiento de javascript en V8, e incluso es pobre que CPython. ¿Alguien podría explicarme si me perdí alguna optimización en GCC o es este el caso? Muchas gracias.

Answer 1

Acabo de probar el ejemplo de C ++. Si elimino la llamada a std::sting::find , el programa finaliza en poco tiempo. Por lo tanto, las asignaciones durante la concatenación de cadenas no son un problema aquí.

Si agrego una variable sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" y reemplazo la aparición de "ABC ... XYZ" en la llamada de std::string::find , el programa necesita casi el mismo tiempo para terminar que el original ejemplo. De nuevo, esto muestra que la asignación y el cálculo de la longitud de la cadena no aumentan mucho el tiempo de ejecución.

Por lo tanto, parece que el algoritmo de búsqueda de cadenas utilizado por libstdc ++ no es tan rápido para su ejemplo como los algoritmos de búsqueda de javascript o python. Tal vez quiera probar C ++ nuevamente con su propio algoritmo de búsqueda de cadenas que se ajuste mejor a su propósito.

Answer 2

Así que fui y jugué un poco con esto en ideone.org.

Aquí una versión ligeramente modificada de su programa C ++ original, pero con la adición en el ciclo eliminada, por lo que solo mide la llamada a std::string::find() . Tenga en cuenta que tuve que reducir el número de iteraciones a ~ 40%, de lo contrario, ideone.org mataría el proceso.

#include <iostream>
#include <string>

int main()
{
    const std::string::size_type limit = 42 * 1024;
    unsigned int found = 0;

    //std::string s;
    std::string s(limit, ''X'');
    for (std::string::size_type i = 0; i < limit; ++i) {
        //s += ''X'';
        if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos)
            ++found;
    }

    if(found > 0)
        std::cout << "Found " << found << " times!/n";
    std::cout << "x''s length = " << s.size() << ''/n'';

    return 0;
}

Mis resultados en ideone.org son el time: 3.37s . (Por supuesto, esto es muy dudoso, pero déjame un momento y espera el otro resultado).

Ahora tomamos este código e intercambiamos las líneas comentadas, para probar agregar, en lugar de encontrar. Tenga en cuenta que, esta vez, he multiplicado por diez el número de iteraciones al tratar de ver el resultado de cualquier momento.

#include <iostream>
#include <string>

int main()
{
    const std::string::size_type limit = 1020 * 1024;
    unsigned int found = 0;

    std::string s;
    //std::string s(limit, ''X'');
    for (std::string::size_type i = 0; i < limit; ++i) {
        s += ''X'';
        //if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos)
        //    ++found;
    }

    if(found > 0)
        std::cout << "Found " << found << " times!/n";
    std::cout << "x''s length = " << s.size() << ''/n'';

    return 0;
}

Mis resultados en ideone.org , a pesar del multiplicado por diez en las iteraciones, son time: 0s .

Mi conclusión: este punto de referencia es, en C ++, altamente dominado por la operación de búsqueda , la adición del carácter en el ciclo no tiene influencia alguna sobre el resultado. ¿Esa era realmente tu intención?

Answer 3

Como lo menciona sbi, el caso de prueba está dominado por la operación de búsqueda. Tenía curiosidad de cuán rápido se compara la asignación de texto entre C ++ y Javascript.

Sistema: Raspberry Pi 2, g ++ 4.6.3, nodo v0.12.0, g ++ -std = c ++ 0x -O2 perf.cpp

C ++: 770 ms

C ++ sin reserva: 1196ms

Javascript: 2310ms

C ++

#include <iostream>
#include <string>
#include <chrono>
using namespace std;
using namespace std::chrono;

void test()
{
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    int x = 0;
    int limit = 1024 * 1024 * 100;
    string s("");
    s.reserve(1024 * 1024 * 101);
    for(int i=0; s.size()< limit; i++){
        s += "SUPER NICE TEST TEXT";
    }

    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
    cout << duration << endl;
}

int main()
{
    test();
}

JavaScript

function test()
{
    var time = process.hrtime();
    var x = "";
    var limit = 1024 * 1024 * 100;
    for(var i=0; x.length < limit; i++){
        x += "SUPER NICE TEST TEXT";
    }

    var diff = process.hrtime(time);
    console.log(''benchmark took %d ms'', diff[0] * 1e3 + diff[1] / 1e6 );
}

test();

Answer 4

El lenguaje C / C ++ no es fácil y lleva años crear programas rápidos.

con la versión strncmp (3) modificada de la versión c:

#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>

void test()
{
    int limit = 102 * 1024;
    char s[limit];
    size_t size = 0;
    while (size < limit) {
        s[size++] = ''X'';
        if (!strncmp(s, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 26)) {
            fprintf(stderr, "zomg/n");
            return;
        }
    }
    printf("x''s length = %zu/n", size);
}

int main()
{
    test();
    return 0;
}

Answer 5

Esa es la más obvia: por favor, trate de hacer la s.reserve(limit); antes del ciclo principal.

La documentación está here .

Debo mencionar que el uso directo de las clases estándar en C ++ de la misma manera que lo hace en Java o Python a menudo le dará un rendimiento inferior si no está al tanto de lo que se hace detrás del escritorio. No hay un rendimiento mágico en el lenguaje en sí mismo, simplemente te da las herramientas adecuadas.

Answer 6

La solución idiomática de C ++ sería:

#include <iostream>
#include <string>
#include <algorithm>

int main()
{
    const int limit = 102 * 1024;
    std::string s;
    s.reserve(limit);

    const std::string pattern("ABCDEFGHIJKLMNOPQRSTUVWXYZ");

    for (int i = 0; i < limit; ++i) {
        s += ''X'';
        if (std::search(s.begin(), s.end(), pattern.begin(), pattern.end()) != s.end())
            std::cout << "Omg Wtf found!";
    }
    std::cout << "X''s length = " << s.size();
    return 0;
}

Podría acelerar esto considerablemente poniendo la cuerda en la pila y usando memmem, pero parece que no hay necesidad. Corriendo en mi máquina, esta es más de 10 veces la velocidad de la solución de Python.

[En mi ordenador portátil]

time ./test X''s length = 104448 real 0m2.055s user 0m2.049s sys 0m0.001s

Answer 7

Lo que te falta aquí es la complejidad inherente de la búsqueda de búsqueda.

Estás ejecutando la búsqueda 102 * 1024 (104 448) veces. Un algoritmo de búsqueda ingenuo intentará, cada vez, hacer coincidir el patrón a partir del primer carácter, luego el segundo, etc.

Por lo tanto, tiene una cadena que va de la longitud 1 a N , y en cada paso busca el patrón en esta cadena, que es una operación lineal en C ++. Eso es N * (N+1) / 2 = 5 454 744 576 comparaciones. No estoy tan sorprendido como tú de que esto tome un tiempo ...

Vamos a verificar la hipótesis utilizando la sobrecarga de find que busca una sola A :

Original: 6.94938e+06 ms
Char    : 2.10709e+06 ms

Aproximadamente 3 veces más rápido, por lo que estamos dentro del mismo orden de magnitud. Por lo tanto, el uso de una cadena completa no es realmente interesante.

Conclusion? Tal vez ese find podría ser optimizado un poco. Pero el problema no vale la pena.

Nota: y para aquellos que pregonan a Boyer Moore, me temo que la aguja es demasiado pequeña, por lo que no ayudará mucho. Puede cortar un orden de magnitud (26 caracteres), pero no más.

Answer 8

Mi primer pensamiento es que no hay un problema.

C ++ ofrece el segundo mejor rendimiento, casi diez veces más rápido que Java. Tal vez todos, excepto Java, se están ejecutando cerca del mejor rendimiento posible para esa funcionalidad, y debería estar buscando cómo solucionar el problema de Java (sugerencia - StringBuilder ).

En el caso de C ++, hay algunas cosas para intentar mejorar un poco el rendimiento. En particular...

• s += ''X''; en lugar de s += "X";
• Declarar string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); fuera del bucle, y pasar esto para las llamadas de find . Una instancia std::string conoce su propia longitud, mientras que una cadena C requiere una verificación en tiempo lineal para determinarlo, y esto puede (o no) ser relevante para std::string::find performance.
• Intente usar std::stringstream , por una razón similar a la razón por la que debería usar StringBuilder para Java, aunque lo más probable es que las conversiones repetidas en la string generen más problemas.

En general, el resultado no es demasiado sorprendente. Es posible que JavaScript, con un buen compilador JIT, pueda optimizar un poco mejor que la compilación estática de C ++ en este caso.

Con suficiente trabajo, siempre debería ser capaz de optimizar C ++ mejor que JavaScript, pero siempre habrá casos en que eso no ocurra de manera natural y donde pueda tomar un poco de conocimiento y esfuerzo lograr eso.

Answer 9

No es que std::string tenga un rendimiento deficiente (tanto como no me gusta C ++), es que el manejo de cadenas está muy optimizado para esos otros lenguajes.

Sus comparaciones de rendimiento de cuerdas son engañosas y presuntuosas si se pretende que representen algo más que eso.

Sé con certeza que los objetos de cadena de Python están completamente implementados en C , y de hecho en Python 2.7, existen numerous optimizations debido a la falta de separación entre cadenas y bytes de unicode. Si ejecutó esta prueba en Python 3.x, la encontrará considerablemente más lenta.

Javascript tiene numerosas implementaciones muy optimizadas. Es de esperar que el manejo de cadenas sea excelente aquí.

Su resultado de Java puede deberse a un manejo incorrecto de cadenas o algún otro caso pobre. Espero que un experto en Java pueda intervenir y corregir esta prueba con algunos cambios.

En cuanto a su ejemplo de C ++, esperaría que el rendimiento excediera ligeramente la versión de Python. Hace las mismas operaciones, con menos sobrecarga de intérprete. Esto se refleja en tus resultados. Precediendo la prueba con s.reserve(limit); eliminaría la sobrecarga de reasignación.

Repito que solo estás probando una sola faceta de las implementaciones de los idiomas. Los resultados de esta prueba no reflejan la velocidad general del lenguaje.

He proporcionado una versión C para mostrar cuán tontos pueden ser estos concursos de meando:

#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>

void test()
{
    int limit = 102 * 1024;
    char s[limit];
    size_t size = 0;
    while (size < limit) {
        s[size++] = ''X'';
        if (memmem(s, size, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 26)) {
            fprintf(stderr, "zomg/n");
            return;
        }
    }
    printf("x''s length = %zu/n", size);
}

int main()
{
    test();
    return 0;
}

Sincronización:

matt@stanley:~/Desktop$ time ./smash 
x''s length = 104448

real    0m0.681s
user    0m0.680s
sys     0m0.000s

Answer 10

Para C ++, intente usar std::string para "ABCDEFGHIJKLMNOPQRSTUVWXYZ" - en mi implementación string::find(const charT* s, size_type pos = 0) const calcula la longitud del argumento de cadena.

Answer 11

Parece que en nodejs mejor algoritmo para las subcadenas de búsqueda. Puedes implementarlo y probarlo.

Answer 12

Su código de prueba está comprobando un escenario patológico de excesiva concatenación de cadenas. (Probablemente se haya omitido la parte de búsqueda de cadenas de la prueba, apuesto a que no aporta casi nada a los resultados finales). La excesiva concatenación de cuerdas es una trampa con la que la mayoría de las lenguas advierten con fuerza, y proporciona alternativas muy conocidas para (es decir, StringBuilder), entonces lo que esencialmente está probando aquí es qué tan mal fallan estos lenguajes en escenarios de falla perfectamente esperada. Eso no tiene sentido.

Un ejemplo de una prueba igualmente sin sentido sería comparar el rendimiento de varios idiomas al lanzar y atrapar una excepción en un circuito cerrado. Todos los idiomas advierten que lanzar y atrapar excepciones es abismalmente lento. No especifican qué tan lento, solo te advierten que no esperes nada. Por lo tanto, seguir adelante y probar precisamente eso, sería inútil.

Por lo tanto, tendría mucho más sentido repetir la prueba sustituyendo la parte de concatenación de cuerdas sin sentido (s + = "X") con cualquier construcción que ofrezca cada uno de estos lenguajes precisamente para evitar la concatenación de cadenas. (Como clase StringBuilder)