Большая разница (x9) во времени выполнения между почти идентичным кодом в C и c++

Я пытался решить это упражнение из www.spoj.com :FCTRL-Factorial

вам действительно не нужно его читать, просто сделайте это, если вам интересно :)

сначала я реализовал его в C++ (вот мое решение):

#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;
}

Я загрузил его как решение для g++ 5.1

результат: времени 0.18 мем 3.3 м

но потом я увидел некоторые комментарии, которые утверждали, что их время выполнения было меньше 0,1. Поскольку я не мог думать о более быстром алгоритме, я попытался реализовать тот же код в 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;
}

Я загрузил его как решение для gcc 5.1

в этот раз результат был: времени 0.02 мем 2.1 M

теперь код почти то же самое, я добавил std::ios_base::sync_with_stdio(false); к коду C++, как было предложено здесь, чтобы отключить синхронизацию с буферами stdio библиотеки C. Я также разделил printf("%dn", num_of_trailing_zeros); до printf("%d", num_of_trailing_zeros); printf("%s","n"); чтобы компенсировать двойной вызов operator<< на cout << num_of_trailing_zeros << "n";.

но я все равно видел x9 лучшая производительность и более низкое использование памяти в C и C++ кода.

почему это?

EDIT

исправил unsigned long до unsigned int в C код. Он должен были unsigned int и результаты, которые показаны выше, связаны с новым (unsigned int) версию.

3 84
javascript c++ gcc performance iostream

3 ответа:

обе программы делают точно то же самое. Они используют один и тот же точный алгоритм, и, учитывая его низкую сложность, их производительность в основном связана с эффективностью обработки ввода и вывода.

сканирование ввода с помощью scanf("%d", &fact_num); с одной стороны и cin >> fact_num; С другой стороны, это не кажется очень дорогостоящим в любом случае. На самом деле это должно быть дешевле в C++, так как тип преобразования известен во время компиляции, и правильный парсер может быть вызван непосредственно компилятором C++. Этот то же самое относится и к выходу. Вы даже делаете точку написания отдельного вызова для printf("%s","\n");, но компилятор C достаточно хорош, чтобы скомпилировать это как вызов putchar('\n');.

поэтому, глядя на сложность ввода-вывода и вычислений, версия C++ должна быть быстрее, чем версия C.

полное отключение буферизации stdout замедляет реализацию C до чего-то еще медленнее, чем версия C++. Еще один тест от AlexLop с fflush(stdout); после последнего printf дает аналогичную производительность, как и версия C++. Это не так медленно, как полное отключение буферизации, потому что вывод записывается в систему небольшими кусками вместо одного байта за раз.

это, кажется, указывает на определенное поведение в вашей библиотеке C++: я подозреваю, что ваша система реализует cin и cout ает вывод cout когда ввод запрашивается от cin. Некоторые библиотеки C делают это также, но обычно только при чтении / записи В и из терминал. Бенчмаркинг, проведенный www.spoj.com сайт, вероятно, перенаправляет вход и выход из файлов.

AlexLop сделал еще один тест: чтение всех входных данных сразу в векторе, а затем вычисление и запись всех выходных данных помогает понять, почему версия C++ намного медленнее. Это повышает производительность до версии C, это доказывает мою точку зрения и устраняет подозрение на код форматирования C++.

еще один тест от Blastfurnace, хранящий все выходы в std::ostringstream и промывка, которая в одном взрыве в конце, улучшает производительность C++ до базовой версии C. КЭД.

Чересстрочный ввод от cin и вывода cout кажется, что вызывает очень неэффективную обработку ввода-вывода, побеждая схему буферизации потока. снижение производительности в 10 раз.

PS: ваш алгоритм неверен для fact_num >= UINT_MAX / 5, потому что fives *= 5 переполнит и обернет вокруг, прежде чем он станет > fact_num. Вы можете исправить это путем fives an unsigned long или unsigned long long если один из этих типов больше, чем unsigned int. Также используйте %u как . Вам повезло, что ребята на www.spoj.com не слишком строги в своих оценках.

EDIT: как позже объяснил vitaux, это поведение действительно предусмотрено стандартом C++. cin связана с cout по умолчанию. Операция ввода от cin для которого входной буфер нуждается в пополнении вызовет cout для сброса ожидающего вывода. В реализации ОП,cin кажется, флаш cout систематически, что немного излишне и явно неэффективно.

Илья Попов предоставил простое решение для этого:cin может быть "привязана" к cout наложив еще одно магическое заклинание в дополнение к std::ios_base::sync_with_stdio(false);:

cin.tie(nullptr);

также обратите внимание, что такой принудительный сброс также происходит при использовании std::endl вместо '\n' для получения конца линии на cout. Изменение выходной строки на более идиоматичный и невинный вид C++cout << num_of_trailing_zeros << endl; будет ухудшать производительность таким же образом.

56

еще один трюк, чтобы сделать iostreams быстрее при использовании cin и cout позвонить 

cin.tie(nullptr);

по умолчанию, когда вы вводите что-либо из cin, оно топит cout. Это может значительно ухудшить производительность, если вы делаете чередование ввода и вывода. Это делается для использования интерфейса командной строки, где вы показываете некоторые подсказки, а затем ждете данных:

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

в этом случае вы хотите убедиться, что приглашение действительно отображается перед началом работы ждем ввода. С линией выше вы разорвать эту связь,cin и cout стать независимым.

начиная с C++11, Еще один способ добиться лучшей производительности с помощью iostreams-использовать std::getline вместе с std::stoi, например:

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

этот путь может прийти близко к C-типу в представлении, или даже перегнать scanf. Используя getchar и особенно getchar_unlocked вместе с рукописным разбором по-прежнему обеспечивает лучшую производительность.

PS. У меня есть написано пост сравнение нескольких способов ввода чисел в C++, полезно для онлайн-судей, но это только на русском языке, извините. Однако примеры кода и окончательная таблица должны быть понятны.

44

проблема в том, что цитируешь cppreference:

любой вход из std::cin, выход в std::cerr или завершение программы вызывает вызов std:: cout.flush()

это легко проверить: если вы замените

cin >> fact_num;

С

scanf("%d", &fact_num);

и cin >> num_of_inputs но сохранить cout вы получите почти такую же производительность в своей версии C++ (или, скорее, версии IOStream), как и в C один:

enter image description here

то же самое происходит, если вы держите cin но заменить

cout << num_of_trailing_zeros << "\n";

С

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

простое решение состоит в том, чтобы "развязать"cout и cin как упоминал Илья Попов:

cin.tie(nullptr);

стандартные реализации библиотеки позволяют опустить вызов flush в некоторых случаях, но не всегда. Вот цитата из C++14 27.7.2.1.3 (благодаря chqrlie):

класс basic_istream:: sentry: во-первых, если есть.tie () - это не нулевой указатель, а вызовы функций.tie () - >flush () для синхронизации выходной последовательности с любым связанным внешним потоком C. За исключением того, что этот вызов может быть подавлен, если область put is.галстук() пуст. Далее реализация позволяет отложить вызов для сброса до вызова is.rdbuf()->underflow() происходит. Если такой вызов не происходит до уничтожения объекта sentry, вызов flush может быть полностью устранен.

27