Что быстрее: while (1) или while (2)?

Это был вопрос интервью, заданный старшим менеджером.

Что быстрее?

while(1) {
    // Some code
}

или

while(2) {
    //Some code
}

Я сказал, что оба имеют одинаковую скорость выполнения, так как выражение внутри whileдолжно наконец вычислить trueили false. В этом случае оба trueвыполняются, и внутри whileусловия нет никаких дополнительных условных инструкций . Таким образом, оба будут иметь одинаковую скорость выполнения, и я предпочитаю while (1).

Но интервьюер уверенно сказал: «Проверьте свои основы. while(1)Это быстрее, чем while(2)». (Он не проверял мою уверенность)

Это правда?

См. Также: "for (;;)" быстрее, чем "while (TRUE)"? Если нет, то почему люди используют это?

Оба цикла бесконечны, но мы можем видеть, какой из них требует больше инструкций / ресурсов за одну итерацию.

Используя gcc, я скомпилировал две следующие программы для сборки на разных уровнях оптимизации:

int main(void) {
    while(1) {}
    return 0;
}

int main(void) {
    while(2) {}
    return 0;
}

Даже без оптимизации ( -O0) сгенерированная сборка была идентична для обеих программ . Следовательно, нет разницы в скорости между двумя петлями.

Для справки вот сгенерированная сборка (используется gcc main.c -S -masm=intelс флагом оптимизации):

С -O0:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    push    rbp
    .seh_pushreg    rbp
    mov rbp, rsp
    .seh_setframe   rbp, 0
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

С -O1:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

С -O2и -O3(тот же вывод):

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Фактически, сборка, сгенерированная для цикла, идентична для каждого уровня оптимизации:

 .L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Важными моментами являются:

.L2:
    jmp .L2

Я не могу читать сборку очень хорошо, но это, безусловно, безусловный цикл. jmpИнструкция безоговорочно сбрасывает программу обратно на .L2этикетке, даже не сравнивая значение против истины, и, конечно , сразу же делает это снова , пока программа не будет каким - то образом закончилась. Это напрямую соответствует коду C / C ++:

L2:
    goto L2;

Редактировать:

Интересно, что даже без оптимизации все следующие циклы производили одинаковый вывод (безусловный jmp) в сборке:

while(42) {}

while(1==1) {}

while(2==2) {}

while(4<7) {}

while(3==3 && 4==4) {}

while(8-9 < 0) {}

while(4.3 * 3e4 >= 2 << 6) {}

while(-0.1 + 02) {}

И даже к моему изумлению:

#include<math.h>

while(sqrt(7)) {}

while(hypot(3,4)) {}

Все становится немного интереснее с пользовательскими функциями:

int x(void) {
    return 1;
}

while(x()) {}

#include<math.h>

double x(void) {
    return sqrt(7);
}

while(x()) {}

На -O0самом деле, эти два примера фактически вызывают xи выполняют сравнение для каждой итерации.

Первый пример (возвращается 1):

.L4:
    call    x
    testl   %eax, %eax
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Второй пример (возвращение sqrt(7)):

.L4:
    call    x
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jp  .L4
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Однако, как -O1и выше, они оба производят ту же сборку, что и предыдущие примеры (безусловное jmpвозвращение к предыдущей метке).

TL; DR

В GCC различные циклы компилируются в одинаковую сборку. Компилятор оценивает значения констант и не выполняет никакого фактического сравнения.

Мораль этой истории такова:

• Существует слой трансляции между исходным кодом C ++ и инструкциями процессора, и этот уровень имеет важное значение для производительности.
• Следовательно, производительность не может быть оценена только с помощью исходного кода.
• Компилятор должен быть достаточно умен, чтобы оптимизировать такие тривиальные случаи. Программисты не должны тратить свое время на размышления о них в подавляющем большинстве случаев.

Да, while(1)намного быстрее , чем while(2), для человека , чтобы читать! Если я вижу while(1)в незнакомой кодовой базе, я сразу знаю, что задумал автор, и мои глазные яблоки могут перейти к следующей строке.

Если я увижу while(2), я, вероятно, остановлюсь в своих треках и попытаюсь выяснить, почему автор не написал while(1). У автора проскользнул палец на клавиатуре? Используют ли разработчики этой кодовой базы while(n)в качестве скрытого механизма комментирования, чтобы циклы выглядели иначе? Это грубый обходной путь для ложного предупреждения в каком-то сломанном инструменте статического анализа? Или это подсказка, что я читаю сгенерированный код? Это ошибка, возникшая из-за опрометчивого поиска и замены всех, или неудачного слияния, или космического луча? Может быть, эта строка кода должна сделать что-то совершенно другое. Может быть, это должно было прочитать while(w)или while(x2). Я бы лучше нашел автора в истории файла и отправил им электронное письмо "WTF" ... и теперь я нарушил свой ментальный контекст.while(2)while(1) заняло бы долю секунды!

Я преувеличиваю, но только немного. Читаемость кода действительно важна. И это стоит упомянуть в интервью!

Существующие ответы, показывающие код, сгенерированный конкретным компилятором для конкретной цели с определенным набором параметров, не полностью отвечают на вопрос - если только вопрос не был задан в этом конкретном контексте («Что быстрее при использовании gcc 4.7.2 для x86_64» с параметрами по умолчанию? ", например).

Что касается определения языка, в абстрактной машине while (1) оценивается целочисленная константа 1и while (2)вычисляется целочисленная константа 2; в обоих случаях результат сравнивается на равенство нулю. Языковой стандарт абсолютно ничего не говорит об относительной производительности двух конструкций.

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

С другой стороны, компиляторы C обязательно должны оценивать некоторые константные выражения во время компиляции, когда они появляются в контекстах, которые требуют константного выражения. Например, это:

int n = 4;
switch (n) {
    case 2+2: break;
    case 4:   break;
}

требует диагностики; Ленивый компилятор не имеет возможности отложить оценку 2+2до времени выполнения. Поскольку компилятор должен иметь возможность оценивать константные выражения во время компиляции, у него нет веских оснований не использовать эту возможность, даже если она не требуется.

Стандарт C ( N1570 6.8.5p4) гласит, что

Оператор итерации приводит к многократному выполнению оператора, называемого телом цикла, до тех пор, пока управляющее выражение не сравнится с 0.

Таким образом, соответствующие константные выражения 1 == 0и 2 == 0, оба из которых оценивают intзначение 0. (Эти сравнения неявны в семантике whileцикла; они не существуют как фактические выражения C).

Извращенно наивный компилятор может генерировать разный код для двух конструкций. Например, для первого он может генерировать безусловный бесконечный цикл (рассматриваемый 1как особый случай), а для второго он может генерировать явное сравнение во время выполнения, эквивалентное 2 != 0. Но я никогда не сталкивался с компилятором C, который бы на самом деле вел себя таким образом, и я серьезно сомневаюсь, что такой компилятор существует.

Большинство компиляторов (я хочу сказать, что все компиляторы производственного качества) имеют опции для запроса дополнительной оптимизации. При такой опции еще менее вероятно, что любой компилятор сгенерирует разный код для двух форм.

Если ваш компилятор генерирует разный код для двух конструкций, сначала проверьте, действительно ли разные последовательности кода имеют разную производительность. Если это так, попробуйте снова скомпилировать с опцией оптимизации (если есть). Если они все еще различаются, отправьте отчет об ошибке поставщику компилятора. Это не обязательно ошибка в смысле несоответствия стандарту C, но это почти наверняка проблема, которую следует исправить.

Итог: while (1)и while(2) почти наверняка имеют одинаковую производительность. Они имеют одинаковую семантику, и у любого компилятора нет веской причины не генерировать идентичный код.

И хотя для компилятора совершенно законно генерировать более быстрый код, while(1)чем для while(2), для компилятора одинаково законно генерировать более быстрый код, while(1)чем для другого вхождения while(1)в той же программе.

(Есть еще один вопрос, неявный из того, который вы задали: как вы справляетесь с интервьюером, который настаивает на неправильной технической точке. Это, вероятно, будет хорошим вопросом для сайта Workplace ).

Подожди минуту. Интервьюер, он похож на этого парня?

Достаточно того, что сам интервьюер провалил это интервью, а что если другие программисты в этой компании «сдали» этот тест?

Нет. Оценивать высказывания 1 == 0и 2 == 0 следует одинаково быстро. Мы могли бы представить плохие реализации компилятора, где один может быть быстрее другого. Но нет веской причины, почему один должен быть быстрее другого.

Даже если есть какое-то неясное обстоятельство, когда утверждение было бы правдой, программисты не должны оцениваться на основе знания неясных (и в этом случае жутких) мелочей. Не беспокойтесь об этом интервью, лучший шаг здесь - уйти.

Отказ от ответственности: это не оригинальный мультфильм Дилберта. Это просто мэшап .

Ваше объяснение верно. Это, кажется, вопрос, который проверяет вашу уверенность в себе в дополнение к техническим знаниям.

Кстати, если вы ответили

Обе части кода одинаково быстры, потому что оба требуют бесконечного времени для завершения

интервьюер скажет

Но while (1)может делать больше итераций в секунду; можешь объяснить почему? (это чепуха; снова проверяю свою уверенность)

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

Вот пример кода, сгенерированного компилятором в моей системе (MS Visual Studio 2012) с отключенными оптимизациями:

yyy:
    xor eax, eax
    cmp eax, 1     (or 2, depending on your code)
    je xxx
    jmp yyy
xxx:
    ...

С включенными оптимизациями:

xxx:
    jmp xxx

Таким образом, сгенерированный код точно такой же, по крайней мере, с оптимизирующим компилятором.

Наиболее вероятное объяснение этого вопроса заключается в том, что интервьюер считает, что процессор проверяет отдельные биты чисел, один за другим, пока не достигнет ненулевого значения:

1 = 00000001
2 = 00000010

Если "ноль?" Алгоритм запускается с правой стороны числа и должен проверять каждый бит, пока не достигнет ненулевого бита, while(1) { }цикл должен будет проверять вдвое больше битов на итерацию, чем while(2) { }цикл.

Это требует очень неправильной ментальной модели работы компьютеров, но у нее есть своя внутренняя логика. Одним из способов проверки было бы спросить, будет ли while(-1) { }или while(3) { }будет одинаково быстро, или если while(32) { }будет еще медленнее .

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

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

Но, конечно, я не знаю, я просто предлагаю один вариант.

Я думаю, что ключ к этому можно найти в «вопросе старшего менеджера». Этот человек, очевидно, прекратил программировать, когда стал менеджером, а затем ему потребовалось несколько лет, чтобы стать старшим менеджером. Никогда не терял интереса к программированию, но никогда не писал строки с тех дней. Таким образом, он упоминает не «какой-нибудь достойный компилятор», как упоминают некоторые ответы, а «компилятор, с которым этот человек работал 20-30 лет назад».

В то время программисты тратили значительную часть своего времени, пробуя различные методы для ускорения и повышения эффективности своего кода, поскольку время ЦП «центрального миникомпьютера» было таким ценным. Как и люди, пишущие компиляторы. Я предполагаю, что единственный компилятор, который его компания сделала доступным в то время, был оптимизирован на основе «часто встречающихся утверждений, которые можно оптимизировать», и он столкнулся с некоторой краткостью, когда столкнулся с while (1) и оценил все еще, включая время (2). Наличие такого опыта может объяснить его позицию и его уверенность в этом.

Вероятно, лучший способ нанять вас - это способ, который позволит старшему менеджеру увлечься и дать вам 2-3 минуты лекций о «старых добрых днях программирования», прежде чем ВЫ плавно поведете его к следующему предмету интервью. (Хорошее время важно здесь - слишком быстро, и вы прерываете историю - слишком медленно, и вы помечены как человек с недостаточным вниманием). Скажите ему в конце интервью, что вам будет очень интересно узнать больше об этой теме.

Вы должны были спросить его, как он пришел к такому выводу. Под любым приличным компилятором эти два компилируются с одинаковыми инструкциями asm. Итак, он должен был сказать вам компилятор, чтобы начать. И даже в этом случае вам придется очень хорошо знать компилятор и платформу, чтобы сделать теоретическое предположение. И в конце концов, на практике это не имеет значения, поскольку существуют другие внешние факторы, такие как фрагментация памяти или загрузка системы, которые будут влиять на цикл больше, чем эта деталь.

Ради этого вопроса я должен добавить, что я помню, как Дуг Гвин из C Committee писал, что некоторые ранние компиляторы C без прохода оптимизатора генерировали бы тест в сборке для while(1)(по сравнению с for(;;)которым его не будет).

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

• без оптимизатора пройти компилятор сгенерирует тест для обоих while(1)иwhile(2)
• с пропуском оптимизатора компилятор получает указание оптимизировать (с безусловным переходом) все, while(1)потому что они рассматриваются как идиоматические. Это оставило бы while(2)с тестом и, следовательно, делает разницу в производительности между ними.

Конечно, я бы добавил к интервьюеру, что неучтение while(1)и while(2)одна и та же конструкция является признаком некачественной оптимизации, поскольку это эквивалентные конструкции.

Другой вариант такого вопроса - посмотреть, хватит ли у вас смелости сказать своему менеджеру, что он / она ошибается! И как тихо ты можешь это передать.

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

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

Мой ответ будет; это не имеет большого значения, я скорее сосредотачиваюсь на бизнес-проблеме, которую мы решаем. В конце концов, за это мне и заплатят.

Кроме того, я бы выбрал, while(1) {}потому что это более распространено, и другим товарищам по команде не нужно было бы тратить время, чтобы выяснить, почему кто-то выбрал бы большее число, чем 1.

Теперь иди написать код. ;-)

Если вы беспокоитесь об оптимизации, вы должны использовать

for (;;)

потому что это не имеет никаких испытаний. (циничный режим)

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

Компания хочет увидеть, как вы отреагируете в этой ситуации. Сидите ли вы тихо и не настаиваете, что ваш ответ правильный, из-за неуверенности в себе или страха расстроить интервьюера? Или вы готовы бросить вызов авторитету, который, как вы знаете, неправ? Они хотят узнать, готовы ли вы отстаивать свои убеждения и можете ли вы сделать это тактично и уважительно.

Раньше я программировал C и ассемблерный код, когда такая чепуха могла иметь значение. Когда это имело значение, мы написали это на Ассамблее.

Если бы мне задали этот вопрос, я бы повторил знаменитую цитату Дональда Кнута 1974 года о преждевременной оптимизации и пошел бы, если бы интервьюер не смеялся и не шел дальше.

Может быть, интервьюер намеренно задал такой тупой вопрос и попросил вас сделать 3 замечания:

1. Основные рассуждения. Обе петли бесконечны, сложно говорить о производительности.
2. Знание об уровнях оптимизации. Он хотел услышать от вас, что если вы позволите компилятору выполнить какую-либо оптимизацию за вас, это оптимизирует условия, особенно если блок не был пустым.
3. Знание микропроцессорной архитектуры. Большинство архитектур имеют специальную инструкцию процессора для сравнения с 0 (хотя не обязательно быстрее).

Вот проблема: если вы на самом деле пишете программу и измеряете ее скорость, скорость обоих циклов может быть разной! Для некоторого разумного сравнения:

unsigned long i = 0;
while (1) { if (++i == 1000000000) break; }

unsigned long i = 0;
while (2) { if (++i == 1000000000) break; }

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

В худшем случае: оптимизирующий компилятор не выясняет, что делает цикл, но выясняет, что значения, полученные при выполнении второго цикла, те же, что и в первом. И сгенерируйте полный код для первого цикла, но не для второго.

Они оба равны - одинаковы.

Согласно спецификациям все, что не равно 0, считается истинным, поэтому даже без какой-либо оптимизации, и хороший компилятор не будет генерировать код для while (1) или while (2). Компилятор сгенерирует простую проверку != 0.

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

И чтобы тратить на это еще больше времени ...

«Хотя (2)» смешно, потому что,

«while (1)» и «while (true)» исторически используются для создания бесконечного цикла, который ожидает, что «break» будет вызван на некотором этапе внутри цикла на основе условия, которое непременно произойдет.

«1» просто для того, чтобы всегда принимать значение «истина», и поэтому сказать «while (2)» почти так же глупо, как сказать «while (1 + 1 == 2)», которое также будет принимать значение «истина».

И если вы хотите быть полностью глупым, просто используйте: -

while (1 + 5 - 2 - (1 * 3) == 0.5 - 4 + ((9 * 2) / 4)) {
    if (succeed())
        break;
}

Я хотел бы думать, что ваш кодер сделал опечатку, которая не повлияла на выполнение кода, но если он намеренно использовал «2» просто для того, чтобы быть странным, то уволите его, прежде чем он пропустит странный шут по всему вашему коду, затрудняя читать и работать с.

Это зависит от компилятора.

Если он оптимизирует код или если он оценивает 1 и 2 как true с тем же числом команд для определенного набора команд, скорость выполнения будет одинаковой.

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

Я имею в виду: это не вопрос, связанный с языком (С).

Поскольку люди, желающие ответить на этот вопрос, хотят самый быстрый цикл, я бы ответил, что оба они одинаково компилируются в один и тот же код сборки, как указано в других ответах. Тем не менее, вы можете предложить интервьюеру использовать «развертывание цикла»; цикл do {} вместо цикла while.

Осторожно: вам нужно убедиться, что цикл по крайней мере всегда будет запускаться один раз .

Цикл должен иметь условие разрыва внутри.

Также для такого цикла я лично предпочел бы использовать do {} while (42), так как любое целое число, кроме 0, сделало бы эту работу.

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

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

#define while(x) sleep(x);

это действительно сделает while(1)вдвое быстрее (или вдвое медленнее), чем while(2).

Единственная причина, по которой я могу думать, почему это while(2)будет медленнее, это:

1. Код оптимизирует цикл до

   cmp eax, 2

2. Когда происходит вычитание, вы по существу вычитаете

   а. 00000000 - 00000010 cmp eax, 2

   вместо

   б. 00000000 - 00000001 cmp eax, 1

cmpтолько устанавливает флаги и не устанавливает результат. Итак, по наименее значимым битам мы знаем, нужно ли нам брать или нет с b . В то время как с вы должны выполнить два вычитания , прежде чем получить заем.