Mauvaise boost::lexical_cast performance

Question

Windows XP SP3. Core 2 Duo 2.0 GHz. Je suis la recherche de la boost::lexical_cast performance extrêmement lent. Voulu trouver des moyens d'accélérer le code. À l'aide de /O2 optimisations sur visual c++ 2008 et en comparant avec la version 1.6 de java et python 2.6.2 je vois les résultats suivants.

Entier casting:

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)

La fois où je suis de voir

c++: 6700 millisecondes

java: 1178 millisecondes

python: 6702 millisecondes

c++ est aussi lent que python et 6 fois plus lent que java.

Double 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)

La fois où je suis de voir

c++: 56129 millisecondes

java: 2852 millisecondes

python: 30780 millisecondes

Donc, pour les doubles c++ est en fait la moitié de la vitesse de python et 20 fois plus lent que la solution java!!. Toutes les idées sur l'amélioration de la boost::lexical_cast la performance? Est-ce à la tige de la mauvaise stringstream mise en œuvre ou peut-on s'attendre à un général 10x diminution de performance de l'aide les bibliothèques boost.

Answer 1

Edit 2012-04-11

rve tout à fait, à juste titre, a commenté à ce sujet lexical_cast du rendement, de fournir un lien:

http://www.boost.org/doc/libs/1_49_0/doc/html/boost_lexical_cast/performance.html

Je n'ai pas le droit d'accès à dynamiser 1.49, mais je me souviens de rendre mon code plus rapide sur une version plus ancienne. Donc je suppose:

1. la réponse suivante est toujours valide (si ce n'est à des fins d'apprentissage)
2. il y avait probablement une optimisation introduit quelque part entre les deux versions (je vais rechercher)
3. ce qui signifie que boost est toujours de mieux en mieux

Réponse originale à cette question

Juste pour ajouter des informations sur Barry, et Il est d'excellentes réponses:

Certains d'arrière-plan

S'il vous plaît rappelez Boost est écrit par les meilleurs développeurs C++ sur cette planète, et examiné par les mêmes développeurs. Si lexical_cast a été si mal, quelqu'un aurait piraté la bibliothèque, soit à la critique, ou avec le code.

Je suppose que vous avez manqué le point de lexical_cast'la réelle valeur...

Comparer des pommes et des oranges.

En Java, vous lancez un sort d'un nombre entier en un Java Chaîne. Vous remarquerez que je ne parle pas d'un tableau de caractères, ou une chaîne définie par l'utilisateur. Vous remarquerez aussi, je ne parle pas de votre définis par l'utilisateur entier. Je parle de la stricte Java Entier et stricte Java Chaîne.

En Python, vous êtes plus ou moins faire la même chose.

Comme dit par d'autres postes, vous sont, en substance, à l'aide de Java et Python équivalents de sprintf (ou moins standard itoa).

En C++, vous êtes à l'aide d'un très puissant en fonte. Pas puissant dans le sens de la vitesse brute de performance (si vous voulez de la vitesse, peut - sprintf "conviendrait mieux), mais puissant dans le sens de l'extensibilité.

Comparer des pommes.

Si vous souhaitez comparer un Java Integer.toString méthode, alors vous devriez comparer avec C sprintf ou C++ ostream des installations.

Le C++ stream solution serait 6 fois plus rapide (sur mon g++) que lexical_cast, et tout à fait moins 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 ;
}

Le C sprintf solution serait 8 fois plus rapide (sur mon g++) que lexical_cast , mais beaucoup moins sûr:

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

Les deux solutions sont aussi vite ou plus vite que votre solution Java (en fonction de vos données).

Comparer des oranges.

Si vous souhaitez comparer un C++ lexical_cast, alors vous devriez comparer avec ce pseudo-code Java:

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

La Source et la Cible quel que soit le type que vous voulez, y compris les types intégrés comme boolean ou int, ce qui est possible en C++ parce que de modèles.

Extensibilité? C'est qu'un gros mot?

Non, mais elle a un coût connu: Lorsqu'il est écrit par le même codeur, général des solutions à des problèmes spécifiques sont généralement plus lentes que des solutions spécifiques à l'écrit de leurs problèmes spécifiques.

Dans le cas actuel, dans un point de vue naïf, lexical_cast vont utiliser le flux des installations de convertir d'un type A dans une chaîne de stream, et puis à partir de cette chaîne de flux dans un type B.

Cela signifie que tant que votre objet peut être sortie dans un cours d'eau, et d'entrée à partir d'un flux, vous serez en mesure d'utiliser lexical_cast - dessus, sans toucher une seule ligne de code.

Alors, quelles sont les utilisations de l' lexical_cast?

Les principales utilisations des lexicale casting sont:

1. La facilité d'utilisation (hey, C++ fonte qui fonctionne pour tout être qui a de la valeur!)
2. En la combinant avec le modèle lourd de code, où vos types sont paramétrés, et comme vous ne voulez pas avoir affaire avec des détails, et vous ne voulez pas connaître les types.
3. Toujours potentiellement relativement efficace, si vous avez un modèle de base de connaissances, comme je vais le démontrer ci-dessous

Le point 2 est très très important ici, car il signifie que nous avons une seule et unique interface/fonction pour lancer une valeur d'un type en une quantité égale ou similaire de la valeur d'un autre type.

C'est le point réel que vous avez manqué, et c'est le point que les coûts en termes de performances.

Mais c'est tellement slooooooowwww!

Si vous voulez premières performances de vitesse, n'oubliez pas que vous avez affaire avec le C++, et que vous avez beaucoup de facilités pour gérer la conversion de manière efficace, et encore, garder l' lexical_cast facilité d'utilisation de la fonctionnalité.

Il m'a fallu quelques minutes pour regarder le lexical_cast source, et venir avec une solution viable. Ajouter à votre code C++ le code suivant:

#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

En activant cette spécialisation de lexical_cast pour les cordes et les services de renseignements (par la définition de la macro SPECIALIZE_BOOST_LEXICAL_CAST_FOR_STRING_AND_INT), mon code est allé 5 fois plus rapide sur mon compilateur g++, ce qui signifie, selon vos données, son rendement devrait être similaire à Java.

Et il m'a fallu 10 minutes de regarder le code boost, et écrire une distance correcte et efficace de la version 32 bits. Et avec un peu de travail, il pourrait sans doute aller plus vite et plus sûr (si l'on a directement accès en écriture à l' std::string tampon interne, nous pourrions éviter temporaire externe de la mémoire tampon, par exemple).

Answer 2

Vous pourraient se spécialiser lexical_cast pour int et double types. Utiliser strtod et strtol dans vos spécialisations.

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;
}

Cette variante sera plus rapide que d'utiliser par défaut la mise en œuvre, car à défaut de la mise en œuvre des travaux de construction de lourds objets de flux. Et il devrait être un peu plus rapide que l' printfcar printf doit analyser la chaîne de format.

Answer 3

lexical_cast est plus général que le code spécifique que vous utilisez en Java et Python. Il n'est pas surprenant qu'une approche générale qui fonctionne dans de nombreux scénarios (lexicale cast est un peu plus que le streaming puis de retour vers et à partir d'un cours d'eau temporaire) finit par être plus lent que des routines.

(BTW, vous pouvez obtenir de meilleures performances de Java à l'aide de la version statique, Integer.toString(int). [1])

Enfin, le traitement de chaîne et deparsing est généralement pas que les performances sensibles, à moins que l'une est l'écriture d'un compilateur, auquel cas lexical_cast est probablement trop d'usage général, et les nombres entiers, etc. sera calculé comme chaque chiffre est numérisée.

[1] Auteur de "stepancheg" douté de mon soupçon que la version statique peut donner une meilleure performance. Voici le code source que j'ai utilisé:

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
    }
}

Le temps d'exécution, à l'aide du JDK 1.6.0-14, serveur de VM:

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

Et dans client VM:

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

Même si théoriquement, d'échapper à l'analyse peut permettre d'allocation sur la pile, et l'in-lining peut introduire la totalité du code (y compris la reproduction) dans les locaux de la méthode, permettant l'élimination de la redondance de la copie, une telle analyse peut prendre beaucoup de temps et le résultat tout à fait un peu de code de l'espace, qui a d'autres coûts dans le cache de code qui ne justifient pas en eux-mêmes dans le code réel, par opposition à microbenchmarks comme vu ici.

Answer 4

Malheureusement je n'ai pas assez de rep pas encore de commentaire...

lexical_cast n'est pas d'abord lent, car il est générique (template recherches se produire au moment de la compilation, de sorte que la fonction virtuelle appels ou d'autres recherches/déréférence ne sont pas nécessaires). lexical_cast est, à mon avis, lent, parce qu'il s'appuie sur le C++ iostreams, qui sont principalement destinés aux opérations de diffusion en continu et de ne pas les conversions, et parce qu' lexical_cast a l'obligation de contrôler et de les convertir iostream des signaux d'erreur. Donc:

• un objet de flux de données doit être créée et détruite
• dans la chaîne de sortie cas ci-dessus, notez que les compilateurs C++ ont du mal à éviter de tampon de copie (une alternative est de format directement à la sortie de la mémoire tampon, comme sprintf , si sprintf de ne pas manipuler de façon sécuritaire les dépassements de mémoire tampon)
• lexical_cast a vérifier pour stringstream d'erreurs (ss.fail()) afin de lever des exceptions sur les échecs de la conversion

lexical_cast , c'est agréable car (OMI) exceptions permettent le recouvrement de toutes les erreurs, sans effort supplémentaire, et parce qu'il a un uniforme prototype. Je n'ai pas personnellement de voir pourquoi l'une de ces propriétés nécessiter une opération lente (sans conversion des erreurs se produisent), mais je ne sais pas de telles fonctions C++ qui sont rapides (éventuellement Esprit ou boost::xpressive?).

Edit: je viens de trouver un message mentionnant l'utilisation de l' BOOST_LEXICAL_CAST_ASSUME_C_LOCALE afin de permettre une "ltid de" l'optimisation: http://old.nabble.com/lexical_cast-optimization-td20817583.html. Il y a également un lien d'article avec un peu plus de détail.