Pourquoi le fractionnement d'une chaîne est-il plus lent en C ++ qu'en Python?

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 en C ++. Hier, j'ai été choqué lorsqu'une implémentation naïve de lecture de lignes depuis stdin était beaucoup plus rapide en Python qu'en C ++ (voir ceci ). Aujourd'hui, j'ai enfin compris comment diviser une chaîne en C ++ avec des délimiteurs de fusion (sémantique similaire à celle de python split ()), et je fais maintenant l'expérience du déjà vu! Mon code C ++ prend beaucoup plus de temps pour faire le travail (mais pas un ordre de grandeur de plus, comme ce fut 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 séparées différentes. One (split1) utilise des méthodes de chaîne pour rechercher des jetons et est capable de fusionner plusieurs jetons ainsi que de gérer de nombreux jetons (cela vient d' ici ). Le second (split2) utilise getline pour lire la chaîne en tant que flux, ne fusionne pas les délimiteurs et ne prend en charge qu'un seul caractère de délimitation (celui-ci a été publié par plusieurs utilisateurs de StackOverflow dans les réponses aux questions de fractionnement de chaîne).

J'ai couru cela plusieurs fois dans divers ordres. Ma machine de test est un Macbook Pro (2011, 8 Go, Quad Core), pas que cela compte beaucoup. Je teste avec un fichier texte de 20 millions 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 mal? Existe-t-il un meilleur moyen de fractionner des chaînes en C ++ qui ne repose pas sur des bibliothèques externes (c'est-à-dire pas de boost), prend en charge la fusion de séquences de délimiteurs (comme le fractionnement de python), est thread-safe (donc pas de strtok), et dont les performances sont au moins à égalité avec python?

Modifier 1 / Solution partielle?:

J'ai essayé d'en faire une comparaison plus juste en demandant à python de réinitialiser la liste factice et de l'ajouter à 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. Fondamentalement, la boucle est maintenant:

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

Les performances de python sont désormais à 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 (comme Matt Joiner l'a suggéré), ces implémentations C ++ ne seraient pas plus rapides. Si quelqu'un a des idées sur la façon de faire cela de manière plus optimale en utilisant C ++, veuillez partager votre code. (Je pense que ma prochaine étape consistera à essayer de l'implémenter en C pur, bien que je ne fasse pas de compromis sur la productivité du programmeur pour réimplémenter mon projet global en C, donc ce ne sera qu'une expérience pour la vitesse de division des chaînes.)

Merci a tous pour votre aide.

Modification finale / solution:

Veuillez voir la réponse acceptée d'Alf. Étant donné que 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 vanilla. À titre de comparaison, j'ai compilé et exécuté mes données via le code d'Alf, et voici les performances sur la même machine que toutes les autres exécutions, essentiellement identiques à l'implémentation naïve de python (bien que plus rapide que l'implémentation de python qui réinitialise / ajoute la liste, comme montré 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

Mon seul petit reproche restant concerne la quantité de code nécessaire pour que C ++ fonctionne dans ce cas.

L'une des leçons tirées de ce numéro et du problème de lecture de la ligne stdin d'hier (lié ci-dessus) est qu'il faut toujours comparer au lieu de faire des hypothèses naïves sur les performances relatives "par défaut" des langues. J'apprécie l'éducation.

Merci encore à tous pour vos suggestions!

En guise de supposition, 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 C ++ std::stringest un type de valeur mutable et est copié à la moindre opportunité.

Si l'objectif est le fractionnement rapide, alors on utiliserait des opérations de sous-chaîne à temps constant, ce qui signifie se référer uniquement à des parties de la chaîne d'origine, comme en Python (et Java, et C #…).

La std::stringclasse C ++ a cependant une fonctionnalité de rachat: elle est standard , de sorte qu'elle peut être utilisée pour passer des chaînes en toute sécurité et de manière portable là où l'efficacité n'est pas une considération principale. Mais assez de discussion. Code - et sur ma machine, c'est bien sûr plus rapide que Python, car 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 bugs. Je n'ai pas testé la fonctionnalité, mais seulement vérifié la vitesse. Mais je pense que, même s'il y a un bug ou deux, une correction qui n'affectera pas significativement la vitesse.

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, en utilisant des chaînes de caractères pour les paramètres et fgetspour 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 horaires pour ceux-ci 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 tous ceux qui voudraient faire des tests supplémentaires, j'ai également mis en place un repo Github avec tous les programmes de la question, la réponse acceptée, cette réponse, ainsi qu'un Makefile et un script pour générer des données de test: https: // github. com / tobbez / division de chaîne .

Je soupçonne que c'est à cause de la façon dont std::vectorest redimensionné pendant le processus d'un appel de fonction push_back (). Si vous essayez d'utiliser std::listou std::vector::reserve()de 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 dummyest attribuée à chaque fois mais pas modifiée. Ce n'est donc pas une comparaison juste avec C ++. Vous devriez essayer de modifier votre code Python dummy = []pour l'initialiser, puis le faire dummy += line.split(). Pouvez-vous signaler le temps d'exécution après cela?

EDIT2 : Pour le rendre encore plus juste, vous pouvez modifier la boucle while dans le 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++;
    };

Je pense que le code suivant est meilleur, en utilisant certaines fonctionnalités C ++ 17 et C ++ 14:

// These codes are un-tested when I write this post, but I'll test it
// When I'm free, and I sincerely welcome others to test and modify this
// code.

// C++17
#include <istream>     // For std::istream.
#include <string_view> // new feature in C++17, sizeof(std::string_view) == 16 in libc++ on my x86-64 debian 9.4 computer.
#include <string>
#include <utility>     // C++14 feature std::move.

template <template <class...> class Container, class Allocator>
void split1(Container<std::string_view, Allocator> &tokens, 
            std::string_view str,
            std::string_view delimiter = " ") 
{
    /* 
     * The model of the input string:
     *
     * (optional) delimiter | content | delimiter | content | delimiter| 
     * ... | delimiter | content 
     *
     * Using std::string::find_first_not_of or 
     * std::string_view::find_first_not_of is a bad idea, because it 
     * actually does the following thing:
     * 
     *     Finds the first character not equal to any of the characters 
     *     in the given character sequence.
     * 
     * Which means it does not treeat your delimiters as a whole, but as
     * a group of characters.
     * 
     * This has 2 effects:
     *
     *  1. When your delimiters is not a single character, this function
     *  won't behave as you predicted.
     *
     *  2. When your delimiters is just a single character, the function
     *  may have an additional overhead due to the fact that it has to 
     *  check every character with a range of characters, although 
     * there's only one, but in order to assure the correctness, it still 
     * has an inner loop, which adds to the overhead.
     *
     * So, as a solution, I wrote the following code.
     *
     * The code below will skip the first delimiter prefix.
     * However, if there's nothing between 2 delimiter, this code'll 
     * still treat as if there's sth. there.
     *
     * Note: 
     * Here I use C++ std version of substring search algorithm, but u
     * can change it to Boyer-Moore, KMP(takes additional memory), 
     * Rabin-Karp and other algorithm to speed your code.
     * 
     */

    // Establish the loop invariant 1.
    typename std::string_view::size_type 
        next, 
        delimiter_size = delimiter.size(),  
        pos = str.find(delimiter) ? 0 : delimiter_size;

    // The loop invariant:
    //  1. At pos, it is the content that should be saved.
    //  2. The next pos of delimiter is stored in next, which could be 0
    //  or std::string_view::npos.

    do {
        // Find the next delimiter, maintain loop invariant 2.
        next = str.find(delimiter, pos);

        // Found a token, add it to the vector
        tokens.push_back(str.substr(pos, next));

        // Skip delimiters, maintain the loop invariant 1.
        //
        // @ next is the size of the just pushed token.
        // Because when next == std::string_view::npos, the loop will
        // terminate, so it doesn't matter even if the following 
        // expression have undefined behavior due to the overflow of 
        // argument.
        pos = next + delimiter_size;
    } while(next != std::string_view::npos);
}   

template <template <class...> class Container, class traits, class Allocator2, class Allocator>
void split2(Container<std::basic_string<char, traits, Allocator2>, Allocator> &tokens, 
            std::istream &stream,
            char delimiter = ' ')
{
    std::string<char, traits, Allocator2> item;

    // Unfortunately, std::getline can only accept a single-character 
    // delimiter.
    while(std::getline(stream, item, delimiter))
        // Move item into token. I haven't checked whether item can be 
        // reused after being moved.
        tokens.push_back(std::move(item));
}

Le choix du conteneur:

1. std::vector.

   En supposant que la taille initiale du tableau interne alloué est 1, et que la taille ultime est N, vous allouerez et désallouerez pour log2 (N) fois, et vous copiez le (2 ^ (log2 (N) + 1) - 1) = (2N - 1) fois. Comme indiqué dans La mauvaise performance de std :: vector est-elle due au fait de ne pas appeler realloc un nombre logarithmique de fois? , cela peut avoir de mauvaises performances lorsque la taille du vecteur est imprévisible et peut être très grande. Mais si vous pouvez en estimer la taille, ce sera moins un problème.

2. std::list.

   Pour chaque push_back, le temps qu'il a consommé est une constante, mais cela prendra probablement plus de temps que std :: vector sur un push_back individuel. L'utilisation d'un pool de mémoire par thread et d'un allocateur personnalisé peut résoudre ce problème.

3. std::forward_list.

   Identique à std :: list, mais occupe moins de mémoire par élément. Exiger qu'une classe wrapper fonctionne en raison de l'absence d'API push_back.

4. std::array.

   Si vous pouvez connaître la limite de croissance, vous pouvez utiliser std :: array. Bien sûr, vous ne pouvez pas l'utiliser directement, car il n'a pas l'API push_back. Mais vous pouvez définir un wrapper, et je pense que c'est le moyen le plus rapide ici et que vous pouvez économiser de la mémoire si votre estimation est assez précise.

5. std::deque.

   Cette option vous permet d'échanger de la mémoire contre des performances. Il n'y aura aucune copie (2 ^ (N + 1) - 1) fois de l'élément, juste N fois l'allocation et aucune désallocation. En outre, vous aurez un temps d'accès aléatoire constant et la possibilité d'ajouter de nouveaux éléments aux deux extrémités.

Selon std :: deque-cppreference

D'un autre côté, les deques ont généralement un coût de mémoire minimal élevé; un deque contenant un seul élément doit allouer son tableau interne complet (par exemple, 8 fois la taille de l'objet sur la libstdc ++ 64 bits; 16 fois la taille de l'objet ou 4096 octets, selon la valeur la plus grande, sur la libc ++ 64 bits)

ou vous pouvez utiliser une combinaison de ceux-ci:

1. std::vector< std::array<T, 2 ^ M> >

   Ceci est similaire à std :: deque, la différence est que ce conteneur ne prend pas en charge l'ajout d'élément à l'avant. Mais il est toujours plus rapide en termes de performances, car il ne copiera pas le std :: array sous-jacent pendant (2 ^ (N + 1) - 1) fois, il copiera simplement le tableau de pointeur pour (2 ^ (N - M + 1) - 1) fois, et allouer un nouveau tableau uniquement lorsque le courant est plein et n'a pas besoin de désallouer quoi que ce soit. En passant, vous pouvez obtenir un temps d'accès aléatoire constant.

2. std::list< std::array<T, ...> >

   Soulage grandement la pression de la framentation de la mémoire. Il n'allouera un nouveau tableau que lorsque le courant est plein et n'a pas besoin de copier quoi que ce soit. Vous devrez toujours payer le prix d'un pointeur supplémentaire comparé au combo 1.

3. std::forward_list< std::array<T, ...> >

   Identique à 2, mais coûte la même mémoire que le combo 1.

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

Si vous prenez l'implémentation split1 et modifiez la signature pour qu'elle corresponde plus étroitement à celle de split2, en changeant ceci:

void split1(vector<string> &tokens, const string &str, const string &delimiters = " ")

pour ça:

void split1(vector<string> &tokens, const string &str, const char delimiters = ' ')

Vous obtenez une différence plus dramatique entre split1 et split2, et une comparaison plus juste:

split1  C++   : Saw 10000000 lines in 41 seconds.  Crunch speed: 243902
split2  C++   : Saw 10000000 lines in 144 seconds.  Crunch speed: 69444
split1' C++   : Saw 10000000 lines in 33 seconds.  Crunch speed: 303030

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

Je soupçonne que cela est lié à la mise en mémoire tampon sur sys.stdin en Python, mais pas à la mise en mémoire tampon dans l'implémentation C ++.

Voir cet article pour plus de détails sur la façon de modifier la taille du tampon, puis réessayez la comparaison: Définition d'une taille de tampon plus petite pour sys.stdin?