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

587

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

Что быстрее?

while(1) {
    // Some code
}

или

while(2) {
    //Some code
}

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

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

Это правда?

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

Николе
источник
202
Полуприличный компилятор оптимизирует обе формы до нуля.
64
В оптимизированной сборке каждые while (n), n! = 0 или for (;;) будут переводиться в бесконечный цикл сборки с меткой в ​​начале и переходом в конец. Точно такой же код, та же производительность.
Алекс Ф
60
Неудивительно, что оптимизация акций приносит 0x100000f90: jmp 0x100000f90(адрес варьируется, очевидно) для обоих фрагментов. Интервьюер, вероятно, хеджировался в тесте регистра против простого помеченного прыжка. И вопрос, и их предположение неубедительны.
WhozCraig
50
Этот вопрос интервьюера подпадает под ту же сторону, что и dilbert.com/strips/comic/1995-11-17 - вы встретите человека, который искренне верит тому, что он говорит, независимо от степени глупости в их утверждении. Просто выберите один из следующих вариантов: глубокий вдох, ругань, смех, плач, некоторая комбинация вышеперечисленного :)
GMasucci
3
@ Майк У: можно задаться вопросом, что должен делать компилятор: перевести на оператор Halt или считать, что цикл завершается через бесконечное время и оптимизировать бесконечную задержку?
Ив Дауст

Ответы:

681

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

Используя 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 ++ и инструкциями процессора, и этот уровень имеет важное значение для производительности.
  • Следовательно, производительность не может быть оценена только с помощью исходного кода.
  • Компилятор должен быть достаточно умен, чтобы оптимизировать такие тривиальные случаи. Программисты не должны тратить свое время на размышления о них в подавляющем большинстве случаев.
ApproachingDarknessFish
источник
196
Возможно, интервьюер не использовал gcc
ММ,
106
@Matt McNabb Это хороший момент, но если интервьюер полагался на оптимизацию для конкретного компилятора, то он должен быть очень откровенным об этом в своем вопросе, и они должны принять ответ «нет разницы» как правильный для некоторые (большинство?) компиляторы.
Джонатан Хартли
109
Чтобы устранить любые сомнения, я протестировал это в clang 3.4.2, и оба цикла производят одинаковую сборку на каждом -Oуровне.
Мартин Турной
16
Я не нахожу это вообще удивительным, поскольку все, что вы поместили в условный раздел циклов, является константами времени компиляции. Таким образом, я подозреваю, что компилятор увидит, что циклы всегда будут истинными или ложными и либо просто jmpвернутся в начало, либо полностью удалят цикл.
sherrellbc
10
@hippietrail Я не понимаю, каким образом содержание (или его отсутствие) цикла может повлиять на эти оптимизации (исключая возможность каких-либо breakоператоров), но я все равно протестировал его, и нет, даже с кодом внутри цикла переход абсолютный и безусловный для обоих while(1)и while(2). Не стесняйтесь проверять других самостоятельно, если вы действительно обеспокоены.
Приближается к
282

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

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

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

Крис Калтер
источник
Мои мысли точно, и именно поэтому, хотя (1) быстрее, лол Хотя я думаю, что это был просто старый случай, когда менеджер пытался убедить себя, что он знает о кодировании, когда он этого не делает, мы все это видели, все хотят быть джедай.
ekerner
8
Абсолютно, это не преувеличение вообще. Определенно, svn-annotate или git blame(или что-то еще) будет использоваться здесь, и в общем случае загрузка истории обвинений в файлах занимает минуты. Тогда, наконец, решить, «а я понимаю, автор написал эту строку, когда только что закончил старшую школу», просто потерял 10 минут ...
v.oddou
11
Отказался, потому что мне надоели условности. Разработчик имеет эту маленькую возможность написать понравившееся ему число, а затем приходит кто-то скучный и недоумевающий, почему это не так 1.
Уткан Гезер
1
Проголосовал из-за риторики. Скорость чтения while (1) точно такая же, как и while (2).
hdante
4
Я прошел через тот же мысленный процесс, который описан в этом ответе минуту назад, когда увидел while(2)в коде (вплоть до рассмотрения вопроса: «Используют ли сопровождающие эту кодовую базу while (n) как неясный механизм комментирования, чтобы циклы выглядели по-другому?») ). Так что нет, вы не преувеличиваете!
Хишам Х.М.
151

Существующие ответы, показывающие код, сгенерированный конкретным компилятором для конкретной цели с определенным набором параметров, не полностью отвечают на вопрос - если только вопрос не был задан в этом конкретном контексте («Что быстрее при использовании 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 ).

Кит Томпсон
источник
8
«В этом случае соответствующие (неявные) константные выражения равны 1! = 0 и 2! = 0, оба из которых оцениваются как значение int 1». Это слишком сложно и неточно. Стандарт просто говорит, что управляющее выражение whileдолжно иметь скалярный тип, и тело цикла повторяется до тех пор, пока выражение не сравняется с 0. Он не говорит, что существует неявное значение expr != 0, которое оценивается ..., которое потребовало бы результата что - 0 или 1 - в свою очередь сравнивать с 0 до бесконечности. Нет, выражение сравнивается с 0, но это сравнение не дает значения. PS Я проголосовал.
Джим Балтер
3
@JimBalter: я понимаю вашу точку зрения и обновлю свой ответ, чтобы устранить ее. Однако я имел в виду, что формулировка стандарта "... пока контрольное выражение не сравнится равным 0" подразумевает оценку <expr> == 0; это то, что «сравнивает равно 0» означает в C. Это сравнение является частью семантики whileцикла. Ни в стандарте, ни в моем ответе нет никакого смысла в том, что результат нужно сравнивать 0снова. (Я должен был написать, ==а не !=.) Но эта часть моего ответа была неясной, и я обновлю ее.
Кит Томпсон
1
«Сравнение равно 0» означает в C - но этот язык в стандарте , а не в C ... реализация выполняет сравнение, она не генерирует сравнение языка C. Вы пишете «оба значения оцениваются как значение int 1», но такого анализа не происходит. Если вы посмотрите на код , созданный для while (2), while (pointer), while (9.67), самым наивным, неоптимизированном компилятором, вы не увидите никакого кода , сгенерированного , что урожайность 0или 1. «Я должен был написать ==, а не! =» - нет, это не имело бы никакого смысла.
Джим Балтер
2
@JimBalter: Хммм. Я не имею в виду, что «сравнение равно 0» подразумевает существование ... == 0выражения C. Моя точка зрения заключается в том, что как «сравнение равно 0», требуемое стандартным описанием whileциклов, так и явное x == 0выражение логически подразумевают одну и ту же операцию. И я думаю, что мучительно наивный компилятор C может генерировать код, который генерирует intзначение 0или 1для любого whileцикла - хотя я не верю, что какой-либо реальный компилятор настолько наивен.
Кит Томпсон
12
Примечание: Это уже на рабочем месте вопрос: workplace.stackexchange.com/questions/4314/...
Joe
141

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

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

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

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

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

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

Янош
источник
6
Это было бы забавно, если бы оно также содержало ответ на вопрос.
Коди Грей
нет, но на самом деле, мы все можем довольно легко представить, что все компиляторы, написанные серьезными компаниями, будут создавать разумный код. давайте возьмем «неоптимизированный случай» / O0, возможно, это закончится так, как анатолиг опубликовал. Тогда вопрос ЦП, будет ли cmpоперанд работать меньше циклов, сравнивая 1 с 0, чем 2 с 0? сколько циклов требуется для выполнения cmp в целом? это переменная в соответствии с битовыми шаблонами? они более «сложные» битовые паттерны, которые замедляются cmp? Я не знаю лично. Вы могли бы представить супердидиотическую реализацию, проверяющую побитно от ранга 0 до n (например, n = 31).
v.oddou
5
Это и моя точка зрения: cmpоперанд должен быть одинаково быстрым для 1 и 200. Возможно, мы могли бы представить идиотские реализации, где это не так. Но можем ли мы представить неидиотическую реализацию, где while(1)быстрее, чем while(200)? Точно так же, если в какой-то доисторический период единственная доступная реализация была такой идиотской, стоит ли нам суетиться об этом сегодня? Я так не думаю, это заостренный разговор с боссом, и настоящая жемчужина в этом!
Янош
@ v.ouddou "будет ли операнд cmp работать меньше циклов, сравнивая от 1 до 0, чем от 2 до 0" - Нет. Вы должны узнать, что такое цикл. «Лично я не знаю. Вы могли бы представить супердидиотическую реализацию, проверяющую понемногу уровень от 0 до n» - или другой способ, по-прежнему делая интервьюера невежественным идиотом. И зачем беспокоиться о проверке по крупицам? Реализация может быть человеком в коробке, который решает сделать перерыв на обед в середине оценки вашей программы.
Джим Балтер
79

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

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

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

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

Но 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

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

anatolyg
источник
28
Этот код действительно то, что компилятор выводит в моей системе. Я не сделал это.
Анатолий
10
IcePack «Операнд для булева типа» - полная чушь. Вы интервьюер? Я предлагаю вам ознакомиться с языком C и его стандартом, прежде чем делать такие заявления.
Джим Балтер
29
"Я не сделал это." - Пожалуйста, не обращайте внимания на пакет со льдом, который говорит глупости. C не имеет логического типа (у него есть _Bool в stdbool.h, но это не то же самое, и семантика whileдавно предшествовала ему), и операнд whileне имеет логического или _Bool или любого другого определенного типа. Операндом whileможет быть любое выражение ... while прерывается на 0 и продолжается не на 0.
Джим Балтер
36
«Обе части кода одинаково быстры, потому что на выполнение обоих требуется бесконечное время», - я подумал о чем-то интересном. Единственный способ завершить бесконечный цикл - перевернуть заряженную частицу или аппаратный сбой: изменение оператора с while (00000001) {}на while (00000000) {}. Чем больше истинных битов, тем меньше вероятность того, что значение перевернется в false. К сожалению, 2 также имеет только один истинный бит. 3, однако, будет работать значительно дольше. Это также относится только к компилятору, который не всегда оптимизирует это (VC ++).
Джонатан Дикинсон
8
@ mr5 Нет. Для того, чтобы немного перевернуть на самом деле привело к чему-то вроде этого, вы говорите о времени выполнения в десятки тысяч лет. Просто мысленный эксперимент. Если вы родом из бессмертной расы, возможно, вы захотите использовать -1, чтобы не допустить влияния бит-флипов на вашу программу.
Джонатан Дикинсон
60

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

1 = 00000001
2 = 00000010

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

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

Райан Кавано
источник
39
Я предположил, что неправильное понимание интервьюера было бы больше похоже на «2 - это int, который должен быть преобразован в логическое значение для использования в условном выражении, тогда как 1 уже является логическим».
Рассел Борогове
7
А если алгоритм сравнения начинается слева, то все наоборот.
Paŭlo Ebermann
1
+1, это именно то, что я думал. Вы могли бы прекрасно представить, что кто-то полагает, что по сути cmpалгоритм ЦП представляет собой линейную проверку битов с ранним выходом из цикла при первом разнице.
v.oddou
1
@PeterCordes «Я никогда не слышал, чтобы кто-то (кроме вас) утверждал, что -O0вывод gcc или clang недостаточно буквален» . Я никогда не говорил таких вещей, и я вообще не имел в виду gcc или лязг. Вы, должно быть, неправильно меня понимаете. Я просто не считаю, что то, что производит MSVC, смешно.
blubberdiblub
1
@PeterCordes Я был неправ, в MSVC точка останова while(1)не прерывается перед циклом, а выражением. Но он все еще разрушается внутри цикла при оптимизации выражения. Возьми этот код с большим количеством перерывов. В неоптимизированном режиме отладки вы получаете это . При оптимизации многие точки останова падают вместе или даже перетекают в следующую функцию (в среде IDE отображаются точки останова во время отладки) - соответствующая разборка .
blubberdiblub
32

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

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

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

Тыну Самуэль
источник
Это действительно превосходно, но while (2) и while (1) явно взяты из комиксов Дильберта. Это НЕ МОЖЕТ быть изобретено кем-то в здравом уме (как кто-то может придумать while (2) как возможную вещь для написания в любом случае?). Если бы ваша гипотеза была верна, то вы бы задали такую ​​уникальную проблему, что могли бы за нее погуглить. Как, например, «while (0xf00b442) медленнее, чем while (1)», как иначе банк мог бы найти вопрос опрашиваемого? Как вы думаете, они являются АНБ и имеют доступ к keycore?
v.oddou
25

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

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

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

OldFrank
источник
19

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

Валентин Раду
источник
14
@ GKFX Если вы дали свой ответ, и они сказали, что вы не правы, нет причины, по которой вы не можете попросить их объяснить, почему. Если Анатолиг прав, и это проверка вашей уверенности в себе, то вам следует объяснить, почему вы ответили так же, как и вы, и спросить их то же самое.
P.Turpie
Я имел в виду первое, что вы им скажете. Не может быть "Почему х быстрее?" «Я не знаю, почему х быстрее?». Очевидно, что, ответив правильно, вы можете спросить.
GKFX
18

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

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

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

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

ouah
источник
10

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

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

UncleKing
источник
8

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

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

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

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

Барт Verkoeijen
источник
1
Если вам не платят за оптимизацию какого-либо кода в реальном времени, для которого вам нужно брить всего 1 или 2 миллисекунды, чтобы соответствовать его требованиям времени выполнения. Конечно, некоторые считают, что это работа для оптимизатора - это если у вас есть оптимизатор для вашей архитектуры.
Neowizard
6

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

for (;;)

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

Том Таннер
источник
2
Вот почему его целесообразно использовать while(2), оно оставляет место для оптимизации, а затем вы просто переключаетесь for (;;)на режим, когда будете готовы к повышению производительности.
Groo
5

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

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

pacoverflow
источник
3

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

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

Питер Вустер
источник
1
Он также сказал: «В устоявшихся инженерных дисциплинах 12% -ное улучшение, легко достижимое, никогда не считается незначительным, и я считаю, что в разработке программного обеспечения должна преобладать та же точка зрения», я думаю, что ходьба неоправданна.
Алиса
3

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

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

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

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

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

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

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

gnasher729
источник
1
Рассуждение о "строках кэша" будет работать только на чипе с очень маленьким кэшем.
Sharp
10
Это не относится к делу. Вопросы о скорости предполагают «все остальное одинаково».
Джим Балтер
6
@JimBalter: Это был не вопрос скорости, это был вопрос о споре с интервьюером. И возможность того, что проведение реального теста может доказать интервьюеру «право» - по причинам, которые не имеют ничего общего с его аргументами, но являются чистым совпадением. Что поставило бы вас в неловкое положение, если бы вы попытались доказать, что он был неправ.
gnasher729
1
@ gnasher729 За исключением логических аргументов, случай совпадения, о котором вы говорите, заслуживает рассмотрения. Но все же слепо верить, что такой случай существует, не только наивно, но и глупо. Пока вы не объясните, что, как или почему это произойдет, этот ответ бесполезен.
user568109
4
@ gnasher729 «Это был не вопрос скорости» - я не буду спорить с людьми, которые используют нечестные риторические приемы.
Джим Балтер
2

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

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

Николай Иванчев
источник
@djechlin - потому что они оба берут 1 цикл процессора.
UncleKing
Константа компилятора сворачивает ее, поэтому она даже не оценивается во время выполнения.
PaulHK
2

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

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

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

ekerner
источник
Откат, который вы сделали, отменяет редактирование пользователем с большим количеством повторений. Эти люди обычно очень хорошо знают политику, и они здесь, чтобы научить их вам. Я считаю, что последняя строка вашего сообщения не добавляет ничего полезного вашему сообщению. Даже если бы я получил шутку, которую я явно пропускаю, я бы посчитал ее слишком болтливой, не стоящей дополнительного абзаца
Палек
@Palec: Спасибо за комментарий. Я обнаружил, что один и тот же парень отредактировал многие из моих сообщений, в основном только для удаления подписи. Поэтому я подумал, что он был просто репутацией тролля, и, следовательно, его репутация. Неужели онлайн-форумы исчерпали язык - и общие вежливости - настолько, что мы больше не подписываем наши труды? может быть, я немного старая школа, но кажется грубым опускать привет и прощаться. Мы используем приложения, но мы все еще люди.
ekerner
1
На Stack бирже , приветствий, слоганы, спасибо и т.д. не приветствуются . То же самое упоминается в справочном центре , особенно при ожидаемом поведении . Ни одна из частей Stack Exchange , даже Stack Overflow , не является форумом - это сайты с вопросами и ответами. Редактирование является одним из отличий. Также комментарии должны служить только для предоставления обратной связи на пост, а не для обсуждения ( Stack Overflow Chat ). И есть много других способов, которыми Q & A отличается от форума. Подробнее об этом в справочном центре и в Meta Stack Overflow .
Палек
Обратите внимание, что если у вас более 2000 повторений (право на редактирование), вы больше не получаете повторений от изменений. Если вы сомневаетесь в том, что редактирование и несогласие с которым вы не согласны, было применено к вашему сообщению, или вы видите чье-то ненадлежащее поведение, спросите об переполнении стека мета . Если редактор сделал что-то не так, он может быть уведомлен модом (может быть, они не понимают) или даже быть наказан каким-либо образом (если поведение было преднамеренно вредоносным). В противном случае вы получите указатели на объяснение, почему редактирование / поведение правильное. Ненужный откат загромождает историю ревизий и может втянуть вас в откатную войну. Я возвращаюсь только тогда, когда действительно уверен, что редактирование неверно.
Палек
Наконец, о подписании, приветствии…: может показаться грубым не включать эти формальности, но это увеличивает отношение сигнал / шум, и информация не теряется. Вы можете выбрать любой псевдоним, который вы хотите, это ваша подпись. В большинстве мест у вас есть свой аватар.
Палек
1

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

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

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

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

user143522
источник
0

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

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

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

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

Антонин ГАВРЕЛЬ
источник
Зачем ему предлагать цикл do {} while? Хотя (1) (или while (2)) делает то же самое.
Catsunami
do while удаляет один дополнительный прыжок, чтобы улучшить производительность. Конечно, в случае, если вы знаете, что цикл будет выполнен хотя бы один раз
Антонин ГАВРЕЛЬ
0

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

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

#define while(x) sleep(x);

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

chqrlie
источник
@MaxB: действительно, трюк с макросами должен быть еще более искаженным. Я думаю, что новая версия должна работать, хотя и не гарантируется стандартом C.
Chqrlie
-4

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

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

    cmp eax, 2

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

    а. 00000000 - 00000010 cmp eax, 2

    вместо

    б. 00000000 - 00000001 cmp eax, 1

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

hdost
источник
15
CMP собирается взять 1 цикл процессора независимо от обоих случаев.
UncleKing
8
Этот код будет неверным. Правильный код будет загружать либо 2, либо 1 в регистр eax, затем сравнивать eax с 0.
gnasher729