Duża różnica (x9) w czasie wykonywania między prawie identycznym kodem w C i C ++

Próbowałem rozwiązać to ćwiczenie z www.spoj.com: FCTRL - Factorial

Nie musisz tego czytać, po prostu zrób to, jeśli jesteś ciekawy :)

Najpierw zaimplementowałem to w C ++ (oto moje rozwiązanie):

#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 https://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;
}

Wgrałem to jako rozwiązanie dla g ++ 5.1

Wynik był następujący: Czas 0,18 Mem 3,3M

Ale potem zobaczyłem kilka komentarzy, które twierdziły, że ich czas wykonania był mniejszy niż 0,1. Ponieważ nie mogłem myśleć o szybszym algorytmie, próbowałem zaimplementować ten sam kod w 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;
}

Wgrałem to jako rozwiązanie dla gcc 5.1

Tym razem wynik był następujący: Czas 0,02 Mem 2,1M

Teraz kod jest prawie taki sam , dodałem std::ios_base::sync_with_stdio(false);do kodu C ++ tak, jak zasugerowano tutaj, aby wyłączyć synchronizację z buforami stdio biblioteki C. Ja również podzieliła printf("%d\n", num_of_trailing_zeros);się printf("%d", num_of_trailing_zeros); printf("%s","\n");, aby zrekompensować podwójnym wezwaniem operator<<w cout << num_of_trailing_zeros << "\n";.

Ale nadal widziałem lepszą wydajność x9 i mniejsze zużycie pamięci w kodzie C w porównaniu z C ++.

Dlaczego?

EDYTOWAĆ

I stała unsigned longsię unsigned intw kodzie C. Powinien był być, unsigned inta wyniki, które pokazano powyżej, są związane z nową ( unsigned int) wersją.

Oba programy robią dokładnie to samo. Używają tego samego dokładnego algorytmu, a biorąc pod uwagę jego małą złożoność, ich wydajność jest głównie związana z wydajnością obsługi wejścia i wyjścia.

skanowanie danych wejściowych z scanf("%d", &fact_num);jednej strony i cin >> fact_num;z drugiej nie wydaje się zbyt kosztowne. W rzeczywistości powinno to być mniej kosztowne w C ++, ponieważ typ konwersji jest znany w czasie kompilacji, a poprawny parser może zostać wywołany bezpośrednio przez kompilator C ++. To samo dotyczy wyników. Możesz nawet napisać osobne wywołanie for printf("%s","\n");, ale kompilator C jest wystarczająco dobry, aby skompilować to jako wywołanie putchar('\n');.

Patrząc więc na złożoność operacji we / wy i obliczeń, wersja C ++ powinna być szybsza niż wersja w C.

Całkowite wyłączenie buforowania stdoutspowalnia implementację C do czegoś nawet wolniejszego niż wersja C ++. Kolejny test AlexLop z fflush(stdout);po ostatnim printfdaje podobną wydajność jak wersja C ++. Nie jest tak powolne, jak całkowite wyłączenie buforowania, ponieważ dane wyjściowe są zapisywane w systemie w małych kawałkach zamiast po jednym bajcie na raz.

Wydaje się, że wskazuje to na specyficzne zachowanie w twojej bibliotece C ++: Podejrzewam, że twój system implementuje cini coutopróżnia dane wyjściowe, coutgdy żądane jest wejście cin. Niektóre biblioteki C również to robią, ale zwykle tylko podczas odczytu / zapisu do iz terminala. Benchmarking wykonany przez witrynę www.spoj.com prawdopodobnie przekierowuje wejście i wyjście do iz plików.

AlexLop przeprowadził kolejny test: odczytanie wszystkich danych wejściowych naraz w wektorze, a następnie obliczenie i zapisanie wszystkich danych wyjściowych pomaga zrozumieć, dlaczego wersja C ++ jest o wiele wolniejsza. Zwiększa wydajność w porównaniu z wersją C, co potwierdza mój punkt widzenia i usuwa podejrzenia dotyczące kodu formatującego C ++.

Kolejny test przeprowadzony przez Blastfurnace, przechowujący wszystkie dane wyjściowe w pliku std::ostringstreami opróżniający go w jednym wybuchu na końcu, poprawia wydajność C ++ do podstawowej wersji C. CO BYŁO DO OKAZANIA.

Wydaje się, że przeplatanie wejścia zi cinwyjścia do coutpowoduje bardzo nieefektywną obsługę operacji we / wy, pokonując schemat buforowania strumienia. zmniejszenie wydajności o współczynnik 10.

PS: Twój algorytm jest nieprawidłowy, fact_num >= UINT_MAX / 5ponieważ fives *= 5przepełni się i zawinie, zanim się stanie > fact_num. Możesz to poprawić, wprowadzając fivesznak unsigned longlub an, unsigned long longjeśli jeden z tych typów jest większy niż unsigned int. Użyj również %ujako scanfformatu. Masz szczęście, że faceci na www.spoj.com nie są zbyt surowi w swoich testach porównawczych.

EDYCJA: Jak później wyjaśnił Vitaux, to zachowanie jest rzeczywiście narzucone przez standard C ++. cinjest coutdomyślnie powiązany . Operacja wejściowa, cindla której bufor wejściowy wymaga uzupełnienia, spowoduje coutopróżnienie oczekującego wyjścia. cinWydaje się , że w realizacji PO coutsystematyczne spłukiwanie się systematyczne, co jest nieco przesadzone i wyraźnie nieefektywne.

Ilya Popov zapewniła na to proste rozwiązanie: cinmożna go rozwiązać cout, rzucając inne magiczne zaklęcie oprócz std::ios_base::sync_with_stdio(false);:

cin.tie(nullptr);

Zauważ również, że taki wymuszony kolor występuje również, gdy używa się std::endlzamiast '\n'tworzyć koniec linii na cout. Zmiana linii wyjściowej na bardziej idiomatyczną i niewinną w C ++ obniżyłaby cout << num_of_trailing_zeros << endl;wydajność w ten sam sposób.

Kolejną sztuczką, która przyspiesza iostreams, gdy używasz obu cini, coutjest dzwonienie

cin.tie(nullptr);

Domyślnie, kiedy wprowadzasz cokolwiek z cin, opróżnia cout. Może to znacznie pogorszyć wydajność, jeśli dane wejściowe i wyjściowe są przeplatane. Odbywa się to dla interfejsu wiersza poleceń, w którym wyświetla się monit, a następnie czeka na dane:

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

W takim przypadku chcesz się upewnić, że monit jest rzeczywiście wyświetlany, zanim zaczniesz czekać na wprowadzenie danych. Linią powyżej zrywasz ten remis cini coutstajesz się niezależny.

Od C ++ 11, jeszcze jednym sposobem na osiągnięcie lepszej wydajności z iostreams jest użycie std::getlinerazem z std::stoi:

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

W ten sposób może zbliżyć się do stylu C pod względem wydajności, a nawet przewyższyć scanf. Używanie, getchara zwłaszcza w getchar_unlockedpołączeniu z ręcznym analizowaniem, nadal zapewnia lepszą wydajność.

PS. Napisałem post porównujący kilka sposobów wprowadzania liczb w C ++, przydatny dla sędziów online, ale jest to tylko po rosyjsku, przepraszam. Próbki kodu i ostateczna tabela powinny być jednak zrozumiałe.

Problem w tym, że cppreference :

dowolne wejście ze std :: cin, wyjście do std :: cerr lub zakończenie programu wymusza wywołanie std :: cout.flush ()

Łatwo to sprawdzić: jeśli wymienisz

cin >> fact_num;

z

scanf("%d", &fact_num);

i to samo, cin >> num_of_inputsale zachowaj cout, uzyskasz prawie taką samą wydajność w swojej wersji C ++ (lub raczej w wersji IOStream) jak w C:

To samo dzieje się, jeśli zachowasz, cinale wymienisz

cout << num_of_trailing_zeros << "\n";

z

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

Prostym rozwiązaniem jest rozwiązanie problemu couti, cinjak wspomniał Ilya Popov:

cin.tie(nullptr);

Standardowe implementacje bibliotek mogą pomijać wywołanie opróżnienia w niektórych przypadkach, ale nie zawsze. Oto cytat z C ++ 14 27.7.2.1.3 (dzięki chqrlie):

Klasa basic_istream :: sentry: Po pierwsze, jeśli is.tie () nie jest pustym wskaźnikiem, funkcja wywołuje is.tie () -> flush () w celu zsynchronizowania sekwencji wyjściowej z dowolnym skojarzonym zewnętrznym strumieniem C. Tyle tylko, że to wywołanie można powstrzymać, jeśli obszar wstawiania is.tie () jest pusty. Ponadto implementacja może odroczyć wywołanie opróżnienia do momentu wywołania is.rdbuf () -> underflow (). Jeśli takie wywołanie nie nastąpi przed zniszczeniem obiektu wartownika, wywołanie flush może zostać całkowicie wyeliminowane.