Défi de la performance C++ : entier à la conversion de std::string

Question

N'importe qui peut battre la performance de mon entier à std::string code, en lien ci-dessous?

Il y a déjà plusieurs questions qui expliquent comment faire pour convertir un entier en std::string en C++, comme les ce l'un, mais aucune des solutions prévues sont efficaces.

Voici la compilation code prêt à l'emploi pour certaines méthodes courantes de compétition:

• Le "C++ voie", à l'aide de stringstream: http://ideone.com/jh3Sa
• sprintf, qui SOI-ers recommandent habituellement à la performance consciente: http://ideone.com/82kwR

Contrairement à la croyance populaire, boost::lexical_cast a sa propre mise en œuvre (livre blanc) et ne pas utiliser les stringstream numériques et de l'insertion des opérateurs. J'aimerais vraiment voir ses performances par rapport, parce que cette autre question suggère qu'il est misérable.

Et ma propre contribution, qui est concurrentiel sur les ordinateurs de bureau, et démontre une approche qui fonctionne à pleine vitesse sur des systèmes embarqués ainsi, à la différence des algorithmes dépend entier modulo:

• Ben algorithmes: http://ideone.com/SsEUW

Si vous souhaitez utiliser ce code, je vais le rendre disponible sous une licence BSD simplifiée (utilisation commerciale autorisée, l'attribution obligatoire). Il suffit de demander.

Enfin, la fonction ltoa non standard mais largement disponibles.

• ltoa version, pour n'importe qui qui a un compilateur qui le fournit (ideone ne marche pas): http://ideone.com/T5Wim

Je vais poster mes mesures de performance comme une réponse sous peu.

Règles pour les algorithmes

• Fournir le code lors de la conversion d'au moins 32 bits signés et non signés entiers en décimal.
• Produire en sortie un std::string.
• Pas de trucs qui sont incompatibles avec le filetage et les signaux (par exemple, statique tampons).
• Vous pouvez supposer un jeu de caractères ASCII.
• Assurez-vous de tester votre code sur INT_MIN sur un complément à deux de la machine où la valeur absolue n'est pas représentable.
• Idéalement, la sortie doit être au caractère identique avec les canonique de C++ version à l'aide d' stringstream, http://ideone.com/jh3Samais tout ce qui est tout à fait compréhensible que le nombre correct est ok aussi
• NOUVEAU: Même si vous pouvez utiliser n'importe quel compilateur et un optimiseur options (à l'exception complètement désactivé) que vous souhaitez pour le titre de comparaison, le code doit également de compiler et de donner les bons résultats sous VC++ 2010 et g++.

Espéré pour la Discussion

Outre de meilleurs algorithmes, je tiens également à obtenir certains tests sur plusieurs plates-formes différentes et les compilateurs (utilisons MO/s de débit que notre unité de mesure standard). Je crois que le code de mon algorithme (je sais que l' sprintf indice de référence prend quelques raccourcis -- maintenant corrigé) est bien comportement défini par la norme, au moins en vertu de l'ASCII hypothèse, mais si vous voyez un comportement indéfini ou des facteurs de production pour lequel la sortie est invalide, merci de le signaler.

Conclusions:

Différents algorithmes effectuer pour g++ et VC2010, probablement en raison de les différentes implémentations de l' std::string sur chaque. VC2010 clairement fait un meilleur travail avec NRVO, se débarrasser de retour par valeur, aidé seulement sur gcc.

Le Code a été constaté que dépasse sprintf par un ordre de grandeur. ostringstream tombe derrière par un facteur de 50 et plus.

Le gagnant du challenge est user434507 qui produit un code qui s'exécute à 350% de la vitesse de mon propre sur gcc. Les autres entrées sont fermées en raison des caprices de la communauté.

Le courant (finale?) la vitesse des champions sont:

• Pour gcc: user434507, à 8 fois plus rapide que l' sprintf: http://ideone.com/0uhhX
• Pour Visual C++: Timo, à 15 fois plus rapide 'sprintf': http://ideone.com/VpKO3

Answer 1

#include <string>

const char digit_pairs[201] = {
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899"
};


std::string& itostr(int n, std::string& s)
{
    if(n==0)
    {
        s="0";
        return s;
    }

    int sign = -(n<0);
    unsigned int val = (n^sign)-sign;

    int size;
    if(val>=10000)
    {
        if(val>=10000000)
        {
            if(val>=1000000000)
                size=10;
            else if(val>=100000000)
                size=9;
            else 
                size=8;
        }
        else
        {
            if(val>=1000000)
                size=7;
            else if(val>=100000)
                size=6;
            else
                size=5;
        }
    }
    else 
    {
        if(val>=100)
        {
            if(val>=1000)
                size=4;
            else
                size=3;
        }
        else
        {
            if(val>=10)
                size=2;
            else
                size=1;
        }
    }
    size -= sign;
    s.resize(size);
    char* c = &s[0];
    if(sign)
        *c='-';

    c += size-1;
    while(val>=100)
    {
       int pos = val % 100;
       val /= 100;
       *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
       c-=2;
    }
    while(val>0)
    {
        *c--='0' + (val % 10);
        val /= 10;
    }
    return s;
}

std::string& itostr(unsigned val, std::string& s)
{
    if(val==0)
    {
        s="0";
        return s;
    }

    int size;
    if(val>=10000)
    {
        if(val>=10000000)
        {
            if(val>=1000000000)
                size=10;
            else if(val>=100000000)
                size=9;
            else 
                size=8;
        }
        else
        {
            if(val>=1000000)
                size=7;
            else if(val>=100000)
                size=6;
            else
                size=5;
        }
    }
    else 
    {
        if(val>=100)
        {
            if(val>=1000)
                size=4;
            else
                size=3;
        }
        else
        {
            if(val>=10)
                size=2;
            else
                size=1;
        }
    }

    s.resize(size);
    char* c = &s[size-1];
    while(val>=100)
    {
       int pos = val % 100;
       val /= 100;
       *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
       c-=2;
    }
    while(val>0)
    {
        *c--='0' + (val % 10);
        val /= 10;
    }
    return s;
}

Cela permettra de sauter sur les systèmes qui ne permettent pas non alignés accès à la mémoire (dans ce cas, le premier non alignés affectation via *(short*) serait la cause d'une erreur de segmentation), mais devrait fonctionner très bien sinon.

Une chose importante à faire est de minimiser l'utilisation de std::string. (Ironique, je sais). Dans Visual Studio, par exemple, la plupart des appels à des méthodes de std::string ne sont pas inline, même si vous spécifiez /Ob2 dans les options du compilateur. Donc, même quelque chose d'aussi insignifiant qu'un appel à l' std::string::clear(), qui vous pourriez vous attendre à être très rapide, peut prendre 100 clockticks lors de la liaison CRT comme une bibliothèque statique, et autant de 300 clockticks lors de la liaison comme un DLL.

Pour la même raison, le retour par référence est préférable car elle évite une affectation, un constructeur et un destructeur.

Answer 2

Ah, génial défi en passant... j'ai eu beaucoup de plaisir avec cette.

J'ai deux algorithmes de présenter (le code est dans le bas si vous avez envie de sauter). Dans mes comparaisons j'ai besoin que la fonction renvoie une chaîne de caractères et qu'il peut manipuler int et unsigned int. Comparer des choses qui ne sont pas de construire une chaîne à ceux qui n'en n'a pas vraiment de sens.

Le premier est un plaisir de la mise en œuvre qui n'utilise pas du tout précalculées tables de recherche ou explicite division/modulo. Celui-ci est en concurrence avec les autres avec gcc et avec tous, mais Timo sur msvc (pour une bonne raison que je vais expliquer ci-dessous). Le second algorithme est mon effective de soumission pour les meilleures performances. Dans mes tests, il bat tous les autres sur gcc et msvc.

Je pense que je sais pourquoi certains résultats sur MSVC sont très bons. std::string a deux constructeurs std::string(char* str, size_t n)
et
std::string(ForwardIterator b, ForwardIterator e)
gcc fait la même chose pour les deux... qu'est-il utilise la deuxième de mettre en œuvre la première. Le premier constructeur peut être mis en œuvre de façon significative plus efficace que ça et que MSVC. L'autre avantage de ceci est que dans certains cas (comme mon code rapide et Timo du code), la chaîne constructeur peut être insérée. En fait, il suffit de commutation entre ces constructeurs dans MSVC est presque 2x différence pour mon code.

Mes résultats de tests de performances:

Code Sources:

- Voigt
- Timo
- ergosys
- user434507
- utilisateur-voigt-timo
- hopman-fun
- hopman-rapide

gcc 4.4.5 -O2 sur Ubuntu 10.10 64 bits, Core i5

hopman_fun: 124.688 MO/sec --- 8.020 s
hopman_fast: 137.552 MO/sec --- 7.270 s
voigt: 120.192 MO/sec --- 8.320 s
user_voigt_timo: 97.9432 MO/sec --- 10.210 s
timo: 120.482 MO/sec --- 8.300 s
utilisateur: 97.7517 MO/sec --- 10.230 s
ergosys: 101.42 MO/sec --- 9.860 s

MSVC 2010 64 bits /Ox sur Windows 7 64 bits, Core i5

hopman_fun: 127 MO/sec --- 7.874 s
hopman_fast: 259 MO/sec --- 3.861 s
voigt: 221.435 MO/sec --- 4.516 s
user_voigt_timo: 195.695 MO/sec --- 5.110 s
timo: 253.165 MO/sec --- 3.950 s
utilisateur: 212.63 MO/sec --- 4.703 s
ergosys: 78.0518 MO/sec --- 12.812 s

Voici quelques résultats de tests/calendrier-cadre sur ideone
http://ideone.com/XZRqp
Notez que ideone est un environnement 32 bits. Mes deux algorithmes en souffrir, mais hopman_fast est au moins toujours compétitifs.

À noter que pour ces deux ou de ne pas construire une chaîne, j'ai ajouté la fonction suivant le modèle:

template <typename T>
std::string itostr(T t) {
    std::string ret;
    itostr(t, ret);
    return ret;
}

Maintenant, pour mon code...d'abord le plaisir:

    // hopman_fun

template <typename T> 
T reduce2(T v) {
    T k = ((v * 410) >> 12) & 0x000F000F000F000Full;
    return (((v - k * 10) << 8) + k);
}

template <typename T>
T reduce4(T v) {
    T k = ((v * 10486) >> 20) & 0xFF000000FFull;
    return reduce2(((v - k * 100) << 16) + (k));
}

typedef unsigned long long ull;
inline ull reduce8(ull v) {
    ull k = ((v * 3518437209u) >> 45);
    return reduce4(((v - k * 10000) << 32) + (k));
}

template <typename T>
std::string itostr(T o) {
    union {
        char str[16];
        unsigned short u2[8];
        unsigned u4[4];
        unsigned long long u8[2];
    };

    unsigned v = o < 0 ? ~o + 1 : o;

    u8[0] = (ull(v) * 3518437209u) >> 45;
    u8[0] = (u8[0] * 28147497672ull);
    u8[1] = v - u2[3] * 100000000;

    u8[1] = reduce8(u8[1]);
    char* f;
    if (u2[3]) {
        u2[3] = reduce2(u2[3]);
        f = str + 6;
    } else {
        unsigned short* k = u4[2] ? u2 + 4 : u2 + 6;
        f = *k ? (char*)k : (char*)(k + 1);
    }
    if (!*f) f++;

    u4[1] |= 0x30303030;
    u4[2] |= 0x30303030;
    u4[3] |= 0x30303030;
    if (o < 0) *--f = '-';
    return std::string(f, (str + 16) - f);
}

Et puis le plus rapide:

    // hopman_fast

struct itostr_helper {
    static unsigned out[10000];

    itostr_helper() {
        for (int i = 0; i < 10000; i++) {
            unsigned v = i;
            char * o = (char*)(out + i);
            o[3] = v % 10 + '0';
            o[2] = (v % 100) / 10 + '0';
            o[1] = (v % 1000) / 100 + '0';
            o[0] = (v % 10000) / 1000;
            if (o[0]) o[0] |= 0x30;
            else if (o[1] != '0') o[0] |= 0x20;
            else if (o[2] != '0') o[0] |= 0x10;
            else o[0] |= 0x00;
        }
    }
};
unsigned itostr_helper::out[10000];

itostr_helper hlp_init;

template <typename T>
std::string itostr(T o) {
    typedef itostr_helper hlp;

    unsigned blocks[3], *b = blocks + 2;
    blocks[0] = o < 0 ? ~o + 1 : o;
    blocks[2] = blocks[0] % 10000; blocks[0] /= 10000;
    blocks[2] = hlp::out[blocks[2]];

    if (blocks[0]) {
        blocks[1] = blocks[0] % 10000; blocks[0] /= 10000;
        blocks[1] = hlp::out[blocks[1]];
        blocks[2] |= 0x30303030;
        b--;
    }

    if (blocks[0]) {
        blocks[0] = hlp::out[blocks[0] % 10000];
        blocks[1] |= 0x30303030;
        b--;
    }

    char* f = ((char*)b);
    f += 3 - (*f >> 4);

    char* str = (char*)blocks;
    if (o < 0) *--f = '-';
    return std::string(f, (str + 12) - f);
}

Answer 3

Données de référence pour le code fourni dans la question:

Sur ideone (gcc 4.3.4):

• stringstreams: 4.4 MB/s
• sprintf: 25.0 MB/s
• le mien (Ben Voigt): 55.8 MO/s
• Timo: 58.5 MO/s
• user434507: 199 MO/s
• user434507 Ben-Timo-507 hybride: 263 MO/s

Core i7, Windows 7 64 bits, 8 GO de RAM, Visual C++ 2010 32 bits:

cl /Ox /EHsc

• stringstreams: 3.39 MB/s, 3.67 MB/s
• sprintf: 16.8 MB/s, 16,2 MO/s
• la mienne: 194 MO/s, 207 MO/s (avec PGO activé: 250 MO/s)

Core i7, Windows 7 64 bits, 8 GO de RAM, Visual C++ 2010 64 bits:

cl /Ox /EHsc

• stringstreams: 4.42 MB/s, 4.92 MB/s
• sprintf: 21.0 MB/s, 20.8 MB/s
• la mienne: 238 MO/s, 228 MO/s

Core i7, Windows 7 64 bits, 8 GO de RAM, cygwin gcc 4.3.4:

g++ -O3

• stringstreams: 2.19 MB/s, 2.17 MB/s
• sprintf: 13.1 MB/s, 13.4 MB/s
• mine: 30.0 MB/s, 30.2 MB/s

edit: je vais ajouter ma propre réponse, mais la question a été a été fermé alors que je suis en ajoutant ici. :) J'ai écrit mon propre algorithme et a réussi à obtenir une bonne amélioration par rapport à Ben du code, si j'ai seulement testé en MSVC 2010. J'ai également fait un point de référence de toutes les implémentations présentées jusqu'à présent, en utilisant le même de la configuration du test qui était Ben le code original. -- Timo

Intel Q9450, Win XP 32bit, MSVC 2010

cl /O2 /EHsc

• stringstream: 2.87 MO/s
• sprintf: 16.1 MB/s
• Ben: 202 MO/s
• Ben (unsigned tampon): 82.0 MO/s
• ergosys (version mise à jour): 64.2 MB/s
• user434507: 172 MO/s
• Timo: 241 MO/s

-

const char digit_pairs[201] = {
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899"
};

static const int BUFFER_SIZE = 11;

std::string itostr(int val)
{
  char buf[BUFFER_SIZE];
  char *it = &buf[BUFFER_SIZE-2];

  if(val>=0) {
    int div = val/100;
    while(div) {
      memcpy(it,&digit_pairs[2*(val-div*100)],2);
      val = div;
      it-=2;
      div = val/100;
    }
    memcpy(it,&digit_pairs[2*val],2);
    if(val<10)
      it++;
  } else {
    int div = val/100;
    while(div) {
      memcpy(it,&digit_pairs[-2*(val-div*100)],2);
      val = div;
      it-=2;
      div = val/100;
    }
    memcpy(it,&digit_pairs[-2*val],2);
    if(val<=-10)
      it--;
    *it = '-';
  }

  return std::string(it,&buf[BUFFER_SIZE]-it);
}

std::string itostr(unsigned int val)
{
  char buf[BUFFER_SIZE];
  char *it = (char*)&buf[BUFFER_SIZE-2];

  int div = val/100;
  while(div) {
    memcpy(it,&digit_pairs[2*(val-div*100)],2);
    val = div;
    it-=2;
    div = val/100;
  }
  memcpy(it,&digit_pairs[2*val],2);
  if(val<10)
    it++;

  return std::string((char*)it,(char*)&buf[BUFFER_SIZE]-(char*)it);
}

Answer 4

Alors que l'info que nous avons ici pour les algorithmes est assez sympa, je pense que la question est "cassé", et je vais vous expliquer pourquoi je pense que c':

La question demande à prendre la performance de l' int->std::string de conversion, et ce peut être de l'intérêt lorsque l'on compare une méthode couramment disponibles, telles que les différents stringstream implémentations ou boost::lexical_cast. Il n'est pas, cependant, n'ont de sens au moment de demander un nouveau code, un algorithme spécialisé, pour ce faire. La raison en est que int2string impliquera toujours une allocation de tas de std::string et si nous sommes en train de presser le dernier à sortir de notre algorithme de conversion, je ne pense pas que cela a du sens de mélanger ces mesures avec les allocations de tas fait par std::string. Si je veux performant conversion je vais toujours utiliser un tampon de taille fixe et certainement jamais attribuer quoi que ce soit sur le tas!

Pour résumer, je pense que les horaires devraient être divisées en:

• Tout d'abord, le plus rapide (int -> mémoire tampon fixe) de conversion.
• Deuxièmement, le calendrier de l' (fixe tampon -> std::string) copie.
• Troisièmement, la vérification de la façon dont le std::string allocation peut être directement utilisé comme un tampon, pour enregistrer la copie.

Ces aspects ne doivent pas être mélangés dans un calendrier, à mon humble avis.

Answer 5

Je ne peux pas tester sous VS, mais cela semble être plus rapide que votre code de g ++, environ 10 %. Il pourrait sans doute être à l’écoute, l’élu de valeurs de décision est des suppositions. int uniquement, Désolé.