Question Pourquoi lire des lignes de stdin beaucoup plus lent en C ++ que Python?


Je voulais comparer les lignes de lecture de chaîne de caractères stdin en utilisant Python et C ++ et j'ai été choqué de voir mon code C ++ fonctionner plus lentement que le code Python équivalent. Puisque 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 ne comprends pas quelque chose.


(Réponse TLDR: inclure la déclaration: cin.sync_with_stdio(false) ou juste utiliser fgets au lieu.

Résultats TLDR: faites défiler tout le bas de ma question et regardez la table.)


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

Modifier:  Je devrais 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 dernier est un serveur très costaud, pas que ce soit trop pertinent.

Édition 2:  (Suppression de cette modification, car 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

Édition 3:

Ok, j'ai essayé la suggestion de J.N. d'essayer d'avoir Python stocker la ligne lue: mais cela n'a fait aucune différence pour la vitesse de python.

J'ai également essayé la suggestion de J.N. d'utiliser scanf dans une char tableau au lieu de getline dans une std::string. Bingo! Cela a abouti à des performances équivalentes pour Python et C ++. (3,333,333 LPS avec mes données d'entrée, qui sont d'ailleurs des lignes courtes de trois champs chacun, habituellement d'environ 20 caractères de large, mais 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++;
};

La 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, je l'ai couru plusieurs fois.) Donc, je suppose que je vais maintenant utiliser scanf au lieu de getline. Mais, je suis toujours curieux si les gens pensent que cette performance a frappé de std::string/getline est typique et raisonnable.

Edit 4 (était: édition finale / solution):

Ajouter:

cin.sync_with_stdio(false);

Immédiatement au-dessus de mon original alors que la boucle ci-dessus résulte en un code qui s'exécute plus vite que Python.

Nouvelle comparaison de performance (Ceci est sur mon 2011 MacBook Pro), en utilisant le code original, l'original avec la synchronisation désactivée, et le code Python d'origine, respectivement, sur un fichier avec 20M lignes de texte. Oui, je l'ai couru plusieurs fois pour éliminer la confusion de disque cache.

$ /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

Merci à @Vaughn Cato pour sa réponse! Toute personne que les gens peuvent élaborer ou de bonnes références peuvent indiquer pourquoi cette synchronisation se produit, ce qu'elle signifie, quand elle est utile et quand elle est désactivée serait grandement appréciée par la postérité. :-)

Edit 5 / Meilleure solution:

Comme suggéré par Gandalf The Gray ci-dessous, gets est encore plus rapide que scanf ou non synchronisé cin approche. J'ai aussi appris que scanf et gets sont à la fois DANGEREUSES et ne doivent PAS ÊTRE UTILISÉES en raison du potentiel de débordement du tampon. Donc, j'ai écrit cette itération en utilisant fgets, l'alternative la plus sûre à obtenir. Voici les lignes pertinentes pour 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 en utilisant un fichier encore plus gros (100M lignes; ~ 3.4 Go) sur un serveur rapide avec un disque très rapide, en comparant le code Python, le non synchronisé cin, et le fgetsapproches, ainsi que la comparaison avec l'utilitaire wc. [Le scanf la segmentation de la version est défaillante et je n'ai pas envie de la dépanner.]:

$ /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 c'est mieux, mais encore assez loin de la performance; Je suis assez sûr que cela est dû au fait que nous examinons chaque personnage sans aucune copie de la mémoire. Je pense que, à ce stade, d'autres parties du code deviendront le goulot d'étranglement, donc je ne pense pas que l'optimisation à ce niveau serait même utile, même si possible (puisque, après tout, je dois stocker les lignes de lecture en mémoire).

Notez également qu'un petit compromis avec l'utilisation d'un char * tampon et fgets vs. non synchronisé cin string est que ce dernier peut lire des lignes de n'importe quelle longueur, alors que le premier nécessite de limiter l'entrée à un certain nombre fini. En pratique, il s'agit probablement d'un problème de lecture de la plupart des fichiers d'entrée basés sur des lignes, car le tampon peut être défini sur une très grande valeur qui ne serait pas dépassée par une entrée valide.

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

Modifier 6:

Comme suggéré par J.F. Sebastian dans les commentaires ci-dessous, l'utilitaire GNU wc utilise du C simple read() (dans le wrapper safe-read.c) pour lire des morceaux (de 16k octets) à la fois et compter de nouvelles lignes. Voici un équivalent Python basé sur le code de J.F. (montrant juste l'extrait pertinent qui remplace le Python for boucle:

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

La performance de cette version est assez rapide (bien que toujours un peu plus lente que l'utilitaire C wc brut, 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 bête de comparer C ++ fgets/cin et le premier code python d'une part à wc -l et ce dernier extrait Python de l'autre, car les deux derniers ne stockent pas réellement les lignes de lecture, mais comptent simplement les nouvelles lignes. Pourtant, il est intéressant d'explorer toutes les différentes implémentations et de réfléchir aux implications sur les performances. Merci encore!

Édition 7: Petit addenda de référence et récapitulatif

Pour être complet, j'ai pensé mettre à jour la vitesse de lecture pour le même fichier sur la même boîte avec le code C ++ original (synchronisé). Encore une fois, ceci est pour un fichier de ligne 100M 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

1456
2018-02-21 03:24


origine


Réponses:


Par défaut, cin est synchronisé avec stdio, ce qui lui évite toute mise en mémoire tampon d'entrée. Si vous ajoutez ceci au dessus de votre main, vous devriez voir une meilleure performance:

std::ios_base::sync_with_stdio(false);

Normalement, quand un flux d'entrée est tamponné, 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, depuis le FILE* basé stdio et iostreams ont souvent des implémentations séparées et donc des tampons séparés, cela pourrait conduire à 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ées ont été lues par cin qu'elle ne l'était réellement, la seconde valeur entière ne serait pas disponible pour scanf fonction, 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 commune d'y parvenir est d'avoir cin lire chaque caractère un à la fois au besoin en utilisant stdio les fonctions. Malheureusement, cela introduit beaucoup de frais généraux. Pour de petites quantités d'intrants, 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 être en mesure de désactiver cette fonctionnalité pour obtenir de meilleures performances si vous saviez ce que vous faisiez. sync_with_stdio méthode.


1279
2018-03-11 18:10



Juste par curiosité, j'ai regardé 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

115
2018-02-21 03:33



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

Dans 'Modifier 4/5/6' du message original, vous utilisez la construction:

$ /usr/bin/time cat big_file | program_to_benchmark

C'est faux de plusieurs façons:

  1. Vous êtes en train de chronométrer l'exécution de `cat`, pas votre repère. L'utilisation de l'UC 'user' et 'sys' affichée par `time` est celle de` cat`, pas votre programme référencé. Pire encore, le temps «réel» n'est pas nécessairement exact. En fonction de l'implémentation de `cat` et des pipelines dans votre système d'exploitation local, il est possible que` cat` écrit un buffer géant final et quitte bien avant que le processus de lecture ne termine son travail.

  2. L'utilisation de `cat` est inutile et en fait contre-productive; vous ajoutez des pièces mobiles. Si vous étiez sur un système suffisamment ancien (c'est-à-dire avec un seul processeur et - dans certaines générations d'ordinateurs - E / S plus rapide que CPU) - le simple fait que `cat` fonctionnait pourrait considérablement colorer les résultats. Vous êtes également soumis à toute mise en mémoire tampon d'entrée et de sortie et à tout autre traitement que `cat` pourrait effectuer. (Cela vous mériterait probablement un prix «Useless Use of Cat» si j'étais Randal Schwartz: https://en.wikipedia.org/wiki/Cat_(Unix)#UUOC_(Useless_Use_Of_Cat))

Une meilleure construction serait:

$ /usr/bin/time program_to_benchmark < big_file

Dans cette déclaration, c'est le coquille qui ouvre big_file, en le passant à votre programme (enfin, en fait `time` qui exécute alors 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 lecture réelle de ses performances sans complications parasites.

Je mentionnerai deux "correctifs" possibles, mais faux, qui pourraient aussi être considérés (mais je les "numérote" différemment car ce ne sont pas des choses qui étaient fausses dans le message original):

R. Vous pouvez "réparer" ceci en ne chronométrant que votre programme:

$ cat big_file | /usr/bin/time program_to_benchmark

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

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

Ce sont faux pour les mêmes raisons que # 2: ils utilisent encore `cat` inutilement. 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ù `chat` est (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 à tester: `sudo cat / dev / sda | / usr / bin / time mon_compression_test - non-sortie »)

  • en pratique, sur les machines modernes, le «chat» ajouté dans le pipeline n'a probablement aucune 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 ...

- ceci indique que `cat` a consommé 74% du CPU pendant le test; et en effet 1,34 / 1,83 est d'environ 74%. Peut-être une course de:

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

aurait pris seulement les 49 secondes restantes! Probablement pas: `cat` a dû payer pour les appels système read () (ou équivalent) qui ont transféré le fichier de 'disk' (en fait le cache buffer), ainsi que les pipes écrit pour les livrer à` wc`. Le test correct aurait toujours dû faire ces appels read (); seuls les appels write-to-pipe et read-from-pipe auraient été sauvegardés, et ceux-ci devraient être plutôt bon marché.

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

En fait, j'ai fait quelques tests rapides avec un fichier de 1,5 gigaoctets sur un système Linux 3.13 (Ubuntu 14.04), obtenant ces résultats (ce sont en fait les résultats 'best of 3', 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 indiquent avoir pris plus de temps CPU (user + sys) que de temps réel. C'est parce que j'utilise la commande intégrée 'time' du shell (Bash), qui est consciente du pipeline; et je suis sur une machine multi-core où des processus séparés dans un pipeline peuvent utiliser des cœurs séparés, en accumulant du temps CPU plus rapidement qu'en temps réel. En utilisant / usr / bin / time, je vois que le temps processeur est plus petit que le temps réel, ce qui montre qu'il ne peut que passer l'unique élément de pipeline sur sa ligne de commande. En outre, la sortie du shell donne des millisecondes alors que / usr / bin / time ne donne que des centièmes de seconde.

Donc, au niveau d'efficacité de `wc -l`, le` cat` fait une énorme différence: 409/283 = 1,453 ou 45,3% de plus en temps réel, et 775/280 = 2,768, soit un énorme 177% CPU en plus! Sur ma boîte de test aléatoire c'était-là-à-le-temps.

Je devrais ajouter qu'il y a au moins une autre différence significative entre ces styles de test, et je ne peux pas dire si c'est un avantage ou 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 une entrée d'un tuyau, exactement à la vitesse envoyée par `cat`, et en morceaux pas plus grand que écrit par` cat`.

Lorsque vous exécutez `/ usr / bin / time mon_programme <big_file`, votre programme reçoit un descripteur de fichier ouvert dans le fichier réel. Votre programme - ou dans de nombreux cas, les bibliothèques d'E / S de la langue dans laquelle elles ont été écrites peuvent prendre différentes actions lorsqu'elles sont présentées avec un descripteur de fichier faisant référence à un fichier normal. Il peut utiliser mmap (2) pour mapper le fichier d'entrée dans son espace d'adressage, au lieu d'utiliser les appels système read (2) 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 binaire `cat`.

Bien sûr, il s'agit d'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 faire quelque chose d'intéressant, comme utiliser mmap (). Donc, dans la pratique, il peut être bon de faire fonctionner les repères dans les deux sens; peut-être en actualisant le résultat «chat» par un petit facteur pour «pardonner» le coût de l'exécution de «chat» lui-même.


77
2018-03-13 23:04



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

Ajouter les instructions suivantes à la version C ++ juste avant le while boucle le met 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 a amélioré la vitesse à 2 secondes et le réglage d'un tampon plus grand l'a ramené à 1 seconde.


75
2018-03-11 16:37



getline, opérateurs de flux, scanf, peut être pratique si vous ne vous souciez pas du temps de chargement du fichier ou si vous chargez de petits fichiers texte. Mais, si la performance est quelque chose qui vous tient à cœur, vous devriez vraiment juste mettre en mémoire tampon le fichier entier en mémoire (en supposant que cela va tenir).

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 ceci:

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

En outre, si vous contrôlez le fichier, pensez à utiliser un format de données binaire à la place du texte. Il est plus fiable de lire et d'écrire parce que vous n'avez pas à faire face à toutes les ambiguïtés des espaces. C'est aussi plus petit et beaucoup plus rapide à analyser.


23
2018-02-21 03:32



À propos, 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 est seulement défini quand une tentative est faite pour lire au-delà de eof. Donc, la boucle correcte serait:

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

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

11
2018-02-21 03:17



Le code suivant a été plus rapide pour moi que l'autre code affiché ici: (Visual Studio 2013, 64 bits, fichier de 500 Mo avec une longueur de ligne uniformément dans [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 de Python de plus d'un facteur 2.


8
2018-02-22 02:33