c - tag - shopify liquid variable




Qual é mais rápido: while(1) ou while(2)? (15)

É claro que não conheço as reais intenções desse gerente, mas proponho uma visão completamente diferente: ao contratar um novo membro em equipe, é útil saber como ele reage a situações de conflito.

Eles te levaram a um conflito. Se isso é verdade, eles são espertos e a pergunta era boa. Para alguns setores, como o setor bancário, postar seu problema no Stack Overflow pode ser um motivo de rejeição.

Mas é claro que eu não sei, apenas proponho uma opção.

Esta foi uma pergunta da entrevista feita por um gerente sênior.

O que é mais rápido?

while(1) {
    // Some code
}

ou

while(2) {
    //Some code
}

Eu disse que ambos têm a mesma velocidade de execução, já que a expressão interna deve finalmente ser avaliada como true ou false . Nesse caso, ambos são avaliados como true e não há instruções condicionais extras dentro da condição while . Então, ambos terão a mesma velocidade de execução e eu prefiro enquanto (1).

Mas o entrevistador disse confiante: "Verifique seu básico. while(1) é mais rápido que while(2) ." (Ele não estava testando minha confiança)

Isso é verdade?

Veja também: "for (;;)" mais rápido que "while (TRUE)"? Se não, por que as pessoas usam isso?


A explicação mais provável para a pergunta é que o entrevistador acha que o processador verifica os bits individuais dos números, um por um, até atingir um valor diferente de zero:

1 = 00000001
2 = 00000010

Se o "é zero?" O algoritmo inicia do lado direito do número e tem que verificar cada bit até que ele atinja um bit diferente de zero; o loop while(1) { } teria que verificar o dobro de bits por iteração do while(2) { } loop.

Isso requer um modelo mental muito errado de como os computadores funcionam, mas tem sua própria lógica interna. Uma maneira de verificar seria perguntar se while(-1) { } ou while(3) { } seria igualmente rápido, ou se while(32) { } seria ainda mais lento .


Ambos os loops são infinitos, mas podemos ver qual deles leva mais instruções / recursos por iteração.

Usando o gcc, eu compilei os dois programas a seguir para montagem em diferentes níveis de otimização:

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


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

Mesmo sem otimizações ( -O0 ), o assembly gerado era idêntico para ambos os programas . Portanto, não há diferença de velocidade entre os dois loops.

Para referência, aqui está o assembly gerado (usando gcc main.c -S -masm=intel com um sinalizador de otimização):

Com -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"

Com -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"

Com -O2 e -O3 (mesma saída):

    .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"

Na verdade, o assembly gerado para o loop é idêntico para todos os níveis de otimização:

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

Os bits importantes sendo:

.L2:
    jmp .L2

Eu não consigo ler assembly muito bem, mas isso é obviamente um loop incondicional. A instrução jmp reconfigura incondicionalmente o programa de volta ao rótulo .L2 sem comparar um valor com o valor true e, claro, imediatamente faz isso novamente até que o programa seja de alguma forma terminado. Isso corresponde diretamente ao código C / C ++:

L2:
    goto L2;

Editar:

Curiosamente, mesmo sem otimizações , os loops a seguir produziram exatamente a mesma saída ( jmp incondicional) na montagem:

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) {}

E até para minha surpresa:

#include<math.h>

while(sqrt(7)) {}

while(hypot(3,4)) {}

As coisas ficam um pouco mais interessantes com funções definidas pelo usuário:

int x(void) {
    return 1;
}

while(x()) {}


#include<math.h>

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

while(x()) {}

Em -O0 , esses dois exemplos realmente chamam x e executam uma comparação para cada iteração.

Primeiro exemplo (retornando 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"

Segundo exemplo (retornando o 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"

No entanto, em -O1 e acima, ambos produzem o mesmo assembly que os exemplos anteriores (um jmp incondicional de volta ao rótulo anterior).

TL; DR

No GCC, os diferentes loops são compilados para montagem idêntica. O compilador avalia os valores constantes e não se incomoda em realizar qualquer comparação real.

A moral da história é:

  • Existe uma camada de tradução entre o código-fonte do C ++ e as instruções da CPU, e essa camada tem implicações importantes para o desempenho.
  • Portanto, o desempenho não pode ser avaliado observando apenas o código-fonte.
  • O compilador deve ser inteligente o suficiente para otimizar esses casos triviais. Os programadores não devem perder tempo pensando sobre eles na grande maioria dos casos.

As respostas existentes que mostram o código gerado por um compilador específico para um determinado destino com um conjunto particular de opções não respondem totalmente à questão - a menos que a pergunta tenha sido feita nesse contexto específico ("O que é mais rápido usando gcc 4.7.2 para x86_64" com opções padrão? ", por exemplo).

No que diz respeito à definição da linguagem, na máquina abstrata, while (1) avalia a constante inteira 1 , e while (2) avalia a constante inteira 2 ; em ambos os casos, o resultado é comparado por igualdade a zero. O padrão de linguagem não diz absolutamente nada sobre o desempenho relativo dos dois construtos.

Eu posso imaginar que um compilador extremamente ingênuo pode gerar código de máquina diferente para os dois formulários, pelo menos quando compilado sem solicitar otimização.

Por outro lado, os compiladores C devem avaliar algumas expressões constantes em tempo de compilação, quando aparecem em contextos que exigem uma expressão constante. Por exemplo, isso:

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

requer um diagnóstico; um compilador preguiçoso não tem a opção de adiar a avaliação de 2+2 até o tempo de execução. Como um compilador precisa ter a capacidade de avaliar expressões constantes em tempo de compilação, não há uma boa razão para não aproveitar essa capacidade mesmo quando não é necessário.

O padrão C ( N1570 6.8.5p4) diz que

Uma instrução de iteração faz com que uma instrução chamada corpo de loop seja executada repetidamente até que a expressão de controle seja igual a 0.

Portanto, as expressões constantes relevantes são 1 == 0 e 2 == 0 , sendo que ambas avaliam o valor int 0 . (Essas comparações estão implícitas na semântica do loop while; elas não existem como expressões C reais.)

Um compilador perversamente ingênuo poderia gerar código diferente para as duas construções. Por exemplo, para o primeiro, ele poderia gerar um loop infinito incondicional (tratando 1 como um caso especial) e, para o segundo, gerar uma comparação explícita em tempo de execução equivalente a 2 != 0 . Mas eu nunca encontrei um compilador C que realmente se comportaria dessa maneira, e duvido seriamente que tal compilador exista.

A maioria dos compiladores (estou tentado a dizer todos os compiladores com qualidade de produção) tem opções para solicitar otimizações adicionais. Sob essa opção, é ainda menos provável que qualquer compilador gere código diferente para os dois formulários.

Se o seu compilador gerar código diferente para as duas construções, primeiro verifique se as diferentes sequências de código realmente têm desempenho diferente. Se sim, tente compilar novamente com uma opção de otimização (se disponível). Se eles ainda diferirem, envie um relatório de bug para o fornecedor do compilador. Não é (necessariamente) um bug no sentido de uma falha em se adequar ao padrão C, mas é quase certamente um problema que deve ser corrigido.

Bottom line: while (1) e while(2) quase certamente têm o mesmo desempenho. Eles têm exatamente a mesma semântica, e não há uma boa razão para qualquer compilador não gerar código idêntico.

E embora seja perfeitamente legal para um compilador gerar código mais rápido para while(1) que para while(2) , é igualmente legal para um compilador gerar código mais rápido por while(1) que por outra ocorrência de while(1) no mesmo programa.

(Há outra questão implícita na pergunta que você fez: como você lida com um entrevistador que insiste em um ponto técnico incorreto? Essa provavelmente seria uma boa pergunta para o site Workplace ).


Eu costumava programar o código C e Assembly de volta quando esse tipo de absurdo poderia ter feito alguma diferença. Quando isso fez diferença, escrevemos em Assembly.

Se me fizessem essa pergunta, eu teria repetido a famosa citação de Donald Knuth, em 1974, sobre otimização prematura, e andei se o entrevistador não riu e seguiu em frente.


Outra questão seria ver se você tem coragem de dizer ao seu gerente que ele está errado! E quão suavemente você pode comunicar isso.

Meu primeiro instinto teria sido gerar saída de montagem para mostrar ao gerente que qualquer compilador decente deveria cuidar disso, e se não estiver fazendo isso, você enviará a próxima atualização para ele :)


Para ver tantas pessoas se aprofundando nesse problema, mostra exatamente por que isso pode muito bem ser um teste para ver com que rapidez você quer otimizar as coisas.

Minha resposta seria; Não importa muito, eu prefiro focar no problema de negócios que estamos resolvendo. Afinal, é para isso que vou ser pago.

Além disso, eu optaria por while(1) {} porque é mais comum, e outros companheiros de equipe não precisariam gastar tempo para descobrir por que alguém escolheria um número maior que 1.

Agora vá escrever algum código. ;-)


Parece-me que esta é uma daquelas questões de entrevista comportamental mascaradas como uma questão técnica. Algumas empresas fazem isso - elas fazem uma pergunta técnica que deve ser bastante fácil para qualquer programador competente responder, mas quando o entrevistado dá a resposta correta, o entrevistador diz que está errado.

A empresa quer ver como você reagirá nessa situação. Você senta lá quieto e não diz que sua resposta está correta, devido a dúvidas ou medo de perturbar o entrevistador? Ou você está disposto a desafiar uma pessoa com autoridade que você sabe que está errada? Eles querem ver se você está disposto a defender suas convicções e se pode fazê-lo de maneira diplomática e respeitosa.


Sua explicação está correta. Esta parece ser uma questão que testa sua autoconfiança além do conhecimento técnico.

By the way, se você respondeu

Ambos os trechos de código são igualmente rápidos, porque ambos levam tempo infinito para completar

o entrevistador diria

Mas while (1) pode fazer mais iterações por segundo; você pode explicar por quê? (isso é um absurdo; teste sua confiança novamente)

Então, respondendo como você, você economizou algum tempo que, de outra forma, você desperdiçaria ao discutir essa má pergunta.

Aqui está um código de exemplo gerado pelo compilador no meu sistema (MS Visual Studio 2012), com otimizações desativadas:

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

Com as otimizações ativadas:

xxx:
    jmp xxx

Portanto, o código gerado é exatamente o mesmo, pelo menos com um compilador otimizado.


Você deveria ter perguntado a ele como ele chegou a essa conclusão. Sob qualquer compilador decente, os dois compilam as mesmas instruções. Então, ele deveria ter dito a você o compilador também para começar. E mesmo assim, você teria que conhecer muito bem o compilador e a plataforma para fazer uma estimativa teórica. E, no final, isso realmente não importa na prática, já que existem outros fatores externos, como fragmentação da memória ou carga do sistema, que influenciarão o loop mais do que esse detalhe.


Ambos são iguais - o mesmo.

De acordo com as especificações, qualquer coisa que não seja 0 é considerada verdadeira, portanto, mesmo sem qualquer otimização, e um bom compilador não gerará nenhum código para while (1) ou while (2). O compilador geraria uma verificação simples para != 0.


Isso depende do compilador.

Se otimizar o código, ou se ele avaliar 1 e 2 para true com o mesmo número de instruções para um conjunto de instruções específico, a velocidade de execução será a mesma.

Em casos reais, sempre será igualmente rápido, mas seria possível imaginar um compilador em particular e um sistema particular, quando isso seria avaliado de maneira diferente.

Quero dizer: isso não é realmente uma questão relacionada à linguagem (C).


Talvez o entrevistador tenha feito essa pergunta idiota intencionalmente e queria que você fizesse 3 pontos:

  1. Raciocínio básico. Ambos os loops são infinitos, é difícil falar sobre desempenho.
  2. Conhecimento sobre níveis de otimização. Ele queria ouvir de você se você deixasse o compilador fazer alguma otimização para você, isso otimizaria a condição, especialmente se o bloco não estivesse vazio.
  3. Conhecimento sobre arquitetura de microprocessador. A maioria das arquiteturas tem uma instrução de CPU especial para comparação com 0 (embora não necessariamente mais rápida).

A única razão pela qual eu consigo pensar em por que o while(2)que seria mais lento é:

  1. O código otimiza o loop para

    cmp eax, 2

  2. Quando a subtração ocorre, você está essencialmente subtraindo

    uma. 00000000 - 00000010 cmp eax, 2

    ao invés de

    b. 00000000 - 00000001 cmp eax, 1

cmpdefine apenas sinalizadores e não define um resultado. Então nos bits menos significativos sabemos se precisamos emprestar ou não com b . Considerando que com um você tem que executar duas subtrações antes de obter um empréstimo.


Como as pessoas que querem responder a esta pergunta querem o loop mais rápido, eu teria respondido que ambas estão compilando igualmente no mesmo código de assembly, conforme indicado nas outras respostas. No entanto, você pode sugerir ao entrevistador que use o 'desenrolamento de loop'; a do {} while loop em vez do loop while.

Cauteloso: Você precisa garantir que o loop seja executado sempre pelo menos uma vez .

O loop deve ter uma condição de quebra dentro.

Também para esse tipo de loop eu pessoalmente preferiria o uso de {} while (42), já que qualquer inteiro, exceto 0, faria o trabalho.





while-loop