ejemplo - C++ map<std:: string> vs map<char*> performance(lo sé, ¿otra vez?)

map iterator c++

Question

Estaba usando un mapa con una clave std::string y, aunque todo funcionaba bien, no estaba obteniendo el rendimiento que esperaba. Busqué lugares para optimizar y mejorar cosas solo un poco y fue cuando un colega dijo: "esa clave de cadena va a ser lenta".

Leí docenas de preguntas y constantemente dicen:

"no use un char * como clave"
" std::string keys nunca es tu cuello de botella"
"La diferencia de rendimiento entre un char * y un std::string es un mito".

A regañadientes probé una tecla de char * y había una diferencia, una gran diferencia.

Reduje el problema a un simple ejemplo:

#include <stdio.h>
#include <stdlib.h>
#include <map>

#ifdef USE_STRING

#include <string>
typedef std::map<std::string, int> Map;

#else

#include <string.h>
struct char_cmp { 
    bool operator () (const char *a,const char *b) const 
    {
        return strcmp(a,b)<0;
    } 
};
typedef std::map<const char *, int, char_cmp> Map;

#endif

Map m;

bool test(const char *s)
{
    Map::iterator it = m.find(s);
    return it != m.end();
}

int main(int argc, char *argv[])
{
    m.insert( Map::value_type("hello", 42) );

    const int lcount = atoi(argv[1]);
    for (int i=0 ; i<lcount ; i++) test("hello");
}

Primero la versión std :: string:

$ g++ -O3 -o test test.cpp -DUSE_STRING
$ time ./test 20000000
real    0m1.893s

Luego la versión ''char *'':

g++ -O3 -o test test.cpp             
$ time ./test 20000000
real    0m0.465s

Esa es una gran diferencia de rendimiento y la misma diferencia que veo en mi programa más grande.

Usar una tecla de char * es una molestia para manejar la liberación de la tecla y simplemente no se siente bien. Expertos en C ++ ¿Qué me estoy perdiendo? ¿Alguna idea o sugerencia?

Answer 1

Almacene std :: string como un puntero y luego pierda la sobrecarga del constructor de copia.

Pero después de que tenga que recordar manejar las eliminaciones.

La razón por la que std :: string es lenta es que se construye a sí misma. Llama al constructor de copia y luego al final llama a eliminar. Si crea la cadena en el montón, pierde la construcción de la copia.

Answer 2

Como se señaló, el problema es una de las especificaciones de los contenedores asociativos (conjuntos y mapas), en el sentido de que sus métodos de búsqueda de miembros siempre fuerzan una conversión a key_type , incluso si existe un operator< que aceptaría comparar su clave con las claves en el mapa a pesar de sus diferentes tipos.

Por otro lado, las funciones en <algorithm> no sufren de esto, por ejemplo lower_bound se define como:

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

Entonces, una alternativa podría ser:

std::vector< std::pair< std::string, int > >

Y luego podrías hacer:

std::lower_bound(vec.begin(), vec.end(), std::make_pair("hello", 0), CompareFirst{})

Donde CompareFirst se define como:

struct CompareFirst {
     template <typename T, typename U>
     bool operator()(T const& t, U const& u) const { return t.first < u.first; }
};

O incluso crea un comparador completamente personalizado (pero es un poco más difícil).

Un vector de par generalmente es más eficiente en cargas de lectura pesada, por lo que en realidad es para almacenar una configuración, por ejemplo.

Aconsejo proporcionar métodos para ajustar los accesos. lower_bound es bastante bajo nivel.

Answer 3

Después de la compilación, los 2 literales de cadena "Hello" tendrán la misma dirección de memoria. En el caso char * usa estas direcciones de memoria como claves.

En el caso de string , cada "Hola" se convertirá en un objeto diferente. Esta es una pequeña parte (realmente muy pequeña) de su diferencia de rendimiento.

Una parte más grande puede ser que como todos los "Hola" que está usando tiene la misma dirección de memoria, strcmp siempre obtendrá 2 punteros de caracteres equivalentes y estoy seguro de que comprueba temprano este caso :) Por lo tanto, nunca se repetirá realmente en todos los caracteres pero la comparación std :: string lo hará.

Answer 4

Está utilizando un const char * como una clave de búsqueda para find() . Para el mapa que contiene const char* este es el tipo correcto que find espera y la búsqueda se puede hacer directamente.

El mapa que contiene std::string espera que el parámetro de find() sea std::string , por lo que en este caso el const char* primero debe convertirse a std::string . Esta es probablemente la diferencia que estás viendo.

Answer 5

Si está en C ++ 11, no se llama al constructor de copia a menos que se cambie la cadena . Debido a que std :: string es una construcción C ++, se necesita al menos 1 desreferencia para obtener los datos de cadena.

Supongo que se tomará el tiempo en una desreferencia adicional (que si se realiza 10000 veces es costoso), y std :: string probablemente haga las comprobaciones del puntero nulo apropiadas, lo que de nuevo consume los ciclos.