Что быстрее: 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)"? Если нет, то почему люди используют это?

22 ответа

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

Используя 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 (;;)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#define while sleep

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

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

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

    cmp eax, 2

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

    а. 00000000 - 00000010 cmp eax, 2

    вместо

    б. 00000000 - 00000001 cmp eax, 1

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

Другие вопросы по тегам