Pourquoi la lecture des lignes à partir de stdin beaucoup plus lent en C++ que Python?

Question

J'ai voulu comparer la lecture des lignes de la chaîne d'entrée à partir de stdin à l'aide de Python et C++ et a été choqué de voir mon code C++ exécuter un ordre de grandeur inférieure à celle de l'équivalent du code Python. Depuis mon C++ est rouillé et je ne suis pas encore un expert Pythonista, s'il vous plaît dites-moi si je fais quelque chose de mal ou si je suis un malentendu quelque chose.

---

(tl;dr réponse: inclure l'énoncé: cin.sync_with_stdio(false), ou simplement utiliser fgets à la place.

tl;dr résultats: faites défiler tout le chemin vers le bas de ma question et de regarder le tableau.)

---

Le 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

Python Équivalent:

#!/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

Merci à l'avance!

Edit: je tiens à noter que j'ai essayé cette fois sous OS-X (10.6.8) et Linux 2.6.32 (RHEL 6.2). Le premier est un macbook pro, ce dernier est un très costaud serveur, pas qu'il est trop pertinent.

Edit 2: (Supprimé cette édition, qui n'est plus applicable)

$ 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

Edit 3:

Bon, j'ai essayé de J. N. la suggestion d'essayer d'avoir python magasin de la ligne de lire: mais il ne fait aucune différence python vitesse.

J'ai aussi essayé J. N. la suggestion de l'utilisation de scanf dans un char tableau au lieu de getline dans un std::string. Bingo! Cela a abouti à des performances équivalentes pour les deux python et c++. (3,333,333 LPS avec mes données d'entrée, qui sont tout juste en deçà des lignes de trois champs de chaque, habituellement d'environ 20 caractères de large, et parfois plus).

Code:

char input_a[512];
char input_b[32];
char input_c[512];
while(scanf("%s %s %s\n", input_a, input_b, input_c) != EOF) {             
    line_count++;
};

Vitesse:

$ cat test_lines | ./readline_test_cpp2 
Read 10000000 lines in 3 seconds. LPS: 3333333
$ cat test_lines | ./readline_test2.py 
Read 10000000 lines in 3 seconds. LPS: 3333333

(Oui, j'ai couru plusieurs fois.) Donc, je pense que je vais maintenant utiliser scanf au lieu de getline. Mais, je suis toujours curieux de savoir si les gens pensent que ce gain de performance de std::string/getline est typique et raisonnable.

Edit 4 (a: Final Edition / Solution):

En ajoutant: cin.sync_with_stdio(false);

Immédiatement au-dessus de ma boucle while résultats ci-dessus dans le code qui s'exécute plus rapidement que Python.

Nouvelle comparaison des performances (c'est sur mon Macbook Pro 2011), avec le code d'origine, l'original avec la synchronisation désactivée, et l'original python, respectivement, sur un fichier avec 20M de lignes de texte. Oui, j'ai couru plusieurs fois pour éliminer le cache disque confondre.

$ /usr/bin/time cat test_lines_double | ./readline_test_cpp
       33.30 real         0.04 user         0.74 sys
Read 20000001 lines in 33 seconds. LPS: 606060
$ /usr/bin/time cat test_lines_double | ./readline_test_cpp1b
        3.79 real         0.01 user         0.50 sys
Read 20000000 lines in 4 seconds. LPS: 5000000
$ /usr/bin/time cat test_lines_double | ./readline_test.py 
        6.88 real         0.01 user         0.38 sys
Read 20000000 lines in 6 seconds. LPS: 3333333

Grâce à @Vaughn Cato pour sa réponse! Toute élaboration de gens peuvent faire ou de bonnes références les gens peuvent point à la raison pour laquelle cette synchronisation se passe, ce que cela signifie, lorsque c'est utile, et quand c'est ok pour désactiver serait grandement apprécié par la postérité. :-)

Edit 5 / Une Meilleure Solution:

Comme suggéré par Gandalf Le Gris ci-dessous, est même plus rapidement que scanf ou la désynchronisation du cin approche. J'ai aussi appris que le scanf et obtient sont à la fois DANGEREUX et ne doit PAS ÊTRE UTILISÉ en raison du risque de dépassement de la mémoire tampon. Alors, j'ai écrit cette itération en utilisant fgets, l'alternative plus sûre aux gets. Voici les lignes de mes collègues noobs:

char input_line[MAX_LINE];
char *result;

//<snip>

while((result = fgets(input_line, MAX_LINE, stdin )) != NULL)    
    line_count++;
if (ferror(stdin))
    perror("Error reading stdin.");

Maintenant, voici les résultats à l'aide d'un même fichier de plus grande taille (100 M lignes; ~3,4 GO) sur un serveur rapide à très rapide du disque, en comparant le python, le unsynced cin, et le fgets approches, ainsi que la comparaison avec les wc de l'utilitaire. [Le scanf version segfaulted et je n'ai pas envie de dépannage.]:

$ /usr/bin/time cat temp_big_file | readline_test.py 
0.03user 2.04system 0:28.06elapsed 7%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 28 seconds. LPS: 3571428

$ /usr/bin/time cat temp_big_file | readline_test_unsync_cin 
0.03user 1.64system 0:08.10elapsed 20%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 8 seconds. LPS: 12500000

$ /usr/bin/time cat temp_big_file | readline_test_fgets 
0.00user 0.93system 0:07.01elapsed 13%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 7 seconds. LPS: 14285714

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
100000000


Recap (lines per second):
python:         3,571,428 
cin (no sync): 12,500,000
fgets:         14,285,714
wc:            54,644,808

Comme vous pouvez le voir, fgets est mieux, mais encore assez loin de wc performance; je suis sûr que cela est dû au fait que les wc examine chaque personnage, sans aucun souvenir de la copie. Je soupçonne que, à ce stade, d'autres parties du code va devenir le goulot d'étranglement, donc je ne pense pas que l'optimisation à ce niveau même de la peine, même si c'est possible (car, après tout, j'ai réellement besoin de stocker la lecture des lignes de la mémoire).

Notez également qu'un petit compromis avec l'aide d'un char * buffer et fgets vs unsynced cin de chaîne est que cette dernière peut lire les lignes de n'importe quelle longueur, alors que les anciennes impose de limiter l'entrée à certains nombre fini. Dans la pratique, ce n'est probablement pas un problème pour la lecture de la plupart de la ligne de base de fichiers d'entrée, le tampon peut être réglé à une valeur très élevée qui ne pourrait être dépassé par d'entrée valide.

Cela a été instructif. Merci à tous pour vos commentaires et vos suggestions.

Edit 6:

Comme l'a suggéré J. F. Sebastian dans les commentaires ci-dessous, la GNU wc utilitaire utilise la plaine C read() (dans le coffre-lire.c wrapper) pour la lecture de morceaux (de 16 k octets) à un moment, et le comte de nouvelles lignes. Voici un python équivalent basé sur J. F. code (juste montrer pertinentes de l'extrait de code qui remplace le python la boucle for:

BUFFER_SIZE = 16384 
count = sum(chunk.count('\n') for chunk in iter(partial(sys.stdin.read, BUFFER_SIZE), ''))

Les performances de cette version est assez rapide (bien que toujours un peu plus lent que le c brutes wc utilitaire, bien sûr:

$ /usr/bin/time cat temp_big_file | readline_test3.py 
0.01user 1.16system 0:04.74elapsed 24%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 4.7275 seconds. LPS: 21152829

Encore une fois, c'est un peu idiot de me comparer C++ fgets/cin et le premier code python d'une part, de wc-l et ce dernier extrait python sur l'autre, comme les deux derniers ne stockent pas réellement la lecture des lignes, mais simplement de compter les retours à la ligne. Pourtant, il est intéressant d'explorer toutes les différentes implémentations et de réfléchir à l'incidence sur les performances. Merci encore!

Edit 7: un petit indice additif et le reboucher

(Bonjour HN lecteurs!)

Pour être complet, je pensais que je mettrais à jour la vitesse de lecture pour le même fichier sur la même case avec l'original (synchronisés) du code C++. Encore une fois, c'est pour un 100M de la ligne de fichier sur un disque rapide. Voici le tableau complet maintenant:

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

Aussi, voir mon suivi de question sur le fractionnement des lignes en C++ vs Python... une vitesse similaire histoire, où l'approche naïve est plus lente en C++!

Edit: pour plus de clarté, enlevé tout petit bug dans le code d'origine qui n'était pas liée à la question. Enfin, de petits réglages à l'espace blanc et de sortie des chaînes de rendre la comparaison plus facile/plus clair.

Answer 1

Par défaut, cin est synchronisé avec stdio, ce qui provoque à éviter toute entrée mise en mémoire tampon. Si vous ajoutez à cela le dessus de votre main, vous devriez voir beaucoup de meilleures performances:

cin.sync_with_stdio(false);

Normalement, lorsqu'un flux d'entrée est mis en mémoire tampon, au lieu de lire les caractères un à un, les flux seront lus en plus gros morceaux. Cela réduit le nombre d'appels système, qui sont en général relativement cher. Cependant, depuis le FICHIER* basé stdio et iostreams ont souvent des implémentations distinctes et donc se séparer des tampons, ce qui pourrait conduire à un problème si les deux sont utilisés ensemble. Par exemple:

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

Si plus d'entrée a été lu par cin que nécessaire, puis de la deuxième valeur entière ne serait pas disponible pour la fonction scanf, qui a son propre tampon. Cela permettrait d'aboutir à des résultats inattendus.

Pour éviter cela, par défaut, les flux sont synchronisés avec stdio. Une commune de la manière d'y parvenir est d'avoir cin lire chaque caractère un à un, en tant que de besoin à l'aide de fonctions de stdio. Malheureusement, ce qui introduit une surcharge importante. Pour les petits montants de l'entrée, ce n'est pas un gros problème, mais lorsque vous lisez des millions de lignes, la perte de performance est importante.

Heureusement, la bibliothèque de créateurs ont décidé que vous devez également être en mesure de désactiver cette fonction pour obtenir une performance améliorée si vous saviez ce que vous faisiez, alors ils ont fourni la sync_with_stdio méthode.

Answer 2

Juste par curiosité, j'ai pris un coup d'oeil à ce qui se passe sous le capot, et j'ai utilisé dtruss/strace sur chaque test.

C++

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

syscalls 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

syscalls sudo dtruss -c ./a.py < in

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

Answer 3

J'ai reproduit le résultat original sur mon ordinateur à l'aide de g++ sur un Mac.

Ajouter les instructions suivantes pour le C++ version juste avant de l' while boucle, il apporte en ligne avec le Python version:

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

sync_with_stdio amélioration de la vitesse à 2 secondes, et la fixation d'un tampon plus grand l'ont réduit à 1 seconde.

Answer 4

Getline, flux operatoes, scanf, peut être pratique si vous ne se soucient pas de fichier temps de chargement ou si vous êtes chargement de petits fichiers texte...mais si la performance est quelque chose que vous aimez, vous devriez vraiment tampon de la totalité du fichier en mémoire (en supposant qu'il sera en forme). 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 la mémoire tampon pour un accès plus commode comme ceci:

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

Aussi, si vous êtes dans le contrôle du fichier, pensez à utiliser un plat de format de données binaire au lieu de texte. C'est plus fiable à lire et à écrire parce que vous n'avez pas à traiter avec toutes les ambiguïtés de l'espace. Il est également plus petit et beaucoup plus rapide à analyser.

Answer 5

Je peux reproduire vos résultats sur mon système. Je nourris un 351 mo de fichier binaire pour les deux programmes et la version de Python divise par zéro, car il s'exécute rapidement et la version C++ prend 12 secondes à s'exécuter.

J'ai pris de la vitesse moyenne arithmétique et a couru les tests un peu de temps:

cat prend une moyenne de 0.055 secondes (plus de huit pistes) pour vider le fichier /dev/null.

La version de Python prend une moyenne de .484 secondes et 0.03 ssd (plus de huit pistes) pour compter les lignes. Voici un représentant de sortie à partir d' /usr/bin/time, ce qui est suffisant pour afficher la mémoire utilisée (20800 max résident kilo-octets) et e / s de disque (0major == tout ce qui a été lu à partir du cache).

0.48user 0.08system 0:00.56elapsed 98%CPU (0avgtext+0avgdata 20800maxresident)k
0inputs+0outputs (0major+1604minor)pagefaults 0swaps

La version C++ prend une moyenne de 12.32 secondes et 0.23 ssd (plus de huit pistes) pour compter les lignes. Un représentant de sortie à partir d' /usr/bin/time montre seulement 4672 max résident kilo-octets et encore une fois, 0major montre tout ce qui a été lu à partir du cache:

12.34user 0.09system 0:12.45elapsed 99%CPU (0avgtext+0avgdata 4672maxresident)k
0inputs+8outputs (0major+349minor)pagefaults 0swaps

J'ai plus de mémoire libre que je sais quoi faire avec:

$ free -m
             total       used       free     shared    buffers     cached
Mem:          5979       4413       1566          0        226       2594
-/+ buffers/cache:       1591       4387
Swap:         6347          1       6346

Comme un résumé rapide, 4387 dans la free colonne -/+ buffers/cache ligne indique que j'ai à peu près quatre gigaoctets de mémoire "libre" pour le noyau de tout temps il veut. La pression de la mémoire n'est pas un problème.

La version de Python créée 54898 lignes strace -o /tmp/python /tmp/readlines.py < /input/file.

La version C++ créée 89802 lignes strace -o /tmp/cpp /tmp/readlines < /input/file.