Pourquoi la division d'une chaîne de caractères est-elle plus lente en C++ qu'en Python ?

Question

J'essaie de convertir du code de Python en C++ dans le but de gagner un peu de vitesse et d'aiguiser mes compétences rouillées en C++. Hier, j'ai été choqué de constater qu'une implémentation naïve de la lecture de lignes depuis stdin était beaucoup plus rapide en Python qu'en C++ (cf. ce ). Aujourd'hui, j'ai finalement trouvé comment diviser une chaîne de caractères en C++ avec des délimiteurs de fusion (sémantique similaire à celle de split() de Python), et j'ai maintenant une expérience de déjà vu ! Mon code C++ prend beaucoup plus de temps pour faire le travail (mais pas un ordre de grandeur de plus, comme c'était le cas pour la leçon d'hier).

Code Python :

#!/usr/bin/env python
from __future__ import print_function                                            
import time
import sys

count = 0
start_time = time.time()
dummy = None

for line in sys.stdin:
    dummy = line.split()
    count += 1

delta_sec = int(time.time() - start_time)
print("Python: Saw {0} lines in {1} seconds. ".format(count, delta_sec), end='')
if delta_sec > 0:
    lps = int(count/delta_sec)
    print("  Crunch Speed: {0}".format(lps))
else:
    print('')

Code C++ :

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

void split1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    // Skip delimiters at beginning
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);

    // Find first non-delimiter
    string::size_type pos = str.find_first_of(delimiters, lastPos);

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the vector
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next non-delimiter
        pos = str.find_first_of(delimiters, lastPos);
    }
}

void split2(vector<string> &tokens, const string &str, char delim=' ') {
    stringstream ss(str); //convert string to stream
    string item;
    while(getline(ss, item, delim)) {
        tokens.push_back(item); //add token to vector
    }
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        spline.clear(); //empty the vector for the next line to parse

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        split2(spline, input_line);

        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp

Notez que j'ai essayé deux implémentations différentes du fractionnement. L'une d'entre elles (split1) utilise des méthodes de chaîne de caractères pour rechercher des tokens et est capable de fusionner plusieurs tokens ainsi que de gérer de nombreux tokens (elle provient de l'application ici ). La seconde (split2) utilise getline pour lire la chaîne en tant que flux, ne fusionne pas les délimiteurs, et ne supporte qu'un seul caractère de délimitation (celle-ci a été postée par plusieurs utilisateurs de StackOverflow en réponse à des questions sur la division des chaînes).

Je l'ai exécuté plusieurs fois dans des ordres différents. Ma machine de test est un Macbook Pro (2011, 8GB, Quad Core), pas que cela importe beaucoup. Je teste avec un fichier texte de 20M de lignes avec trois colonnes séparées par des espaces qui ressemblent chacune à ceci : "foo.bar 127.0.0.1 home.foo.bar"

Résultats :

$ /usr/bin/time cat test_lines_double | ./split.py
       15.61 real         0.01 user         0.38 sys
Python: Saw 20000000 lines in 15 seconds.   Crunch Speed: 1333333
$ /usr/bin/time cat test_lines_double | ./split1
       23.50 real         0.01 user         0.46 sys
C++   : Saw 20000000 lines in 23 seconds.  Crunch speed: 869565
$ /usr/bin/time cat test_lines_double | ./split2
       44.69 real         0.02 user         0.62 sys
C++   : Saw 20000000 lines in 45 seconds.  Crunch speed: 444444

Qu'est-ce que je fais de mal ? Existe-t-il une meilleure façon de diviser une chaîne de caractères en C++ qui ne dépende pas de bibliothèques externes (donc pas de boost), qui supporte la fusion de séquences de délimiteurs (comme le split de python), qui soit thread safe (donc pas de strtok), et dont les performances soient au moins équivalentes à celles de python ?

Edit 1 / Partial Solution? :

J'ai essayé de rendre la comparaison plus équitable en faisant en sorte que python réinitialise la liste fictive et l'ajoute à chaque fois, comme le fait C++. Ce n'est toujours pas exactement ce que fait le code C++, mais c'est un peu plus proche. En gros, la boucle est maintenant :

for line in sys.stdin:
    dummy = []
    dummy += line.split()
    count += 1

Les performances de python sont maintenant à peu près les mêmes que celles de l'implémentation C++ de split1.

/usr/bin/time cat test_lines_double | ./split5.py
       22.61 real         0.01 user         0.40 sys
Python: Saw 20000000 lines in 22 seconds.   Crunch Speed: 909090

Je suis toujours surpris que, même si Python est tellement optimisé pour le traitement des chaînes de caractères (comme Matt Joiner l'a suggéré), que ces implémentations C++ ne soient pas plus rapides. Si quelqu'un a des idées sur la façon de faire ceci de manière plus optimale en utilisant C++, merci de partager votre code. (Je pense que ma prochaine étape sera d'essayer d'implémenter ceci en C pur, bien que je ne vais pas troquer la productivité du programmeur pour ré-implémenter mon projet global en C, donc ce sera juste une expérience pour la vitesse de séparation des chaînes).

Merci à tous pour votre aide.

Final Edit/Solution :

Veuillez consulter la réponse acceptée d'Alf. Comme python traite les chaînes strictement par référence et que les chaînes STL sont souvent copiées, les performances sont meilleures avec les implémentations python vanille. A titre de comparaison, j'ai compilé et exécuté mes données avec le code d'Alf, et voici les performances sur la même machine que toutes les autres exécutions, essentiellement identiques à l'implémentation python naïve (bien que plus rapide que l'implémentation python qui réinitialise/applique la liste, comme indiqué dans l'édition ci-dessus) :

$ /usr/bin/time cat test_lines_double | ./split6
       15.09 real         0.01 user         0.45 sys
C++   : Saw 20000000 lines in 15 seconds.  Crunch speed: 1333333

Le seul petit reproche qui me reste concerne la quantité de code nécessaire pour que le C++ fonctionne dans ce cas.

L'une des leçons tirées de ce problème et de celui de la lecture de la ligne stdin d'hier (lien ci-dessus) est qu'il faut toujours procéder à une évaluation comparative au lieu de faire des suppositions naïves sur les performances relatives "par défaut" des langues. J'apprécie cette leçon.

Merci encore à tous pour vos suggestions !

Answer 1

À titre d'information, les chaînes Python sont des chaînes immuables comptées par référence, de sorte qu'aucune chaîne n'est copiée dans le code Python, tandis que les chaînes C++ sont des chaînes immuables. std::string est un type de valeur mutable, et est copié à la moindre occasion.

Si l'objectif est un fractionnement rapide, alors on utilisera des opérations de sous-chaînes en temps constant, ce qui signifie que seulement référant à des parties de la chaîne originale, comme en Python (et Java, et C# ).

Le C++ std::string a cependant un avantage : elle est standard Il peut donc être utilisé pour faire passer des chaînes de caractères en toute sécurité et de manière portable dans les endroits où l'efficacité n'est pas une considération majeure. Mais assez discuté. Le code -- et sur ma machine, c'est bien sûr plus rapide que Python, puisque la gestion des chaînes de Python est implémentée en C qui est un sous-ensemble de C++ (he he) :

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

class StringRef
{
private:
    char const*     begin_;
    int             size_;

public:
    int size() const { return size_; }
    char const* begin() const { return begin_; }
    char const* end() const { return begin_ + size_; }

    StringRef( char const* const begin, int const size )
        : begin_( begin )
        , size_( size )
    {}
};

vector<StringRef> split3( string const& str, char delimiter = ' ' )
{
    vector<StringRef>   result;

    enum State { inSpace, inToken };

    State state = inSpace;
    char const*     pTokenBegin = 0;    // Init to satisfy compiler.
    for( auto it = str.begin(); it != str.end(); ++it )
    {
        State const newState = (*it == delimiter? inSpace : inToken);
        if( newState != state )
        {
            switch( newState )
            {
            case inSpace:
                result.push_back( StringRef( pTokenBegin, &*it - pTokenBegin ) );
                break;
            case inToken:
                pTokenBegin = &*it;
            }
        }
        state = newState;
    }
    if( state == inToken )
    {
        result.push_back( StringRef( pTokenBegin, &*str.end() - pTokenBegin ) );
    }
    return result;
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        //spline.clear(); //empty the vector for the next line to parse

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        //split2(spline, input_line);

        vector<StringRef> const v = split3( input_line );
        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp -std=c++0x

Avertissement : J'espère qu'il n'y a pas de bogues. Je n'ai pas testé la fonctionnalité, mais seulement la vitesse. Mais je pense que, même s'il y a un ou deux bugs, leur correction n'affectera pas de manière significative la vitesse.

Answer 2

Je ne propose pas de meilleures solutions (du moins en termes de performances), mais des données supplémentaires qui pourraient être intéressantes.

Utilisation de strtok_r (variante réentrante de strtok ) :

void splitc1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    char *saveptr;
    char *cpy, *token;

    cpy = (char*)malloc(str.size() + 1);
    strcpy(cpy, str.c_str());

    for(token = strtok_r(cpy, delimiters.c_str(), &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters.c_str(), &saveptr)) {
        tokens.push_back(string(token));
    }

    free(cpy);
}

En outre, l'utilisation de chaînes de caractères pour les paramètres, et fgets pour la saisie :

void splitc2(vector<string> &tokens, const char *str,
        const char *delimiters) {
    char *saveptr;
    char *cpy, *token;

    cpy = (char*)malloc(strlen(str) + 1);
    strcpy(cpy, str);

    for(token = strtok_r(cpy, delimiters, &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters, &saveptr)) {
        tokens.push_back(string(token));
    }

    free(cpy);
}

Et, dans certains cas, où la destruction de la chaîne d'entrée est acceptable :

void splitc3(vector<string> &tokens, char *str,
        const char *delimiters) {
    char *saveptr;
    char *token;

    for(token = strtok_r(str, delimiters, &saveptr);
        token != NULL;
        token = strtok_r(NULL, delimiters, &saveptr)) {
        tokens.push_back(string(token));
    }
}

Les délais sont les suivants (y compris mes résultats pour les autres variantes de la question et la réponse acceptée) :

split1.cpp:  C++   : Saw 20000000 lines in 31 seconds.  Crunch speed: 645161
split2.cpp:  C++   : Saw 20000000 lines in 45 seconds.  Crunch speed: 444444
split.py:    Python: Saw 20000000 lines in 33 seconds.  Crunch Speed: 606060
split5.py:   Python: Saw 20000000 lines in 35 seconds.  Crunch Speed: 571428
split6.cpp:  C++   : Saw 20000000 lines in 18 seconds.  Crunch speed: 1111111

splitc1.cpp: C++   : Saw 20000000 lines in 27 seconds.  Crunch speed: 740740
splitc2.cpp: C++   : Saw 20000000 lines in 22 seconds.  Crunch speed: 909090
splitc3.cpp: C++   : Saw 20000000 lines in 20 seconds.  Crunch speed: 1000000

Comme nous pouvons le voir, la solution de la réponse acceptée est toujours la plus rapide.

Pour ceux qui voudraient faire d'autres tests, j'ai également mis en place un repo Github avec tous les programmes de la question, la réponse acceptée, cette réponse, et en plus un Makefile et un script pour générer des données de test : https://github.com/tobbez/string-splitting .

Answer 3

Je pense que c'est à cause de la façon dont std::vector est redimensionné au cours d'un appel à la fonction push_back(). Si vous essayez d'utiliser std::list ou std::vector::reserve() pour réserver suffisamment d'espace pour les phrases, vous devriez obtenir de bien meilleures performances. Ou vous pouvez utiliser une combinaison des deux comme ci-dessous pour split1() :

void split1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    // Skip delimiters at beginning
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);

    // Find first non-delimiter
    string::size_type pos = str.find_first_of(delimiters, lastPos);
    list<string> token_list;

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the list
        token_list.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next non-delimiter
        pos = str.find_first_of(delimiters, lastPos);
    }
    tokens.assign(token_list.begin(), token_list.end());
}

EDIT : L'autre chose évidente que je vois est que la variable Python dummy obtient assigné à chaque fois mais non modifié. Ce n'est donc pas une comparaison équitable avec le C++. Vous devriez essayer de modifier votre code Python pour qu'il soit dummy = [] pour l'initialiser et ensuite faire dummy += line.split() . Pouvez-vous indiquer le temps d'exécution après cela ?

EDIT2 : Pour être encore plus équitable pouvez-vous modifier la boucle while en code C++ pour qu'elle soit :

    while(cin) {
        getline(cin, input_line);
        std::vector<string> spline; // create a new vector

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        split2(spline, input_line);

        count++;
    };

Answer 4

Vous faites l'hypothèse erronée que l'implémentation C++ que vous avez choisie est nécessairement plus rapide que celle de Python. La gestion des chaînes de caractères en Python est hautement optimisée. Voir cette question pour en savoir plus : Pourquoi les opérations std::string sont-elles peu performantes ?

Answer 5

void split5(vector<string> &tokens, const string &str, char delim=' ') {

    enum { do_token, do_delim } state = do_delim;
    int idx = 0, tok_start = 0;
    for (string::const_iterator it = str.begin() ; ; ++it, ++idx) {
        switch (state) {
            case do_token:
                if (it == str.end()) {
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                    return;
                }
                else if (*it == delim) {
                    state = do_delim;
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                }
                break;

            case do_delim:
                if (it == str.end()) {
                    return;
                }
                if (*it != delim) {
                    state = do_token;
                    tok_start = idx;
                }
                break;
        }
    }
}