Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 127
Ну раз нет разницы в производительности, я считаю, что все же лучше использовать while (true), т. к. эта конструкция имеет гораздо более понятный смысл чем for с каким-то смайликом.
Не с каким-то, это же Ктулху =)
А можно еще так написать:
for(;1;)
Можно еще и for (;;0) например написать. или (0;;0)
Или вовсе (;;-0)
Способы создания смайлов на Си бессчетны ;)
Или вовсе (;;-0)
Способы создания смайлов на Си бессчетны ;)
Мы остановились, добившись успешной компиляции следующего:
for(;P("\n"),R-;P("|"))for(e=C;e-;P("_"+(*u++/8)%2))P("| "+(*u/4)%2);
Вывод можно? Ну или функцию P хотя бы =)
Ну, лет 10 назад на Turbo C 2.0 мне удалось это скомпилировать. С тех пор на C я не писал, так что, боюсь, всё уже забыл.
Как же вы тогда это запомнили? О_о
Гугл выплюнул такую страницу.
Тьфу. Так это цитата. Слепорылый я. Мне показалось, что forgotten привёл пример своего кода.
А еще можно найти это на lurkmore. Про это там говорится:
Вот на С++ вы можете написать subj. На паскале вы не можете такого написать, это одно из преимуществ паскаля перед С++...
Список не полон без for (0;1;0).
А что делать с предупреждением MSVC: «warning C4127: conditional expression is constant»?
Для полноты, мне кажется, стоит добавить хотябы один результат с компилятором Visual Studio.
А while (1) почти аналогичен for (;;) по длине ;)
Привыкать к автоматическому приведению типов — не есть хорошо.
вообще, если на то пошло, все boolean в C — суть синтаксический сахар.
в конечном итоге все будет именно что приведено к 0 (false) либо не-0 (true)
поэтому, задавая 1, я как раз таки не пользуюсь никаким приведением, а сразу даю конечное значение.
в конечном итоге все будет именно что приведено к 0 (false) либо не-0 (true)
поэтому, задавая 1, я как раз таки не пользуюсь никаким приведением, а сразу даю конечное значение.
Всё есть 1 и 0. Это же не значит, что нужно писать бинарные данные.
На самом деле, писать while(1) или while(true) или for(;;) — дело принятого форматирования и каждый выбирает для себя свой удобный вариант.
Главное, чтобы в пределах одного проекта использовалась везде идентичноеиспользованиенаписание.
UPD: масло масленное
На самом деле, писать while(1) или while(true) или for(;;) — дело принятого форматирования и каждый выбирает для себя свой удобный вариант.
Главное, чтобы в пределах одного проекта использовалась везде идентичное
UPD: масло масленное
Либо вы неверно понимаете природу boolean значений в C, либо неверно читаете мои комментарии.
Я не сказал, что записываю значение true в бинарном виде.
Я сказал, что записываю его в той самой форме, в которой его воспринимает компилятор.
Утверждать, что в C литерал 1 приводится к литералу true — безграмотность, извините.
Я не сказал, что записываю значение true в бинарном виде.
Я сказал, что записываю его в той самой форме, в которой его воспринимает компилятор.
Утверждать, что в C литерал 1 приводится к литералу true — безграмотность, извините.
Простите, виноват, не правильно выразился.
Фразой «Всё есть 1 и 0.» я не имел ввиду природу значений boolean в си.
Это был ответ на ваш комментарий, что Вы сразу даёте конечное значение. Как бы параллель с бинарными данными: все, что мы пишем в любом случае становится бинарными данными, но ведь мы не пишем прямо бинарные данные.
Так и boolean значения — их же ввели в язык, значит там, где нужно использовать boolean, сугубо по моему мнению стоит использовать true/false, а не 1/0.
Я ни в коем случае не подразумеваю, что только так нужно делать, это уже выбор каждого.
Фразой «Всё есть 1 и 0.» я не имел ввиду природу значений boolean в си.
Это был ответ на ваш комментарий, что Вы сразу даёте конечное значение. Как бы параллель с бинарными данными: все, что мы пишем в любом случае становится бинарными данными, но ведь мы не пишем прямо бинарные данные.
Так и boolean значения — их же ввели в язык, значит там, где нужно использовать boolean, сугубо по моему мнению стоит использовать true/false, а не 1/0.
Я ни в коем случае не подразумеваю, что только так нужно делать, это уже выбор каждого.
Безусловно, вы правы, это выбор каждого.
Во мне скорее говорит старая привычка, сформировавшаяся при разработке на Си в достаточно давние времена.
На StackOverflow, к слову, есть дискуссия на эту тему.
Согласно википедии, тип Boolean определяется как int. А true и false — как макросы для 1 и 0, соответственно.
Для C++ вы правы, там bool — отдельный тип, приводящийся к int.
Во мне скорее говорит старая привычка, сформировавшаяся при разработке на Си в достаточно давние времена.
На StackOverflow, к слову, есть дискуссия на эту тему.
Согласно википедии, тип Boolean определяется как int. А true и false — как макросы для 1 и 0, соответственно.
Для C++ вы правы, там bool — отдельный тип, приводящийся к int.
В C99+, тип bool определяется как _Bool, и к int он не имеет отношения (хотя и входит в категорию integral types).
Вероятно, википедия немного лукавит.
Сейчас еще погуглил. Согласно стандарту, _Bool действительно является интегральным типом. Основное отличие от int в том, что при приведении к нему любые значения, при сравнении оказывающиеся равны 0, станут = 0, а не оказывающиеся станут = 1. Это решает проблему неравнозначности условий (x) и (x == true).
Цитата:
Сейчас еще погуглил. Согласно стандарту, _Bool действительно является интегральным типом. Основное отличие от int в том, что при приведении к нему любые значения, при сравнении оказывающиеся равны 0, станут = 0, а не оказывающиеся станут = 1. Это решает проблему неравнозначности условий (x) и (x == true).
Цитата:
When any scalar value is converted to _Bool, the result is 0 if the value compares equal to 0; otherwise, the result is 1
int? Шито? В Студии инт занимает 4 байта, а bool 1 — в МиниГВ аналогично. Но забавный факт — хоть бул и имеет толожения 1/0. Дефакто выделенный байт может иметь 256 различных состояний — студия просто возвращет тру если не равно нулю, а МиниГВ проверяет только крайний правый бит — правда не ясно как на это смотрят ребята из комитета станадартов.
Ну логично предположить, если у Вас был курс компиляторов, что for — это while.
>> смело говорите что “for (;;)” — 8 символов написать быстрее, чем “while (true)” — 12 символов.
Ответят — while(1), разница в один символ, но читабельность! ))
Пишем так:
#define EVER ;;
for (EVER) {
Ну и дальше, кто не читал, по теме: stackoverflow.com/questions/2611246/is-for-faster-than-while-true-if-not-why-do-people-use-it
Ответят — while(1), разница в один символ, но читабельность! ))
Пишем так:
#define EVER ;;
for (EVER) {
Ну и дальше, кто не читал, по теме: stackoverflow.com/questions/2611246/is-for-faster-than-while-true-if-not-why-do-people-use-it
Статья просто шикарная! А сделаете сравнение скорости обработки двойных и одинарных кавычек в JS? И сравнение скорости обработки переменной компилятором GCC если буквы написаны в алфавитном порядке и в обратном алфавитном порядке?
Мне почему-то кажется, что в обратном порядке компилятору будет быстрее — как в жизни — сначала самое тяжёлое делается, а потом лёгкая мелочьь уже добивается запросто. А если начинать с мелких кодов, то на крупные у компилятора может не остаться сил.
Скорость распознавания лексем от этих факторов не зависит. Посимвольно if'ами такие вещи не проверяются. Для этого есть bit sets или вообще — таблично управляемые конечные автоматы.
а вот мне кажется что пост заслуживает внимания не за свое содержание, а за подход и упорство в нем примененные. Обычно, сравнивая кавычки, далее чем за сравнение цикла в 100000 итераций руки ни у кого не доходят. Тут же бенчмарк подкреплен анализом скомпилированного участка кода с выводами и объяснениями.
while (true) ибо понятно и расширяемо. for без параметров — это хак, за такое надо бить по рукам.
Я как-то раз от нечего делать писал так (очевидно, что не оптимально):
А в Qt есть такое:
while ("Infinity") {
// ...
}
А в Qt есть такое:
forever {
// ...
}
while (true) куда более выразительна, хотя Qt'шное forever {} у комментатора выше мне нравится ещё больше.
Основная проблема, что и for, и while — это операторы конечного цикла, а использование для зацикливания — это такой «хак», который багофичу с тем, что при константных условиях оператор зацикливается, превращает в общепринятую практику. А это плохо.
В любом случае спор о спичках.
Основная проблема, что и for, и while — это операторы конечного цикла, а использование для зацикливания — это такой «хак», который багофичу с тем, что при константных условиях оператор зацикливается, превращает в общепринятую практику. А это плохо.
В любом случае спор о спичках.
Во всех проектах более-менее продолжительных встречал именно
Это стандартное решение из разряда «общей точки выхода по goto».
#define FOREVER for(;;)Это стандартное решение из разряда «общей точки выхода по goto».
Это, скорее, претензия к создателям языка. При том, что у Си есть много ограничений, наложенных «fancy assembler with types», нет ни одной причины, почему оператора forever не должно было было быть в языке. Ну или, там, loop {}. Его приходится компенсировать специальными костылями с препроцессором. Некрасиво.
Причина очевидна — в языке уже есть аж целых два идиоматических способа выразить бесконечный цикл; зачем добавлять сахар, который не делает код ни короче, ни понятней?
Кстати, заметьте, что ни один мэйнстримный ЯП с си-подобным синтаксисом не ввёл такой сахар — хотя в других областях понадобавляли много чего, вплоть до лямбд. Это как бы говорит нам о ценности данной фичи…
Кстати, заметьте, что ни один мэйнстримный ЯП с си-подобным синтаксисом не ввёл такой сахар — хотя в других областях понадобавляли много чего, вплоть до лямбд. Это как бы говорит нам о ценности данной фичи…
Достаточно мэйнстримный и си-подобный язык Wiring, используемый для программирования контроллера Arduino и аналогов, имеет конструкцию loop {}.
Я бы не назвал это мейнстримным языком. Мейнстрим — это C#, Java, JavaScript, PHP.
Впрочем, даже если опустить эту планку, суть аргумента не меняется — наиболее популярные языки-последователи этой темы не касались, при том, что была масса других нововведений.
Впрочем, даже если опустить эту планку, суть аргумента не меняется — наиболее популярные языки-последователи этой темы не касались, при том, что была масса других нововведений.
Интересно, это как-нибудь связано с тем, что бесконечные циклы встречаются при программировани на микроконтроллерах гораздо чаще, чем чем в общем случае?
Занекропощу: Wiring — это просто C++ (и именно C++, а не C) обмазанный макросами. И таки макроса loop там нет. Есть функция loop(), которая вызывается из замаскированного main:
// cat /usr/share/arduino/hardware/arduino/cores/arduino/main.cpp
#include <Arduino.h>
int main(void)
{
init();
#if defined(USBCON)
USBDevice.attach();
#endif
setup();
for (;;) {
loop();
if (serialEventRun) serialEventRun();
}
return 0;
}
Есть причина — потому что его можно реализовать уже имеющимися средствами. У Си это во многом в философии — в языке только то чего нельзя реализовать, остальное в библиотеки. Для «fancy assembler with types» спасибо хоть for есть.
Я видел где то статью, там описывалось, что иногда все же использовать конечный цикл, если в итоге он будет конечным. Использовать заведомо большое число, которое покрывает ориентировочный диапазон, и обрабатывать выход за этот диапазон, каким либо способом, например считать это ошибкой или зависанием.
Рассчитайте ка мне число, заведомо большее, чем количество опросов сокета веб-сервером?
Ну если обычным инкрементом переполнять такую переменную на 3 Ггц процессоре уйдёт порядка 200 лет. Цифра, конечно, большая. При большем аптайме сервера (гипотетически), он просто упадёт. Так что это не решение.
И следует все-же рассчитывать на возможный дальнейший прогресс гигагерцев, — что будет если завтра все производители перейдут с кремния на скажем германий или нанотрубки, и частота процессоров за пару лет взлетит до 400-500 ГГц? В таком случае переполнение случится уже не за 200 лет, а за скромные 2 года, что вполне может быть аптаймом сервера.
Только goto, только хардкор.
А мне вообще кажется (так ли?), что бесконечные while и for преобразуются в goto-лапшу :)
begin:
//blah-blah-blah
goto begin
begin:
//blah-blah-blah
goto begin
ну goto преобразуется к jmp, а как мы видели из asm выкладок автора, бесконечный цикл тоже в итоге преобразуется к jmp (две другие команды mov и callq относятся к вызову printf), так что да, с точки зрения компилятора ваш пример идентичен.
Разницы тогда между всеми тремя вариантами не будет? Или всё же с goto получим что-то другое?
В асме нет команд for и while, так что будет goto в любом случае) Ну, по крайней мере в x86
В x86 есть команда
loop, которая декрементирует регистр cx, сравнивает с нулём, и если не ноль, по переходит на заданный адрес. Правда она уже давно почти не используется, потому как не даёт выигрыша по сравнению с командами по отдельности, но менее гибкая.А ещё есть команды типа «перейти, если не ноль» (
jnz и т.д.). Благодаря им, когда-то давно было выгодно писать циклы по убыванию, что позволяло избывиться от отдельной команды сравнения.
вообще-то писать циклы по убыванию и сейчас выгоднее. вдобавок с ними меньше кода, когда верхний предел вычисляется.
Когда-то давно у меня было предубеждение насчет Си — ну разве может на выходе получиться настолько быстродействующий код по сравнению с асмом? Переубедило то, когда я посмотрел на скомпилированный результат — сначала шел переход в середину цикла, а в конце условный переход в точку до цикла. «Черд, я думал, что так сделает только человек» тогда воскликнул я. В общем, все эти вроде бы неиспользуемые команды, реально используются компилятором
да их там нет, но в невырожденых случаях, там будет условный переход а не безусловный.
Из
получилось:
То есть, тоже самое. Кстати, код такой же короткий как for. И лично мне кажется даже нагляднее. Но я то в основном на Фортране программирую, так что моё мнение не показательно.
#include <stdio.h>
int main (int argc, char* argv[])
{
x:
printf("1\n");
goto x;
}
получилось:
00000000004004f4 <main>:
4004f4: 48 83 ec 08 sub $0x8,%rsp
4004f8: bf fc 05 40 00 mov $0x4005fc,%edi
4004fd: e8 ee fe ff ff callq 4003f0 <puts@plt>
400502: eb f4 jmp 4004f8 <main+0x4>
То есть, тоже самое. Кстати, код такой же короткий как for. И лично мне кажется даже нагляднее. Но я то в основном на Фортране программирую, так что моё мнение не показательно.
С GOTO может случиться проще на две команды. Не будет call вызова, просто JMP в начало.
дел
В джаве байткод такой и получается
По-моему это как раз один из тех случаев, когда логичнее всего использовать goto. Все же 99% всех for и while не бесконечны. А знаменитый совет по поводу goto имеет свои исключения.
while и for помимо своей цикличности вносят еще и область видимости. Это особенно важно для С++. Поэтому если и использовать goto, то с фигурными скобками:
Получается даже немного длинее. Нет, все-таки в этом случае право большинство: for и while — лучше.
int main ()
{
loop:
{
printf("1\n");
}
goto loop;
}
Получается даже немного длинее. Нет, все-таки в этом случае право большинство: for и while — лучше.
Если современный компилятор не может соптимзировать эти две конструкции в эквивалентный набор команд — грош цена такому комплятору.
То-что у вас на -O1 и -O2/-O3 разный размер, это выравнивание сработало (или что-то подобное, плохо уже помню). От сюда и дополнительная «пустая» инструкция:
Собственно у вас 64-битный процессор, поэтому и выровняли до 8-байт.
while(1) тоже 8-мь. Плюс лично мне проще так написать, ежели for с ;;.
400434: 0f 1f 40 00 nopl 0x0(%rax)
Собственно у вас 64-битный процессор, поэтому и выровняли до 8-байт.
что “for (;;)” — 8 символов написать быстрее, чем “while (true)” — 12 символов.
while(1) тоже 8-мь. Плюс лично мне проще так написать, ежели for с ;;.
Я лично за
— Более выразительно, не такая абракадабра
— Гораздо более понятно для людей, неопытных в C-подобных языках
— Очевидно, что сделано намеренно, тогда как
Аргументы сторонников
— K&R использовали
— Меньше символов набирать (хотя тогда можно сравнить с
— MSVC не выдаёт на него предупреждение
— Кто-то считает, что
— Некоторые считают, что
— Пишется одинаково в С-подобных языках, тогда как в С++ будет
Мне многие из этих аргуметнов кажутся надуманными.
while(true), аргументы:— Более выразительно, не такая абракадабра
— Гораздо более понятно для людей, неопытных в C-подобных языках
— Очевидно, что сделано намеренно, тогда как
for(;;) выглядит как что-то недописанноеАргументы сторонников
for(;;) (по ответам на StackOverflow):— K&R использовали
for(;;)— Меньше символов набирать (хотя тогда можно сравнить с
while(1))— MSVC не выдаёт на него предупреждение
— Кто-то считает, что
for(;;) сильнее бросается в глаза— Некоторые считают, что
true — это магическая константа. И говорят, почему тогда не while(42) например? И на основании этого делают вывод, что надо пользоваться for— Пишется одинаково в С-подобных языках, тогда как в С++ будет
while(true), в С while(TRUE), а если использовать while(1), то это не сработает в Java (там условие должно иметь булев тип)Мне многие из этих аргуметнов кажутся надуманными.
в С while(TRUE)
Либо:
while(1)
либо в C99:
#include <stdbool.h>
<...>
while(true)
либо (в том-же C99):
while((_Bool)1)
Откуда вы взяли TRUE, непонятно.
Это не я взял.
Я же написал, что аргументы за for я взял из обсуждений со SO, и лично я с ними не очень согласен.
Я же написал, что аргументы за for я взял из обсуждений со SO, и лично я с ними не очень согласен.
Откуда-откуда, конечно же из #include windows.h
P.S. Завидую человеку, который честно не знает откуда в C может взяться TRUE.
P.S. Завидую человеку, который честно не знает откуда в C может взяться TRUE.
> Завидую человеку, который честно не знает откуда в C может взяться TRUE
Там даже true есть, если сделать #include <stdbool.h>
Сам обычно бесконечные циклы реализую либо через while(1), либо через
label:
(код)
goto label;
(но так — значительно реже, если где-то после goto label нужно вернутся на label)
Там даже true есть, если сделать #include <stdbool.h>
Сам обычно бесконечные циклы реализую либо через while(1), либо через
label:
(код)
goto label;
(но так — значительно реже, если где-то после goto label нужно вернутся на label)
(zyx-desktop:zyx:~/tmp/c) 2 % grep -P '^#\s*define\s+TRUE' /usr/include/*.h --files-with-match
/usr/include/atasmart.h
/usr/include/bfd.h
/usr/include/curses.h
/usr/include/gif_lib.h
/usr/include/jmorecfg.h
/usr/include/lcms2.h
/usr/include/lcms.h
/usr/include/ncurses.h
/usr/include/notmuch.h
/usr/include/odbcinstext.h
/usr/include/pth.h
/usr/include/slcurses.h
/usr/include/twolame.h
(zyx-desktop:zyx:~/tmp/c) 2 % grep -P '^#\s*define\s+TRUE' /usr/include/*.h --files-with-match | xargs qfile | cut -d ' ' -f 1 | sort | uniq
dev-db/unixODBC
dev-libs/libatasmart
dev-libs/pth
media-libs/giflib
media-libs/lcms
media-libs/libjpeg-turbo
media-sound/twolame
net-mail/notmuch
sys-libs/ncurses
sys-libs/slang
Полагаю, что просто писать такой
#define в заголовочном файле — весьма частое явление, считающееся де‐факто стандартом. В приведённом коде замена true на TRUE заработать не должна.
Ну собственно, если скормить эти примеры gcc c ключом -S, то на выходе увидим совершенно идентичные ассемблерные листинги. Удивительно было бы ожидать тут какие-то различия.
смело говорите что “for (;;)” — 8 символов написать быстрее, чем “while (true)” — 12 символов
Не учитываете Intellisense. В VS+Resharper (C#) чтобы написать while(true) нужно нажать 3 клавиши. А вот для for (;;) около 11, если без мыши…
для С и плюсов пока нет решарпера
Найти редактор/IDE для C со сниппетами несложно. Но если учитывать их наличие, то скорость написание обеих конструкций становится зависимой исключительно от настроек редактора, но не от количества символов в конструкциях. Где‐то что‐то может даже иметься в наличии по‐умолчанию, но не факт, что в некотором конкретном редакторе по‐умолчанию будет
while (true), а не for (;;).
Visual Assist X. Давно уже не мыслю работу в студии, без этой штуки
Меня вот вседа поражают эти обсуждения. Вы реально тайпаете код со скоростью под 200 символов в минуту, что это становится критичным? А когда же подумать о том что пишется и как это выглядит? Почти у всех быстро тайпающих товарищей я вижу ад в архитектуре и тяжёлый избыточный код с повторениями.
Замечу, что компилятор javac тоже выдает идентичный байткод для обоих вариантов записи бесконечного цикла (проверял).
Для господ дискутирующих предлагается скомпилировать следующий код
с ключами /W4 (warnings level 4) и /WX (treat warnings as errors) в Visual Studio.
Получите ошибку «conditional expression is constant».
Пара моих клиентов именно так компилируют свой код и меня просят. Т.е. у меня лично этот вопрос не стоит вообще.
while(true) {
do_something();
}с ключами /W4 (warnings level 4) и /WX (treat warnings as errors) в Visual Studio.
Получите ошибку «conditional expression is constant».
Пара моих клиентов именно так компилируют свой код и меня просят. Т.е. у меня лично этот вопрос не стоит вообще.
400438/4096 = 97,763183594
Фэйспалм.
400438 в шестнадцатеричной. 4096 это 0x1000. Ничего делить не надо, смотрим последние 3 цифры
Вы конечно извините меня, но логические аргументы в спорах о вкусовщине это троллинг какой-то
Раньше писали while(1), что не сильно длиннее for(;;), но как-то более классически выглядит.
Зря потратили время на статью и дизассемблирование. Затык в производительности не будет никогда в таких мелочах.
Это примерно как потытаться просчитать, какая из двух маршруток быстрее до метро доедет, пока они обе уезжают, а мыслитель остаётся стоять на остановке.
Это примерно как потытаться просчитать, какая из двух маршруток быстрее до метро доедет, пока они обе уезжают, а мыслитель остаётся стоять на остановке.
Надо бы проверить
repeat
until false;
repeat
until false;
А давайте искать максимум из двух целых чисел!
Я предлагаю два способа это сделать:
и
Компилируем:
И смотрим, что получилось:
По модулю соглашений о передаче параметров в функции и возвращении результата в обоих случаях были сгенерированы две инструкции: сравнения и условной пересылки.
Вы посмотрели бы, что g++ (лучше самой последней доступной версии и с -O3) делает вот с такой функцией:
и насколько быстрее то, что он генерирует, работает, чем неоптимизированные варианты или даже оптимизированные, но сгенерированные clang++, компиляторами от Intel и Microsoft. Вот это интересное дело, а
Я предлагаю два способа это сделать:
int max(int a, int b) {
return a < b ? b : a;
}
и
int odd_max(int a, int b) {
int _a;
int _b;
int a_lt_b;
int rec;
int res;
double i;
_a = a;
_b = b;
a_lt_b = 2;
i = 0.0;
while (a_lt_b == 2) {
if (i > 0.0 && odd_max(a, _b) != odd_max(b, _a))
return _a + _b;
if (_a < b)
a_lt_b = 1;
else if (_b < a || _a == b)
a_lt_b = 0;
else {
rec = odd_max(a, _b);
if (rec == _a)
a_lt_b = 0;
else if (rec == b)
a_lt_b = 1;
else
a_lt_b = 2;
}
i = i + 0.1;
}
if (a_lt_b)
res = _b;
else
res = _a;
return res;
}
Компилируем:
$ cc -O2 max.c
И смотрим, что получилось:
$ objdump -d a.out
a.out: file format elf64-x86-64
<...>
0000000000400570 <max>:
400570: 39 fe cmp %edi,%esi
400572: 89 f8 mov %edi,%eax
400574: 0f 4d c6 cmovge %esi,%eax
400577: c3 retq
<...>
0000000000400580 <odd_max>:
400580: 39 f7 cmp %esi,%edi
400582: 89 f0 mov %esi,%eax
400584: 0f 4d c7 cmovge %edi,%eax
400587: c3 retq
<...>
По модулю соглашений о передаче параметров в функции и возвращении результата в обоих случаях были сгенерированы две инструкции: сравнения и условной пересылки.
Вы посмотрели бы, что g++ (лучше самой последней доступной версии и с -O3) делает вот с такой функцией:
long long fib(int n) {
if (n < 3)
return 1;
return fib(n - 1) + fib(n - 2);
}
и насколько быстрее то, что он генерирует, работает, чем неоптимизированные варианты или даже оптимизированные, но сгенерированные clang++, компиляторами от Intel и Microsoft. Вот это интересное дело, а
for(;;)while(true)
Может отдельным постом лучше оформить? Чтобы не потерялось
совсем как-то несерьёзно.
Это не несерьёзно — это смешно.
Несложно заметить, что исходный код циклов не содержит, потому разворачивание циклов здесь неприменимо. Речь идёт об успешном частичном разворачивании рекурсии, которая, между прочим, содержит два рекурсивных вызова, каждый из которых нехвостовой.
До конца развернуть рекурсию даже при известном на момент компиляции аргументе возможно, только если аргумент достаточно мал, поскольку дерево вызовов содержит экспоненциальное (от аргумента) число узлов и задача вычислительно очень сложна. Такая оптимизация, впрочем, является скорее свёрткой констант, чем разворачиванием рекурсии. При статически неизвестном аргументе это невозможно (придётся оценивать аргумент сверху максимальным значением, имеющим представление в типе int).
Что было бы здорово ожидать от компилятора — это более аргессивное выделение общих подвыражений, полученных в результате частичного разворачивания рекурсии (по сути, аккуратных инлайнов). Действительно, fib(n) = fib(n — 1) + fib(n — 2) = (fib(n — 2) + fib(n — 3)) + (fib(n — 3) + fib(n — 4)) (для n > 4) и fib(n — 3) — общее подвыражение. Можно его вычислять единожды, а не дважды, так как fib — «чистая» функция, которая не имеет побочных эффектов и результат которой зависит только от аргумента. Разворачивать с удалением общих подвыражений можно не на один уровень, как в примере, а на некоторое число уровней (пока размер результирующего кода разумен, где разумность оценивается даже не столько размером исполняемого файла, сколько размером кеша инструкций центрального процессора).
Предел ожиданий от компилятора — замена нехвостовой рекурсии на хвостовую с накапливающими параметрами и последующая оптимизация хвостового вызова. Но это пока на фантастику похоже.
До конца развернуть рекурсию даже при известном на момент компиляции аргументе возможно, только если аргумент достаточно мал, поскольку дерево вызовов содержит экспоненциальное (от аргумента) число узлов и задача вычислительно очень сложна. Такая оптимизация, впрочем, является скорее свёрткой констант, чем разворачиванием рекурсии. При статически неизвестном аргументе это невозможно (придётся оценивать аргумент сверху максимальным значением, имеющим представление в типе int).
Что было бы здорово ожидать от компилятора — это более аргессивное выделение общих подвыражений, полученных в результате частичного разворачивания рекурсии (по сути, аккуратных инлайнов). Действительно, fib(n) = fib(n — 1) + fib(n — 2) = (fib(n — 2) + fib(n — 3)) + (fib(n — 3) + fib(n — 4)) (для n > 4) и fib(n — 3) — общее подвыражение. Можно его вычислять единожды, а не дважды, так как fib — «чистая» функция, которая не имеет побочных эффектов и результат которой зависит только от аргумента. Разворачивать с удалением общих подвыражений можно не на один уровень, как в примере, а на некоторое число уровней (пока размер результирующего кода разумен, где разумность оценивается даже не столько размером исполняемого файла, сколько размером кеша инструкций центрального процессора).
Предел ожиданий от компилятора — замена нехвостовой рекурсии на хвостовую с накапливающими параметрами и последующая оптимизация хвостового вызова. Но это пока на фантастику похоже.
С устранением одной из рекурсий clang тоже справился. А вот Intel уже нет.
Всё-таки нет у clang'а устранения одного из рекурсивных вызовов: присмотритесь, их по-прежнему два, просто осуществляются они в цикле. Несложная инструментация кода, по крайней мере, показывает, что рекурсивные вызовы осуществляются примерно те же, их лишь чуть меньше, примерно в два раза. А это с учётом экспоненциальной асимптотики почти равносильно замене (по временной сложности) вызова fib(n) вызовом fib(n — 1). Если вы сассемблируете файлы fib.S и fib.nonopt.S, то увидите, что вторая программа медленнее первой как раз примерно вдвое.
Я в комментарии выше предполагал, что компилятор, в принципе, мог бы пройти примерно такой путь:
0. Начнём мы с вами с оригинальной функции:
Компилировать её и все последующие я буду g++-4.8 с флагом -O0, чтобы исполнять ровно то, что хочу исполнять. На моей машине на входе 50 функция fib_00 работает примерно 3 мин. 20 с.
1. Первое, что сделаем — исключительно для удобства выделим отдельные переменные для хранения результатов рекурсивных вызовов:
2. Следующим шагом аккуратно подставим вместо рекурсивных вызовов нечто, максимально приближенное к телу функции fib_00. Это обычный инлайн, такое компиляторы умеют делать давно и поголовно:
В замене первого рекурсивного вызова '(n — 1) > 2' есть ни что иное, как отрицание условия '(n — 1) < 3', выражения-параметры '(n — 1) — 1' и '(n — 1) — 2' я сразу упростил, то есть, сымитировал свёртку констант. Замена второго вызова выполнена аналогично.
Такая несложная оптимизация уже привела к увеличению производительности: время работы примерно 1 мин. 40 с. Вероятно, это связано со снижением накладных расходов на вызов, не таких уж и малых по модулю вычислительной простоты одного вызова функции fib_00 (нужно сделать только одно сравнение (и условный переход) и одно сложение) и 64-битности платформы. Но мы пойдём дальше.
3. Сгруппируем объявления временных переменных перед проверками условий; упростим условия, снова применив свёртку и протягивание констант; заметим, что второе условие может быть истинным только если истинно первое и потому вложим второй условный оператор в тело первого, чтобы не проверять второе условие, если оно заведомо ложно:
Думаю, что происходившее в первом моём комментарии убедительно показывает, что все эти манипуляции вполне по силам оптимизаторам современных компиляторов.
На этом этапе становится очевидным, как возможно применить выделение общих подвыражений: при выполнении условия 'n > 3' выражение 'fib_03(n — 3)' вычислять придётся в любом случае, но результат может пригодиться, если будет выполнено условие 'n > 4'.
4. Выполним выделение общего подвыражения:
Я хочу обратить ваше внимание, прежде чем заявить о результатах такой опимизации, на то, что же произошло с деревом вызовов. А произошло следующее: до сих пор можно было считать, что при каждом уменьшении аргумента на 1 создавалось два рекурсивных вызова (несимметричность дерева вызовов функции fib_00 для простоты проигнорируем). Значит, всего вызовов осуществляется приблизительно 2n (в действительности, вследствие упомянутой несимметричности, основание степени меньше. А именно, более точное значение числа вызовов — φn, где φ — легендарное золотое сечение). Теперь же, во-первых, шаг по дереву вызовов осуществлется через каждое уменьшение аргумента на 2, а не 1 (так как мы заинлайнили тела функции fib_00, мы «схлопнули» каждые два соседних уровня в дереве вызовов в один), а на каждом шаге рекурсивных вызовов осуществляется не 2, а 3. Значит, примерное их число — 3n/2. Что меньше 2n асимптотически! Результат не заставляет себя ждать: эта версия программы отработала менее, чем за 2 с, если быть точным, чуть более, чем в 100 раз быстрее (на том же входе 50) первоначального варианта.
6-9. Я продолжил немного эти простые манипуляции, но здесь их не привожу, поскольку комментарий и так уже чрезмерно велик. Полный листинг и результаты элементарного бенчмарка можно посмотреть здесь. На 9-ом шаге «оптимизации» время работы стало невозможно оценивать утилитой time, так как оно вплотную приблизилось ко времени запуска программы и печати результата. Более точные замеры мне было делать лень, если кто-то захочет этот маленький эксперимент продолжить, не забудьте поделиться результатами :)
Я в комментарии выше предполагал, что компилятор, в принципе, мог бы пройти примерно такой путь:
0. Начнём мы с вами с оригинальной функции:
long long fib_00(int n) {
if (n < 3)
return 1;
return fib_00(n - 1) + fib_00(n - 2);
}
Компилировать её и все последующие я буду g++-4.8 с флагом -O0, чтобы исполнять ровно то, что хочу исполнять. На моей машине на входе 50 функция fib_00 работает примерно 3 мин. 20 с.
1. Первое, что сделаем — исключительно для удобства выделим отдельные переменные для хранения результатов рекурсивных вызовов:
long long fib_01(int n) {
if (n < 3)
return 1;
long long prev1 = fib_01(n - 1);
long long prev2 = fib_01(n - 2);
return prev1 + prev2;
}
2. Следующим шагом аккуратно подставим вместо рекурсивных вызовов нечто, максимально приближенное к телу функции fib_00. Это обычный инлайн, такое компиляторы умеют делать давно и поголовно:
long long fib_02(int n) {
if (n < 3)
return 1;
long long prev1 = 1;
if (n - 1 > 2)
prev1 = fib_02(n - 2) + fib_02(n - 3);
long long prev2 = 1;
if (n - 2 > 2)
prev2 = fib_02(n - 3) + fib_02(n - 4);
return prev1 + prev2;
}
В замене первого рекурсивного вызова '(n — 1) > 2' есть ни что иное, как отрицание условия '(n — 1) < 3', выражения-параметры '(n — 1) — 1' и '(n — 1) — 2' я сразу упростил, то есть, сымитировал свёртку констант. Замена второго вызова выполнена аналогично.
Такая несложная оптимизация уже привела к увеличению производительности: время работы примерно 1 мин. 40 с. Вероятно, это связано со снижением накладных расходов на вызов, не таких уж и малых по модулю вычислительной простоты одного вызова функции fib_00 (нужно сделать только одно сравнение (и условный переход) и одно сложение) и 64-битности платформы. Но мы пойдём дальше.
3. Сгруппируем объявления временных переменных перед проверками условий; упростим условия, снова применив свёртку и протягивание констант; заметим, что второе условие может быть истинным только если истинно первое и потому вложим второй условный оператор в тело первого, чтобы не проверять второе условие, если оно заведомо ложно:
long long fib_03(int n) {
if (n < 3)
return 1;
long long prev1 = 1;
long long prev2 = 1;
if (n > 3) {
prev1 = fib_03(n - 2) + fib_03(n - 3);
if (n > 4)
prev2 = fib_03(n - 3) + fib_03(n - 4);
}
return prev1 + prev2;
}
Думаю, что происходившее в первом моём комментарии убедительно показывает, что все эти манипуляции вполне по силам оптимизаторам современных компиляторов.
На этом этапе становится очевидным, как возможно применить выделение общих подвыражений: при выполнении условия 'n > 3' выражение 'fib_03(n — 3)' вычислять придётся в любом случае, но результат может пригодиться, если будет выполнено условие 'n > 4'.
4. Выполним выделение общего подвыражения:
long long fib_04(int n) {
if (n < 3)
return 1;
long long prev1 = 1;
long long prev2 = 1;
if (n > 3) {
long long prev3 = fib_04(n - 3);
prev1 = fib_04(n - 2) + prev3;
if (n > 4)
prev2 = prev3 + fib_04(n - 4);
}
return prev1 + prev2;
}
Я хочу обратить ваше внимание, прежде чем заявить о результатах такой опимизации, на то, что же произошло с деревом вызовов. А произошло следующее: до сих пор можно было считать, что при каждом уменьшении аргумента на 1 создавалось два рекурсивных вызова (несимметричность дерева вызовов функции fib_00 для простоты проигнорируем). Значит, всего вызовов осуществляется приблизительно 2n (в действительности, вследствие упомянутой несимметричности, основание степени меньше. А именно, более точное значение числа вызовов — φn, где φ — легендарное золотое сечение). Теперь же, во-первых, шаг по дереву вызовов осуществлется через каждое уменьшение аргумента на 2, а не 1 (так как мы заинлайнили тела функции fib_00, мы «схлопнули» каждые два соседних уровня в дереве вызовов в один), а на каждом шаге рекурсивных вызовов осуществляется не 2, а 3. Значит, примерное их число — 3n/2. Что меньше 2n асимптотически! Результат не заставляет себя ждать: эта версия программы отработала менее, чем за 2 с, если быть точным, чуть более, чем в 100 раз быстрее (на том же входе 50) первоначального варианта.
6-9. Я продолжил немного эти простые манипуляции, но здесь их не привожу, поскольку комментарий и так уже чрезмерно велик. Полный листинг и результаты элементарного бенчмарка можно посмотреть здесь. На 9-ом шаге «оптимизации» время работы стало невозможно оценивать утилитой time, так как оно вплотную приблизилось ко времени запуска программы и печати результата. Более точные замеры мне было делать лень, если кто-то захочет этот маленький эксперимент продолжить, не забудьте поделиться результатами :)
Отмечу здесь, чтобы не потерялось.
Clang, оказывается, неплохо умеет «сворачивать» суммы, например, сумму квадратов k по k от 1 до n: пруф. Повторить не смогли ни gcc, ни icc. С суммой кубов Clang, кстати, справится ничуть не хуже.
Clang, оказывается, неплохо умеет «сворачивать» суммы, например, сумму квадратов k по k от 1 до n: пруф. Повторить не смогли ни gcc, ни icc. С суммой кубов Clang, кстати, справится ничуть не хуже.
FACEPALM. И эта статья ещё положительных голосов набрала…
Вы ещё сравните, что быстрее: while(1) или while(1==1)!
Вы ещё сравните, что быстрее: while(1) или while(1==1)!
Положительных — это еще мягко сказано :-)
Дело в том, что есть довольно много людей считающих что «компилятор тупой». А еще хуже, что есть люди, которые так считают и проведут «псевдо бенчмарк». Благодаря плаванию частоты, энергосбережению проца и просто кривым рукам эти люди получат что for быстрее while или наоборот. Сделают вывод и будут это доказывать окружающим.
В этой статье я не делаю открытие для себя или для тех, кому это и «так понятно». Я пытаюсь натолкнуть людей на то, что иногда нужно заглянуть внутрь и внутри совсем не страшно.
UPD. И я думаю есть те, кто спорит про while(1) и while(1==1)
В этой статье я не делаю открытие для себя или для тех, кому это и «так понятно». Я пытаюсь натолкнуть людей на то, что иногда нужно заглянуть внутрь и внутри совсем не страшно.
UPD. И я думаю есть те, кто спорит про while(1) и while(1==1)
Дело в том, что есть довольно много людей считающих что «компилятор тупой».
То, что компилятор не тупой, ваша статья не показывает. Я не знаю, через какую жопу и под какими веществами надо написать компилятор, чтобы он делал существенно разный код для for(;;) и while(1). Есть более интересные примеры для демонстрации возможностей оптимизатора.
В заключительном P. S. я пытался разглядеть сарказм, но, боюсь, его там нет.
Я пытаюсь натолкнуть людей на то, что иногда нужно заглянуть внутрь и внутри совсем не страшно.
В современных реалиях заглядывать внутрь имеет смысл только если пишешь для МК, а тех, кто пишут для МК, учить просматривать асм-листинги не надо (запущенных ардуинщиков я не считаю, но им просматривать листинги не надо по другой причине).
Низкоуровневая оптимизация в ЯВУ — просто феерия тупости. Это имело смысл только лет 20 назад и раньше, когда Си был просто оберткой над асмом. Почитайте различные современные coding-style, а также рекомендации компиляторов gcc, clang и др.: в один голос все говорят: 1) используйте высокоуровневую оптимизацию (= выбор алгоритма с лучшими O-оценками), 2) предпочитайте читаемый и поддерживаемый код перед низкоуровнево-оптимизированным, 3) пожалуйста, не мешайте оптимизатору. Современные оптимизаторы для современных процессоров пишут код лучше людей. Удел людей — алгоритмы, удел компилятора и оптимизатора — машинный код. Не надо мешать друг другу.
К сожалению, ковыряние в битах многим придаёт иллюзию всесильности и власти над тупой железякой.
Гляньте сами результаты опроса внизу моего январского поста.
Гляньте сами результаты опроса внизу моего январского поста.
Что быстрее while (true) или for (;;)?Быстрее? В смысле, какой из двух бесконечных циклов быстрее завершится?
И да, вы забыли поставить запятую или двоеточие после «быстрее».
400438/4096 = 97,763183594Вы забыли перед делением перевести адреса из шестнадцатиричной системы счисления в десятичную, должна получиться 1024-я страница.
400520/4096 = 97,783203125
Пронесло. Страница памяти одна. Да это 97 страница Виртуальной памяти Виртуального адресного пространства процесса.
while (true) и for (;;) идентичны по производительности между собой и с любыми оптимизациями -Ox.Про сравнение производительности бесконечных циклов мне еще слышать не приходилось. Так, надо было лучше бенчмарк провести, чтобы уж наверняка…
смело говорите что “for (;;)” — 8 символов написать быстрее, чем “while (true)” — 12 символов.Ах, ну, если сравнивать так, тогда вы забыли про различные автодополнения редакторов кода, которые значительно ускоряют ввод. Да и
while (true) выглядит более выразительно, читаемо и понятно даже школьнику. И потом, при желании, while (true) всегда можно сократить до while (1).PS:
Нет, вы серьезно? O_o
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Что быстрее while (true) или for (;;)?