Pourquoi la lecture des lignes depuis stdin est-elle beaucoup plus lente en C ++ qu'en Python?

Je voulais comparer les lignes de lecture des entrées de chaîne de stdin en utilisant Python et C ++ et j'ai été choqué de voir mon code C ++ s'exécuter un ordre de grandeur plus lentement que le code Python équivalent. Comme mon C ++ est rouillé et que je ne suis pas encore un expert Pythonista, dites-moi si je fais quelque chose de mal ou si je me méprends sur quelque chose.

(Réponse TLDR: incluez la déclaration: cin.sync_with_stdio(false)ou utilisez simplement à la fgetsplace.

Résultats TLDR: faites défiler jusqu'au bas de ma question et regardez le tableau.)

Code C ++:

#include <iostream>
#include <time.h>

using namespace std;

int main() {
    string input_line;
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    while (cin) {
        getline(cin, input_line);
        if (!cin.eof())
            line_count++;
    };

    sec = (int) time(NULL) - start;
    cerr << "Read " << line_count << " lines in " << sec << " seconds.";
    if (sec > 0) {
        lps = line_count / sec;
        cerr << " LPS: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

// Compiled with:
// g++ -O3 -o readline_test_cpp foo.cpp

Équivalent Python:

#!/usr/bin/env python
import time
import sys

count = 0
start = time.time()

for line in  sys.stdin:
    count += 1

delta_sec = int(time.time() - start_time)
if delta_sec >= 0:
    lines_per_sec = int(round(count/delta_sec))
    print("Read {0} lines in {1} seconds. LPS: {2}".format(count, delta_sec,
       lines_per_sec))

Voici mes résultats:

$ cat test_lines | ./readline_test_cpp
Read 5570000 lines in 9 seconds. LPS: 618889

$cat test_lines | ./readline_test.py
Read 5570000 lines in 1 seconds. LPS: 5570000

Je dois noter que j'ai essayé ceci sous Mac OS X v10.6.8 (Snow Leopard) et Linux 2.6.32 (Red Hat Linux 6.2). Le premier est un MacBook Pro, et le second est un serveur très costaud, pas que ce soit trop pertinent.

$ for i in {1..5}; do echo "Test run $i at `date`"; echo -n "CPP:"; cat test_lines | ./readline_test_cpp ; echo -n "Python:"; cat test_lines | ./readline_test.py ; done
Test run 1 at Mon Feb 20 21:29:28 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 2 at Mon Feb 20 21:29:39 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 3 at Mon Feb 20 21:29:50 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 4 at Mon Feb 20 21:30:01 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 5 at Mon Feb 20 21:30:11 EST 2012
CPP:   Read 5570001 lines in 10 seconds. LPS: 557000
Python:Read 5570000 lines in  1 seconds. LPS: 5570000

Petit addenda de référence et récapitulation

Pour être complet, j'ai pensé mettre à jour la vitesse de lecture du même fichier sur la même boîte avec le code C ++ d'origine (synchronisé). Encore une fois, c'est pour un fichier de ligne 100M sur un disque rapide. Voici la comparaison, avec plusieurs solutions / approches:

Implementation      Lines per second
python (default)           3,571,428
cin (default/naive)          819,672
cin (no sync)             12,500,000
fgets                     14,285,714
wc (not fair comparison)  54,644,808

Par défaut, cinest synchronisé avec stdio, ce qui lui permet d'éviter toute mise en mémoire tampon d'entrée. Si vous ajoutez ceci en haut de votre main, vous devriez voir des performances bien meilleures:

std::ios_base::sync_with_stdio(false);

Normalement, lorsqu'un flux d'entrée est mis en mémoire tampon, au lieu de lire un caractère à la fois, le flux sera lu en plus gros morceaux. Cela réduit le nombre d'appels système, qui sont généralement relativement coûteux. Cependant, étant donné que les FILE*bases stdioet iostreamsont souvent des implémentations distinctes et donc des tampons séparés, cela pourrait entraîner un problème si les deux étaient utilisés ensemble. Par exemple:

int myvalue1;
cin >> myvalue1;
int myvalue2;
scanf("%d",&myvalue2);

Si plus d'entrée a été lue cinque nécessaire, la deuxième valeur entière ne serait pas disponible pour la scanffonction, qui a son propre tampon indépendant. Cela conduirait à des résultats inattendus.

Pour éviter cela, par défaut, les flux sont synchronisés avec stdio. Une façon courante d'y parvenir est d'avoir cinlu chaque caractère un par un selon les besoins à l'aide des stdiofonctions. Malheureusement, cela introduit beaucoup de frais généraux. Pour de petites quantités d'entrée, ce n'est pas un gros problème, mais lorsque vous lisez des millions de lignes, la pénalité de performance est importante.

Heureusement, les concepteurs de la bibliothèque ont décidé que vous devriez également pouvoir désactiver cette fonctionnalité pour obtenir de meilleures performances si vous saviez ce que vous faisiez, ils ont donc fourni la sync_with_stdiométhode.

Par simple curiosité, j'ai jeté un œil à ce qui se passe sous le capot, et j'ai utilisé dtruss / strace à chaque test.

C ++

./a.out < in
Saw 6512403 lines in 8 seconds.  Crunch speed: 814050

appels système sudo dtruss -c ./a.out < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            6
pread                                           8
mprotect                                       17
mmap                                           22
stat64                                         30
read_nocancel                               25958

Python

./a.py < in
Read 6512402 lines in 1 seconds. LPS: 6512402

appels système sudo dtruss -c ./a.py < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            5
pread                                           8
mprotect                                       17
mmap                                           21
stat64                                         29

J'ai quelques années de retard ici, mais:

Dans 'Edit 4/5/6' du post d'origine, vous utilisez la construction:

$ /usr/bin/time cat big_file | program_to_benchmark

C'est faux de deux manières différentes:

1. Vous planifiez réellement l'exécution de cat, pas votre référence. L'utilisation du processeur «utilisateur» et «sys» affichée par timeest celle de cat, pas votre programme de référence. Pire encore, le temps «réel» n'est pas nécessairement précis. Selon l'implémentation de catet des pipelines dans votre système d'exploitation local, il est possible que le catdernier tampon géant soit écrit et se termine bien avant que le processus de lecture ne termine son travail.

2. L'utilisation de catest inutile et en fait contre-productive; vous ajoutez des pièces mobiles. Si vous étiez sur un système suffisamment ancien (c.-à-d. Avec un seul processeur et - dans certaines générations d'ordinateurs - des E / S plus rapides que le processeur) - le simple fait de catfonctionner pourrait considérablement colorer les résultats. Vous êtes également soumis à tout ce que la mise en mémoire tampon d'entrée et de sortie et tout autre traitement catpeuvent faire. (Cela vous gagnerait probablement un prix `` Utilisation inutile du chat '' si j'étais Randal Schwartz.

Une meilleure construction serait:

$ /usr/bin/time program_to_benchmark < big_file

Dans cette déclaration, c'est le shell qui ouvre big_file, en le passant à votre programme (enfin, timeauquel il exécute ensuite votre programme en tant que sous-processus) en tant que descripteur de fichier déjà ouvert. 100% de la lecture du fichier est strictement la responsabilité du programme que vous essayez de comparer. Cela vous donne une vraie lecture de ses performances sans complications parasites.

Je mentionnerai deux «correctifs» possibles, mais en fait erronés, qui pourraient également être pris en compte (mais je les «numérote» différemment car ce ne sont pas des choses qui étaient erronées dans le message d'origine):

A. Vous pouvez «corriger» cela en chronométrant uniquement votre programme:

$ cat big_file | /usr/bin/time program_to_benchmark

B. ou en chronométrant l'intégralité du pipeline:

$ /usr/bin/time sh -c 'cat big_file | program_to_benchmark'

Ce sont des erreurs pour les mêmes raisons que # 2: ils utilisent toujours catinutilement. Je les mentionne pour plusieurs raisons:

• ils sont plus «naturels» pour les personnes qui ne sont pas entièrement à l'aise avec les fonctions de redirection d'E / S du shell POSIX

• il peut y avoir des cas où cat est nécessaire (par exemple: le fichier à lire nécessite une sorte de privilège d'accès, et vous ne voulez pas accorder ce privilège au programme à benchmarkée: sudo cat /dev/sda | /usr/bin/time my_compression_test --no-output)

• dans la pratique , sur les machines modernes, l'ajout catdans le pipeline est probablement sans conséquence réelle.

Mais je dis cette dernière chose avec une certaine hésitation. Si nous examinons le dernier résultat dans «Edit 5» -

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU ...

- cela prétend avoir catconsommé 74% du CPU pendant le test; et en effet 1,34 / 1,83 est d'environ 74%. Peut-être une série de:

$ /usr/bin/time wc -l < temp_big_file

n'aurait pris que les 0,49 secondes restantes! Probablement pas: catici, il fallait payer pour les read()appels système (ou équivalent) qui ont transféré le fichier depuis le «disque» (en fait le cache de tampon), ainsi que le tube écrit pour les livrer wc. Le test correct aurait toujours dû faire ces read()appels; seuls les appels d'écriture sur le tuyau et de lecture sur le tuyau auraient été enregistrés, et ceux-ci devraient être assez bon marché.

Pourtant, je prédis que vous seriez en mesure de mesurer la différence entre cat file | wc -let wc -l < fileet de trouver une différence notable (pourcentage à 2 chiffres). Chacun des tests les plus lents aura payé une pénalité similaire en temps absolu; ce qui équivaudrait cependant à une fraction plus petite de son temps total plus grand.

En fait, j'ai fait quelques tests rapides avec un fichier d'ordures de 1,5 gigaoctet, sur un système Linux 3.13 (Ubuntu 14.04), obtenant ces résultats (ce sont en fait les «meilleurs des 3» résultats; après avoir amorcé le cache, bien sûr):

$ time wc -l < /tmp/junk
real 0.280s user 0.156s sys 0.124s (total cpu 0.280s)
$ time cat /tmp/junk | wc -l
real 0.407s user 0.157s sys 0.618s (total cpu 0.775s)
$ time sh -c 'cat /tmp/junk | wc -l'
real 0.411s user 0.118s sys 0.660s (total cpu 0.778s)

Notez que les deux résultats du pipeline prétendent avoir pris plus de temps CPU (utilisateur + sys) que le temps réel d'horloge murale. C'est parce que j'utilise la commande «time» intégrée du shell (bash), qui connaît le pipeline; et je suis sur une machine multicœur où des processus séparés dans un pipeline peuvent utiliser des cœurs distincts, accumulant du temps CPU plus rapidement qu'en temps réel. En utilisant /usr/bin/timeje vois un temps CPU plus petit qu'en temps réel - montrant qu'il ne peut chronométrer que l'élément de pipeline unique qui lui est passé sur sa ligne de commande. De plus, la sortie du shell donne des millisecondes alors qu'elle /usr/bin/timene donne que des centièmes de seconde.

Ainsi, au niveau de l'efficacité de wc -l, le catfait une énorme différence: 409/283 = 1,453 ou 45,3% de temps réel en plus, et 775/280 = 2,768, soit un énorme processeur utilisé de 177%! Sur ma boîte de test aléatoire, il était là au moment.

Je dois ajouter qu'il existe au moins une autre différence significative entre ces styles de test, et je ne peux pas dire s'il s'agit d'un avantage ou d'une faute; vous devez décider vous-même:

Lorsque vous exécutez cat big_file | /usr/bin/time my_program, votre programme reçoit des entrées d'un canal, à la vitesse précisément envoyée par cat, et en morceaux pas plus grands que ceux écrits par cat.

Lorsque vous exécutez /usr/bin/time my_program < big_file, votre programme reçoit un descripteur de fichier ouvert vers le fichier réel. Votre programme - ou dans de nombreux cas les bibliothèques d'E / S de la langue dans laquelle il a été écrit - peut prendre différentes mesures lorsqu'il est présenté avec un descripteur de fichier référençant un fichier standard. Il peut utiliser mmap(2)pour mapper le fichier d'entrée dans son espace d'adressage, au lieu d'utiliser des read(2)appels système explicites . Ces différences pourraient avoir un effet beaucoup plus important sur vos résultats de référence que le faible coût d'exécution du catbinaire.

Bien sûr, c'est un résultat de référence intéressant si le même programme fonctionne de manière sensiblement différente entre les deux cas. Il montre que, en effet, le programme ou ses bibliothèques d' E / S sont en train de faire quelque chose intéressant, comme l' utilisation mmap(). Donc, dans la pratique, il peut être judicieux d'exécuter les repères dans les deux sens; peut-être en escomptant le catrésultat par un petit facteur pour "pardonner" le coût de fonctionnement catlui-même.

J'ai reproduit le résultat original sur mon ordinateur en utilisant g ++ sur un Mac.

L'ajout des instructions suivantes à la version C ++ juste avant la whileboucle la met en ligne avec la version Python :

std::ios_base::sync_with_stdio(false);
char buffer[1048576];
std::cin.rdbuf()->pubsetbuf(buffer, sizeof(buffer));

sync_with_stdio a amélioré la vitesse à 2 secondes et la définition d'un tampon plus important l'a ramenée à 1 seconde.

getline, les opérateurs de flux scanf, peuvent être pratiques si vous ne vous souciez pas du temps de chargement des fichiers ou si vous chargez de petits fichiers texte. Mais, si les performances vous intéressent, vous devez vraiment simplement mettre tout le fichier en mémoire tampon (en supposant qu'il convienne).

Voici un exemple:

//open file in binary mode
std::fstream file( filename, std::ios::in|::std::ios::binary );
if( !file ) return NULL;

//read the size...
file.seekg(0, std::ios::end);
size_t length = (size_t)file.tellg();
file.seekg(0, std::ios::beg);

//read into memory buffer, then close it.
char *filebuf = new char[length+1];
file.read(filebuf, length);
filebuf[length] = '\0'; //make it null-terminated
file.close();

Si vous le souhaitez, vous pouvez envelopper un flux autour de ce tampon pour un accès plus pratique comme celui-ci:

std::istrstream header(&filebuf[0], length);

De plus, si vous contrôlez le fichier, envisagez d'utiliser un format de données binaires plat au lieu du texte. Il est plus fiable de lire et d'écrire car vous n'avez pas à gérer toutes les ambiguïtés des espaces blancs. Il est également plus petit et beaucoup plus rapide à analyser.

Le code suivant était plus rapide pour moi que l'autre code publié ici jusqu'à présent: (Visual Studio 2013, 64 bits, fichier de 500 Mo avec une longueur de ligne uniforme en [0, 1000)).

const int buffer_size = 500 * 1024;  // Too large/small buffer is not good.
std::vector<char> buffer(buffer_size);
int size;
while ((size = fread(buffer.data(), sizeof(char), buffer_size, stdin)) > 0) {
    line_count += count_if(buffer.begin(), buffer.begin() + size, [](char ch) { return ch == '\n'; });
}

Il bat toutes mes tentatives Python de plus d'un facteur 2.

Soit dit en passant, la raison pour laquelle le nombre de lignes pour la version C ++ est supérieur au nombre pour la version Python est que l'indicateur eof n'est défini que lorsqu'une tentative est effectuée pour lire au-delà de eof. La boucle correcte serait donc:

while (cin) {
    getline(cin, input_line);

    if (!cin.eof())
        line_count++;
};

Dans votre deuxième exemple (avec scanf ()), la raison pour laquelle cela est encore plus lent pourrait être parce que scanf ("% s") analyse la chaîne et recherche tout caractère d'espace (espace, tabulation, nouvelle ligne).

En outre, oui, CPython effectue une mise en cache pour éviter les lectures sur disque dur.

Un premier élément de réponse: <iostream>est lent. Zut lent. J'obtiens une énorme amélioration des performances avec scanfcomme ci-dessous, mais il est toujours deux fois plus lent que Python.

#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;

int main() {
    char buffer[10000];
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    int read = 1;
    while(read > 0) {
        read = scanf("%s", buffer);
        line_count++;
    };
    sec = (int) time(NULL) - start;
    line_count--;
    cerr << "Saw " << line_count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = line_count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } 
    else
        cerr << endl;
    return 0;
}

Eh bien, je vois que dans votre deuxième solution, vous êtes passé de cinà scanf, ce qui était la première suggestion que j'allais vous faire (cin is sloooooooooooow). Maintenant, si vous passez de scanfà fgets, vous verriez une autre amélioration des performances:fgets c'est la fonction C ++ la plus rapide pour l'entrée de chaîne.

BTW, je ne savais pas à propos de cette synchronisation, c'est bien. Mais vous devriez quand même essayer fgets.