Gros décalage (x9) dans le temps d’exécution entre un code presque identique en C et C++

Question

J'ai essayé de résoudre cet exercice de www.spoj.com : FCTRL - Factorielle

Vous n'avez donc pas à le lire, il suffit de faire si vous êtes curieux :)

J'ai d'abord mis en œuvre en C++ (ici c'est ma solution):

#include <iostream>
using namespace std;

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    std::ios_base::sync_with_stdio(false); // turn off synchronization with the C library's stdio buffers (from http://stackoverflow.com/a/22225421/5218277)

    cin >> num_of_inputs;

    while (num_of_inputs--)
    {
        cin >> fact_num;

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        cout << num_of_trailing_zeros << "\n";
    }

    return 0;
}

J'ai téléchargé comme la solution pour g++ 5.1

Le résultat a été: Temps 0.18 Mem3.3 M

Mais ensuite j'ai vu certains commentaires qui ont déclaré que leur temps d'exécution est inférieure à 0,1. Puisque je ne pouvais pas penser algorithme plus rapide, j'ai essayé de mettre en œuvre le même code en C:

#include <stdio.h>

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    scanf("%d", &num_of_inputs);

    while (num_of_inputs--)
    {
        scanf("%d", &fact_num);

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        printf("%d", num_of_trailing_zeros);
        printf("%s","\n");
    }

    return 0;
}

J'ai téléchargé la solution idéale pour les ccag 5.1

Cette fois, le résultat a été: Temps De 0,02 Mem2.1 M

Maintenant, le code est presque la même, j'ai ajouté std::ios_base::sync_with_stdio(false); pour le code C++ comme il a été suggéré ici pour désactiver la synchronisation avec le C de la bibliothèque stdio tampons. J'ai également divisé l' printf("%d\n", num_of_trailing_zeros); de printf("%d", num_of_trailing_zeros); printf("%s","\n"); afin de compenser pour le double appel de operator<< en cout << num_of_trailing_zeros << "\n";.

Mais je ne voyais toujours x9 de meilleures performances et la plus faible utilisation de la mémoire en C et C++ code.

Pourquoi est-ce?

MODIFIER

J'ai fixé unsigned long de unsigned int dans le C du code. Il doit avoir été unsigned int , et les résultats qui sont présentés ci-dessus sont liés à la nouvelle (unsigned int) de la version.

Answer 1

Les deux programmes font exactement la même chose. Ils utilisent le même algorithme, et compte tenu de sa faible complexité, leur performance est principalement liée à l'efficacité de l'entrée et la sortie de la manipulation.

la numérisation de l'entrée scanf("%d", &fact_num); sur un côté et de l' cin >> fact_num; sur l'autre ne semble pas très coûteux. En fait, il devrait être moins coûteux en C++ depuis le type de conversion est connu au moment de la compilation et de la bonne analyseur peut être invoquée directement par le compilateur C++. La même chose vaut pour la sortie. Vous même faire un point de la rédaction d'un appel distinct pour printf("%s","\n");, mais le compilateur C est assez bon pour le compiler comme un appel à l' putchar('\n');.

Donc en regardant la complexité de l'I/O et le calcul, la version C++ devrait être plus rapide que la version C.

Complètement désactiver la mise en mémoire tampon de l' stdout ralentit le C mise en œuvre de quelque chose d'encore plus lent que la version C++. Un autre test par AlexLop avec un fflush(stdout); après la dernière printf rendements des performances similaires à la version C++. Il n'est pas aussi lent que désactiver complètement la mise en mémoire tampon parce que la production est écrit dans le système en petits morceaux au lieu d'un octet à la fois.

Cela semble pointer vers un comportement spécifique dans votre bibliothèque C++: je soupçonne votre mise en œuvre du système d' cin et cout bouffées de chaleur à la sortie d' cout lorsque la saisie est demandée cin. Certaines bibliothèques C faire cela, mais en général seulement lors de la lecture/écriture des vers et depuis le terminal. L'analyse comparative effectuée par le www.spoj.com site probablement les redirections d'entrée et de sortie et des fichiers.

AlexLop a fait un autre test: lecture de toutes les entrées à la fois un vecteur et par la suite le calcul et l'écriture de toutes les données de sortie permet de comprendre pourquoi la version C++ est beaucoup plus lent. Il augmente les performances à celle de la version C, cela prouve mon point de vue et supprime des soupçons sur le C++ code de mise en forme.

Un autre test par Blastfurnace, le stockage de toutes les sorties dans un std::ostringstream et de rinçage que, dans une explosion à la fin, permet d'améliorer les performances de C++ à celle de la base de C de la version. CQFD.

L'entrelacement d'entrée de cin et de sortie d' cout semble provoquer une très inefficace I/O de la manipulation, en battant le flux de mise en mémoire tampon régime. réduire les performances par un facteur de 10.

PS: votre algorithme est incorrect pour fact_num >= UINT_MAX / 5 car fives *= 5 débordement et l'enrouler autour de avant qu'il ne devienne > fact_num. Vous pouvez corriger ce problème en rendant fives un unsigned long ou unsigned long long si l'un de ces types est plus grand que unsigned int. Également utiliser %u le scanf format. Vous avez de la chance les gars www.spoj.com ne sont pas trop strictes dans leur indice de référence.

EDIT: Comme expliqué un peu plus tard par vitaux, ce comportement est en effet mandaté par la norme C++. cin , est lié à l' cout par défaut. Une opération d'entrée de cin pour lequel la mémoire tampon d'entrée doit être rempli entraînera cout pour le rincer dans l'attente de sortie. Dans le cas des OP de la mise en œuvre, cin semble rincer cout systématiquement, ce qui est un peu exagéré, et visiblement inefficace.

Ilya Popov a fourni une solution simple pour cela: cin peut être déliée de cout par coulée d'une autre les formules magiques en plus de std::ios_base::sync_with_stdio(false);:

cin.tie(nullptr);

Notez également que ces forcé rougeur se produit également lors de l'utilisation d' std::endl au lieu de '\n' pour produire une fin de ligne sur cout. Modification de la ligne de sortie de plus en plus en C++ idiomatiques et innocent regardant cout << num_of_trailing_zeros << endl; serait dégrader les performances de la même façon.

Answer 2

Un autre truc pour faire de iostreams plus rapide lorsque vous utilisez les deux cin et cout est d'appeler

cin.tie(nullptr);

Par défaut, lors de la saisie de tout, de la cin, il bouffées cout. Il peut considérablement nuire à la performance si vous ne entrelacés d'entrée et de sortie. Ceci est fait pour l'interface de ligne de commande utilise, où vous montrez quelques invite et puis d'attendre pour les données:

std::string name;
cout << "Enter your name:";
cin >> name;

Dans ce cas, vous souhaitez assurez-vous que l'invite est montré en fait avant de commencer attente d'entrée. Avec la ligne au-dessus de vous briser cette égalité, cin et cout devenir indépendant.

Depuis C++11, un moyen de plus pour obtenir de meilleures performances avec iostreams est d'utiliser std::getline avec std::stoi, comme ceci:

std::string line;
for (int i = 0; i < n && std::getline(std::cin, line); ++i)
{
    int x = std::stoi(line);
}

De cette façon, peut se rapprocher de style C dans la performance, ou même de les dépasser, scanf. À l'aide de getchar et surtout getchar_unlocked ensemble avec manuscrites d'analyse fournit toujours de meilleures performances.

PS. J'ai écrit un post en comparant plusieurs façons de saisir des chiffres en C++, utile pour les juges en ligne, mais il est seulement en russie, désolé. Les exemples de code et de la table finale, cependant, doit être compréhensible.

Answer 3

Le problème est que, citant cppreference:

n'importe quelle entrée de std::cin, sortie à std::eree, ou la fin du programme, les forces de l'appel à std::cout.flush()

C'est facile à tester: si vous remplacez

cin >> fact_num;

avec

scanf("%d", &fact_num);

et même pour cin >> num_of_inputs mais gardez cout vous aurez à peu près la même performance dans votre version C++ (ou, plutôt IOStream version) comme en C:

La même chose se produit si vous gardez cin mais remplacer

cout << num_of_trailing_zeros << "\n";

avec

printf("%d", num_of_trailing_zeros);
printf("%s","\n");

Une solution simple est de dénouer cout et cin comme mentionné par Ilya Popov:

cin.tie(nullptr);

La bibliothèque Standard implémentations sont autorisés à omettre l'appel à rincer, dans certains cas, mais pas toujours. Voici une citation de C++14 27.7.2.1.3 (grâce à chqrlie):

Classe basic_istream::sentry : tout d'Abord, si est.la cravate() n'est pas un pointeur null, la fonction d'appels est.la cravate()->flush() pour synchroniser la séquence de sortie avec toute C externe flux. Sauf que cet appel peut être supprimée si le mis de la zone de l'est.la cravate() est vide. Aller plus loin dans la mise en œuvre est autorisé à différer l'appel à rincer jusqu'à ce que l'appel de l'est.rdbuf()->underflow() se produit. Si aucun appel se produit avant la sentinelle objet est détruit, l'appel à la chasse peut être entièrement éliminées.