c++ - Muy poco impulso:: rendimiento lexical_cast

boost lexical-cast

Question

Windows XP SP3. Core 2 Duo 2.0 GHz. Estoy descubriendo que el rendimiento de :: lexical_cast es extremadamente lento. Quería descubrir formas de acelerar el código. Usando las optimizaciones de O2 en Visual C ++ 2008 y comparando con Java 1.6 y Python 2.6.2 veo los siguientes resultados.

Encastre entero

c++:
std::string s ;
for(int i = 0; i < 10000000; ++i)
{
s = boost::lexical_cast<string>(i);
}
java:
String s = new String();
for(int i = 0; i < 10000000; ++i)
{
s = new Integer(i).toString();
}
python:
for i in xrange(1,10000000):
s = str(i)

Los tiempos que estoy viendo son

c ++: 6700 milisegundos

java: 1178 milisegundos

python: 6702 milisegundos

c ++ es tan lento como python y 6 veces más lento que java.

Doble casting:

c++:
std::string s ;
for(int i = 0; i < 10000000; ++i)
{
s = boost::lexical_cast<string>(d);
}
java:
String s = new String();
for(int i = 0; i < 10000000; ++i)
{
double d = i*1.0;
s = new Double(d).toString();
}
python:
for i in xrange(1,10000000):
d = i*1.0
s = str(d)

Los tiempos que estoy viendo son

c ++: 56129 milisegundos

java: 2852 milisegundos

python: 30780 milisegundos

¡Así que para los dobles, c ++ es en realidad la mitad de la velocidad de Python y 20 veces más lenta que la solución java !! ¿Alguna idea sobre cómo mejorar el impulso :: rendimiento lexical_cast? ¿Esto se deriva de la implementación de stringstream pobre o podemos esperar una disminución general de 10x en el rendimiento del uso de las bibliotecas de impulso.

Answer 1

Editar 2012-04-11

rve comentado correctamente sobre el rendimiento de lexical_cast, proporcionando un enlace:

boost.org/doc/libs/1_49_0/doc/html/boost_lexical_cast/…

No tengo acceso en este momento para aumentar 1.49, pero recuerdo haber acelerado mi código en una versión anterior. Entonces supongo

1. la siguiente respuesta sigue siendo válida (aunque solo sea con fines de aprendizaje)
2. probablemente hubo una optimización introducida en algún lugar entre las dos versiones (buscaré eso)
3. lo que significa que el impulso sigue mejorando y mejorando

Respuesta original

Solo para agregar información sobre las excelentes respuestas de Barry y Motti:

Algunos antecedentes

Recuerda que Boost está escrito por los mejores desarrolladores de C ++ en este planeta y revisado por los mismos mejores desarrolladores. Si lexical_cast estaba tan equivocado, alguien habría pirateado la biblioteca con críticas o con código.

Supongo que te perdiste el valor real de lexical_cast ...

Comparando manzanas y naranjas.

En Java, está convirtiendo un entero en una cadena Java. Notará que no estoy hablando de una matriz de caracteres o una cadena definida por el usuario. Notarás que no estoy hablando de tu número entero definido por el usuario. Estoy hablando del estricto Java Integer y el estricto Java String.

En Python, estás más o menos haciendo lo mismo.

Como se dijo en otras publicaciones, en esencia usas los equivalentes de sprintf de Java y Python (o menos itoa ).

En C ++, estás usando un elenco muy poderoso. No es poderoso en el sentido de rendimiento de velocidad cruda (si desea velocidad, tal vez sprintf sería más adecuado), pero poderoso en el sentido de extensibilidad.

Comparando manzanas.

Si desea comparar un método Java Integer.toString , entonces debe compararlo con las instalaciones C sprintf o C ++ ostream .

La solución de flujo de C ++ sería 6 veces más rápida (en mi g ++) que lexical_cast , y bastante menos extensible:

inline void toString(const int value, std::string & output)
{
// The largest 32-bit integer is 4294967295, that is 10 chars
// On the safe side, add 1 for sign, and 1 for trailing zero
char buffer[12] ;
sprintf(buffer, "%i", value) ;
output = buffer ;
}

La solución C sprintf sería 8 veces más rápida (en mi g ++) que lexical_cast pero mucho menos segura:

inline void toString(const int value, char * output)
{
sprintf(output, "%i", value) ;
}

Ambas soluciones son tan rápidas o más rápidas que su solución Java (según sus datos).

Comparando naranjas.

Si desea comparar un C ++ lexical_cast , entonces debe compararlo con este pseudo código de Java:

Source s ;
Target t = Target.fromString(Source(s).toString()) ;

La fuente y el destino son del tipo que desee, incluidos los tipos incorporados como boolean o int , que es posible en C ++ debido a las plantillas.

¿Extensibilidad? ¿Es esa una mala palabra?

No, pero tiene un costo bien conocido: cuando se escribe con el mismo codificador, las soluciones generales a problemas específicos suelen ser más lentas que las soluciones específicas escritas para sus problemas específicos.

En el caso actual, en un punto de vista ingenuo, lexical_cast usará las facilidades de flujo para convertir de un tipo A a un flujo de cadenas, y luego de este flujo de cadenas a un tipo B

Esto significa que, siempre que su objeto se pueda enviar a una transmisión y a una transmisión, podrá usar lexical_cast sin tocar ninguna línea de código.

Entonces, ¿cuáles son los usos de lexical_cast ?

Los principales usos de la fundición léxica son:

1. Facilidad de uso (¡hey, un elenco de C ++ que funciona para que todo sea un valor!)
2. Combínelo con código pesado de plantilla, donde sus tipos están parametrizados, y como tal, no desea tratar con detalles, y no quiere saber los tipos.
3. Todavía es potencialmente relativamente eficiente, si tiene conocimientos básicos de plantilla, como demostraré a continuación

El punto 2 es muy importante aquí, porque significa que tenemos una única interfaz / función para convertir un valor de un tipo en un valor igual o similar de otro tipo.

Este es el verdadero punto que te perdiste, y este es el punto que cuesta en términos de rendimiento.

Pero es tan slooooooowwww!

Si desea un rendimiento de velocidad sin formato, recuerde que está tratando con C ++, y que tiene muchas facilidades para manejar la conversión de manera eficiente, y aún así, mantener la lexical_cast facilidad de uso de lexical_cast .

Me llevó algunos minutos mirar la fuente lexical_cast y obtuve una solución viable. Agregue a su código C ++ el siguiente código:

#ifdef SPECIALIZE_BOOST_LEXICAL_CAST_FOR_STRING_AND_INT
namespace boost
{
template<>
std::string lexical_cast<std::string, int>(const int &arg)
{
// The largest 32-bit integer is 4294967295, that is 10 chars
// On the safe side, add 1 for sign, and 1 for trailing zero
char buffer[12] ;
sprintf(buffer, "%i", arg) ;
return buffer ;
}
}
#endif

Al habilitar esta especialización de lexical_cast para strings y ints (definiendo la macro SPECIALIZE_BOOST_LEXICAL_CAST_FOR_STRING_AND_INT ), mi código fue 5 veces más rápido en mi compilador de g ++, lo que significa que, de acuerdo con sus datos, su rendimiento debería ser similar al de Java.

Y me llevó 10 minutos mirar el código de impulso y escribir una versión de 32 bits remotamente eficiente y correcta. Y con algo de trabajo, probablemente podría ir más rápido y más seguro (si tuviéramos acceso directo de escritura al buffer interno std::string , podríamos evitar un buffer externo temporal, por ejemplo).

Answer 2

Como dijo Barry, lexical_cast es muy general, debería usar una alternativa más específica, por ejemplo, revisar itoa ( int->string ) y atoi ( string -> int ).

Answer 3

Lamentablemente, todavía no tengo suficientes representantes para comentar ...

lexical_cast no es principalmente lento porque es genérico (las búsquedas de plantillas ocurren en tiempo de compilación, por lo que no son necesarias las llamadas a funciones virtuales u otras búsquedas / referencias). lexical_cast es, en mi opinión, lento, porque se basa en iostremas de C ++, que están destinados principalmente a las operaciones de transmisión y no a las conversiones individuales, y porque lexical_cast debe verificar y convertir las señales de error iostream. Así:

• un objeto de secuencia debe ser creado y destruido
• en el caso de salida de cadena anterior, tenga en cuenta que los compiladores de C ++ tienen dificultades para evitar copias de búfer (una alternativa es formatear directamente en el búfer de salida, como sprintf , aunque sprintf no manejará de forma segura los desbordamientos de búfer)
• lexical_cast tiene que verificar si stringstream errores de stringstream de stringstream ( ss.fail() ) para lanzar excepciones en fallas de conversión

lexical_cast es agradable porque las excepciones (IMO) permiten atrapar todos los errores sin esfuerzo adicional y porque tienen un prototipo uniforme. No veo personalmente por qué estas propiedades requieren una operación lenta (cuando no se producen errores de conversión), aunque no conozco funciones C ++ tan rápidas (posiblemente Spirit o boost :: xpressive?).

Editar: Acabo de encontrar un mensaje que menciona el uso de BOOST_LEXICAL_CAST_ASSUME_C_LOCALE para habilitar una optimización "itoa": http://old.nabble.com/lexical_cast-optimization-td20817583.html . También hay un article vinculado con un poco más de detalle.

Answer 4

Lo que el reparto léxico está haciendo en tu código se puede simplificar a esto:

string Cast( int i ) {
ostringstream os;
os << i;
return os.str();
}

Desafortunadamente, suceden muchas cosas cada vez que llamas a Cast ():

• se crea una secuencia de cadenas posiblemente asignando memoria
• operador << para el entero i se llama
• el resultado se almacena en la secuencia, posiblemente asignando memoria
• una copia de cadena se toma de la secuencia
• una copia de la cadena es (posiblemente) creada para ser devuelta.
• la memoria está desasignada

En tu propio código:

 s = Cast( i );

la asignación implica asignaciones adicionales y se realizan desasignaciones. Puede reducir esto ligeramente al usar:

string s = Cast( i );

en lugar.

Sin embargo, si el rendimiento es realmente importante para usted, debe considerar usar un mecanismo diferente. Puede escribir su propia versión de Cast () que (por ejemplo) crea una secuencia de cadenas estática. Dicha versión no sería segura para subprocesos, pero podría no ser importante para sus necesidades específicas.

En resumen, lexical_cast es una característica conveniente y útil, pero dicha conveniencia viene (como siempre debe ser) con compensaciones en otras áreas.

Answer 5

Puede especializar lexical_cast para int y tipos double . Use strtod y strtol en sus especializaciones.

namespace boost {
template<>
inline int lexical_cast(const std::string& arg)
{
char* stop;
int res = strtol( arg.c_str(), &stop, 10 );
if ( *stop != 0 ) throw_exception(bad_lexical_cast(typeid(int), typeid(std::string)));
return res;
}
template<>
inline std::string lexical_cast(const int& arg)
{
char buffer[65]; // large enough for arg < 2^200
ltoa( arg, buffer, 10 );
return std::string( buffer ); // RVO will take place here
}
}//namespace boost
int main(int argc, char* argv[])
{
std::string str = "22"; // SOME STRING
int int_str = boost::lexical_cast<int>( str );
std::string str2 = boost::lexical_cast<std::string>( str_int );
return 0;
}

Esta variante será más rápida que la implementación predeterminada, porque en la implementación predeterminada hay construcción de objetos de flujo pesado. Y debe ser un poco más rápido que printf , porque printf debería analizar la cadena de formato.

Answer 6

Utilizo esta solución muy rápida para los tipos de POD ...

namespace DATATYPES {
typedef std::string TString;
typedef char* TCString;
typedef double TDouble;
typedef long THuge;
typedef unsigned long TUHuge;
};
namespace boost {
template<typename TYPE>
inline const DATATYPES::TString lexical_castNumericToString(
const TYPE& arg,
const DATATYPES::TCString fmt) {
enum { MAX_SIZE = ( std::numeric_limits<TYPE>::digits10 + 1 ) // sign
+ 1 }; // null
char buffer[MAX_SIZE] = { 0 };
if (sprintf(buffer, fmt, arg) < 0) {
throw_exception(bad_lexical_cast(typeid(TYPE),
typeid(DATATYPES::TString)));
}
return ( DATATYPES::TString(buffer) );
}
template<typename TYPE>
inline const TYPE lexical_castStringToNumeric(const DATATYPES::TString& arg) {
DATATYPES::TCString end = 0;
DATATYPES::TDouble result = std::strtod(arg.c_str(), &end);
if (not end or *end not_eq 0) {
throw_exception(bad_lexical_cast(typeid(DATATYPES::TString),
typeid(TYPE)));
}
return TYPE(result);
}
template<>
inline DATATYPES::THuge lexical_cast(const DATATYPES::TString& arg) {
return (lexical_castStringToNumeric<DATATYPES::THuge>(arg));
}
template<>
inline DATATYPES::TString lexical_cast(const DATATYPES::THuge& arg) {
return (lexical_castNumericToString<DATATYPES::THuge>(arg,"%li"));
}
template<>
inline DATATYPES::TUHuge lexical_cast(const DATATYPES::TString& arg) {
return (lexical_castStringToNumeric<DATATYPES::TUHuge>(arg));
}
template<>
inline DATATYPES::TString lexical_cast(const DATATYPES::TUHuge& arg) {
return (lexical_castNumericToString<DATATYPES::TUHuge>(arg,"%lu"));
}
template<>
inline DATATYPES::TDouble lexical_cast(const DATATYPES::TString& arg) {
return (lexical_castStringToNumeric<DATATYPES::TDouble>(arg));
}
template<>
inline DATATYPES::TString lexical_cast(const DATATYPES::TDouble& arg) {
return (lexical_castNumericToString<DATATYPES::TDouble>(arg,"%f"));
}
} // end namespace boost

Answer 7

si la velocidad es una preocupación, o si simplemente está interesado en qué tan rápido pueden ser esos moldes con C ++, hay un thread interesado al respecto.

Boost.Spirit 2.1 (que se lanzará con Boost 1.40) parece ser muy rápido, incluso más rápido que los equivalentes C (strtol (), atoi () etc.).

Answer 8

lexical_cast es más general que el código específico que estás usando en Java y Python. No es de extrañar que un enfoque general que funciona en muchos escenarios (el lanzamiento léxico sea poco más que la transmisión y luego volver hacia y desde un flujo temporal) termine siendo más lento que las rutinas específicas.

(Por cierto, puede obtener un mejor rendimiento de Java utilizando la versión estática, Integer.toString(int) . [1])

Finalmente, el análisis sintáctico y el deparsing no suelen ser sensibles al rendimiento, a menos que uno esté escribiendo un compilador, en cuyo caso lexical_cast es probablemente demasiado general, y los enteros, etc. se calcularán a medida que se escanea cada dígito.

[1] El comentarista "stepancheg" dudó de mi sugerencia de que la versión estática puede dar un mejor rendimiento. Aquí está la fuente que utilicé:

public class Test
{
static int instanceCall(int i)
{
String s = new Integer(i).toString();
return s == null ? 0 : 1;
}
static int staticCall(int i)
{
String s = Integer.toString(i);
return s == null ? 0 : 1;
}
public static void main(String[] args)
{
// count used to avoid dead code elimination
int count = 0;
// *** instance
// Warmup calls
for (int i = 0; i < 100; ++i)
count += instanceCall(i);
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; ++i)
count += instanceCall(i);
long finish = System.currentTimeMillis();
System.out.printf("10MM Time taken: %d ms/n", finish - start);
// *** static
// Warmup calls
for (int i = 0; i < 100; ++i)
count += staticCall(i);
start = System.currentTimeMillis();
for (int i = 0; i < 10000000; ++i)
count += staticCall(i);
finish = System.currentTimeMillis();
System.out.printf("10MM Time taken: %d ms/n", finish - start);
if (count == 42)
System.out.println("bad result"); // prevent elimination of count
}
}

Los tiempos de ejecución, utilizando JDK 1.6.0-14, servidor VM:

10MM Time taken: 688 ms
10MM Time taken: 547 ms

Y en el cliente VM:

10MM Time taken: 687 ms
10MM Time taken: 610 ms

Aunque teóricamente, el análisis de escape puede permitir la asignación en la pila, y la incorporación puede introducir todo el código (incluida la copia) en el método local, permitiendo la eliminación de la copia redundante, tal análisis puede llevar bastante tiempo y dar como resultado bastante espacio de código, que tiene otros costos en la memoria caché de código que no se justifican en código real, a diferencia de microbenchmarks como se ve aquí.

Answer 9

lexical_cast puede o no ser tan lento en relación con Java y Python como lo indican tus bencharks, porque tus mediciones de referencia pueden tener un problema sutil. Las asignaciones / desasignaciones de espacios de trabajo realizadas por léxico o los métodos iostream que utiliza se miden por sus puntos de referencia porque C ++ no difiere estas operaciones. Sin embargo, en el caso de Java y Python, las desasignaciones asociadas pueden, de hecho, haberse transferido a un futuro ciclo de recolección de basura y no haber sido detectadas por las mediciones de referencia. (A menos que ocurra un ciclo de GC por casualidad mientras el punto de referencia está en progreso y en ese caso estaría midiendo demasiado). Por lo tanto, es difícil saber con certeza sin examinar los detalles de las implementaciones de Java y Python cuánto debe atribuirse el "costo" a la carga del GC diferido que puede (o no) eventualmente imponerse.

Este tipo de problema, obviamente, se puede aplicar a muchos otros puntos de referencia del lenguaje recopilados en C ++ vs. basura.