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

85

Я пытался решить это упражнение с сайта 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 Mem 3,3M Результаты выполнения C ++

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

На этот раз результат был: Time 0.02 Mem 2.1M Результаты выполнения C

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

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

Почему это?

РЕДАКТИРОВАТЬ

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

Алекс Лоп.
источник
31
Потоки C ++ очень медленные по дизайну. Потому что медленное и устойчивое побеждает в гонке. : P ( бежит до того, как я
обожгусь
7
Медлительность не связана с безопасностью или приспособляемостью. Он слишком перегружен всеми флагами потока.
Кароли Хорват
8
@AlexLop. Использование a std::ostringstreamдля накопления вывода и его одновременной отправки std::cout всем в конце сокращает время до 0,02. Использование std::coutв цикле просто медленнее в их среде, и я не думаю, что есть простой способ улучшить его.
Blastfurnace
6
Больше никого не беспокоит тот факт, что эти тайминги были получены с использованием ideone?
ildjarn 06
6
@Olaf: Боюсь, я не согласен, этот вопрос очень актуален для всех выбранных тегов. C и C ++ в целом достаточно близки, поэтому такая разница в производительности требует объяснения. Я рад, что мы его нашли. Возможно, как следствие, следует улучшить GNU libc ++.
chqrlie 06

Ответы:

56

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

сканирование ввода с 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. QED.

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

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

РЕДАКТИРОВАТЬ: как позже объяснил vitaux, такое поведение действительно предусмотрено стандартом C ++. по умолчанию cinпривязан к cout. Операция ввода, cinдля которой требуется пополнение входного буфера, приведет coutк сбросу ожидающих вывода. В реализации OP, 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;снизит производительность.

chqrlie
источник
2
Вы, наверное, правы насчет промывки ручья Сбор вывода в a std::ostringstreamи вывод всего одного раза в конце сокращает время до паритета с версией C.
Blastfurnace
2
@ DavidC.Rankin: Я рискнул предположить (cout краснеет после прочтения cin), придумал способ доказать это, AlexLop реализовал его, и это действительно дает убедительные доказательства, но Blastfurnace придумал другой способ доказать мою точку зрения и свои тесты дают столь же убедительные доказательства. Я беру это за доказательство, но, конечно, это не полностью формальное доказательство, если посмотреть на исходный код C ++, можно.
chqrlie 06
2
Я попытался использовать ostringstreamдля вывода, и он дал Time 0.02 QED :). Что касается fact_num >= UINT_MAX / 5, ДОБРЫЙ вопрос!
Алекс Лоп.
1
Сбор всех входных данных в a vectorи последующая обработка вычислений (без ostringstream) дает тот же результат! Время 0,02. Сочетание обоих vectorи ostringstreamне улучшит его больше. То же время 0,02
Алекс Лоп.
2
Более простое исправление, которое работает, даже если sizeof(int) == sizeof(long long)это: добавить тест в тело цикла после, num_of_trailing_zeros += fact_num/fives;чтобы проверить fives, достиг ли он своего максимума:if (fives > UINT_MAX / 5) break;
chqrlie
44

Еще один способ сделать 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);
}

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

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

Илья Попов
источник
1
Спасибо за объяснение и +1 за решение, но предложенная вами альтернатива с std::readlineи std::stoiне является функционально эквивалентной коду OPs. Оба cin >> x;и scanf("%f", &x);принимают пробелы муравья в качестве разделителя, в одной строке может быть несколько чисел.
chqrlie 07
27

Проблема в том, что цитируя cppreference :

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

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

cin >> fact_num;

с участием

scanf("%d", &fact_num);

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

введите описание изображения здесь

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

cout << num_of_trailing_zeros << "\n";

с участием

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

Простое решение - развязать coutи, cinкак сказал Илья Попов:

cin.tie(nullptr);

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

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

витаут
источник
Спасибо за объяснение. Тем не менее, цитируя C ++ 14 27.7.2.1.3: Class basic_istream :: sentry : Во-первых, если is.tie()это не нулевой указатель, функция вызывает is.tie()->flush()синхронизацию выходной последовательности с любым связанным внешним потоком C. За исключением того, что этот вызов может быть подавлен, если область размещения is.tie()пуста. Кроме того, реализации разрешено отложить вызов для сброса до тех пор, пока не is.rdbuf()->underflow()произойдет вызов . Если такой вызов не происходит до того, как часовой объект будет уничтожен, вызов flush может быть полностью исключен.
chqrlie 07
Как обычно в C ++, все гораздо сложнее, чем кажется. Библиотека C ++ OP не так эффективна, как позволяет Стандарт.
chqrlie 07
Спасибо за ссылку cppreference. Но мне не нравится «неправильный ответ» на экране печати ☺
Алекс Лоп.
@AlexLop. К сожалению, исправлена ​​проблема с "неправильным ответом" =). Забыл обновить другой cin (хотя это не влияет на время).
vitaut 07
@chqrlie Верно, но даже в случае потери значимости производительность, вероятно, будет хуже по сравнению с решением stdio. Спасибо за стандартный исх.
vitaut