c++ - titulo - title tag e title heading




É<mais rápido que<=? (9)

TL;DR resposta TL;DR

Para a maioria das combinações de arquitetura, compilador e linguagem, não será mais rápido.

Resposta completa

Outras respostas se concentraram na arquitetura x86 , e eu não conheço a arquitetura ARM (que seu montador de exemplo parece ser) bem o suficiente para comentar especificamente sobre o código gerado, mas este é um exemplo de uma micro-optimisation que é muito arquitetura específico, e é tão provável que seja uma anti-otimização quanto uma otimização .

Como tal, eu sugeriria que esse tipo de micro-optimisation é um exemplo de programação de cultos de carga , em vez da melhor prática de engenharia de software.

Existem provavelmente algumas arquiteturas onde isso é uma otimização, mas eu conheço pelo menos uma arquitetura onde o oposto pode ser verdadeiro. A venerável arquitetura Transputer só tinha instruções de código de máquina para igual e maior que ou igual a , então todas as comparações tinham que ser construídas a partir dessas primitivas.

Mesmo assim, em quase todos os casos, o compilador podia ordenar as instruções de avaliação de tal forma que, na prática, nenhuma comparação tivesse qualquer vantagem sobre qualquer outra. No pior caso, pode ser necessário adicionar uma instrução inversa (REV) para trocar os dois itens principais na pilha do operando . Esta foi uma instrução de byte único, que teve um único ciclo para ser executado, então teve a menor sobrecarga possível.

Se uma micro-otimização como essa é ou não uma otimização ou uma anti-otimização depende da arquitetura específica que você está usando, então normalmente é uma má idéia adquirir o hábito de usar micro-otimizações específicas da arquitetura, caso contrário você pode instintivamente use um quando for inadequado fazê-lo, e parece que é exatamente isso que o livro que você está lendo está defendendo.

Estou lendo um livro onde o autor diz que if( a < 901 ) é mais rápido que if( a <= 900 ) .

Não exatamente como neste exemplo simples, mas há pequenas alterações de desempenho no código complexo de loop. Suponho que isso tenha que fazer alguma coisa com código de máquina gerado, caso isso seja verdade.


Assumindo que estamos falando de tipos inteiros internos, não há maneira possível de um ser mais rápido que o outro. Eles são obviamente semanticamente idênticos. Ambos pedem ao compilador para fazer exatamente a mesma coisa. Apenas um compilador terrivelmente corrompido geraria um código inferior para um desses.

Se houver alguma plataforma em que < seja mais rápido que <= para tipos inteiros simples, o compilador deve sempre converter <= para < para constantes. Qualquer compilador que não seria apenas um compilador ruim (para essa plataforma).


Eu vejo que nem é mais rápido. O compilador gera o mesmo código de máquina em cada condição com um valor diferente.

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

Meu exemplo é do GCC na plataforma x86_64 no Linux.

Os redatores de compiladores são pessoas muito inteligentes, e eles pensam nessas coisas e em muitas outras que a maioria de nós aceita como certas.

Notei que, se não é uma constante, então o mesmo código de máquina é gerado em ambos os casos.

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3

Historicamente (estamos falando dos anos 80 e início dos anos 90), havia algumas arquiteturas em que isso era verdade. O problema da raiz é que a comparação de inteiros é inerentemente implementada via subtrações de inteiros. Isso dá origem aos seguintes casos.

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

Agora, quando A < B a subtração tem que emprestar um bit alto para a subtração ser correta, assim como você carrega e pede emprestado ao adicionar e subtrair manualmente. Esse bit "emprestado" era geralmente chamado de carry e seria testável por uma instrução de ramificação. Um segundo bit chamado bit zero seria definido se a subtração fosse identicamente zero, o que implicava igualdade.

Geralmente, havia pelo menos duas instruções de ramificação condicional, uma para ramificar no carry e outra no bit zero.

Agora, para chegar ao cerne da questão, vamos expandir a tabela anterior para incluir os resultados carry e zero bit.

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

Então, implementar uma ramificação para A < B pode ser feito em uma instrução, porque o bit carry é claro apenas neste caso, isto é,

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

Mas, se quisermos fazer uma comparação menor do que ou igual, precisamos fazer uma verificação adicional do sinalizador zero para capturar o caso da igualdade.

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

Portanto, em algumas máquinas, usar uma comparação "menor que" pode salvar uma instrução da máquina . Isso foi relevante na era da velocidade do processador sub-megahertz e das taxas de velocidade de CPU para memória de 1: 1, mas hoje é quase totalmente irrelevante.


Não, não será mais rápido na maioria das arquiteturas. Você não especificou, mas no x86, todas as comparações integrais serão tipicamente implementadas em duas instruções de máquina:

  • Uma instrução test ou cmp , que define EFLAGS
  • E uma Jcc (salto) , dependendo do tipo de comparação (e layout de código):
    • jne - Salta se não igual -> ZF = 0
    • jz - Salta se zero (igual) -> ZF = 1
    • jg - Salto se maior -> ZF = 0 and SF = OF
    • (etc ...)

Exemplo (Editado por brevidade) Compilado com $ gcc -m32 -S -masm=intel test.c

    if (a < b) {
        // Do something 1
    }

Compila para:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

E

    if (a <= b) {
        // Do something 2
    }

Compila para:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

Portanto, a única diferença entre os dois é uma instrução jg versus jge . Os dois terão a mesma quantidade de tempo.

Gostaria de abordar o comentário de que nada indica que as diferentes instruções de salto levam a mesma quantidade de tempo. Este é um pouco difícil de responder, mas aqui está o que eu posso dar: Na Intel Instruction Set Reference , eles são agrupados em uma instrução comum, Jcc (Jump se a condição for satisfeita). O mesmo agrupamento é feito em conjunto no Manual de Referência de Otimização , no Apêndice C. Latência e Throughput.

Latência - O número de ciclos de clock que são necessários para o núcleo de execução concluir a execução de todos os μops que formam uma instrução.

Taxa de transferência - O número de ciclos de clock necessários para aguardar antes que as portas de problema estejam livres para aceitar a mesma instrução novamente. Para muitas instruções, o rendimento de uma instrução pode ser significativamente menor que sua latência

Os valores para o Jcc são:

      Latency   Throughput
Jcc     N/A        0.5

com a seguinte nota de rodapé no Jcc :

7) A seleção de instruções de saltos condicionais deve ser baseada na recomendação da seção 3.4.1, “Otimização de previsão de ramificação”, para melhorar a previsibilidade das ramificações. Quando os ramos são previstos com sucesso, a latência do jcc é efetivamente zero.

Portanto, nada nos documentos da Intel sempre trata uma instrução Jcc forma diferente das outras.

Se pensarmos no circuito real usado para implementar as instruções, pode-se supor que haveria portas AND / OR simples nos diferentes bits no EFLAGS , para determinar se as condições são atendidas. Não há, então, nenhuma razão para que uma instrução testando dois bits deva demorar mais ou menos tempo do que um teste apenas um (Ignorando o atraso de propagação do gate, que é muito menor que o período de clock).

Editar: ponto flutuante

Isso vale também para o ponto flutuante x87: (praticamente o mesmo código acima, mas com o double vez do int .)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret

Na verdade, eles terão exatamente a mesma velocidade, porque no nível de montagem, ambos pegam uma linha. Tal como:

  • jl ax,dx (salta se o AX for menor que DX)
  • jle ax,dx (salta se AX for menor ou igual a DX)

Então não, nem é mais rápido. Mas se você quiser ser realmente técnico, acho que, se você verificá-lo em um nível de corrente de elétrons, seria um pouco mais rápido, mas não em qualquer lugar perto de uma velocidade que você notaria.


Para código de ponto flutuante, a comparação <= pode de fato ser mais lenta (por uma instrução) mesmo em arquiteturas modernas. Aqui está a primeira função:

int compare_strict(double a, double b) { return a < b; }

No PowerPC, primeiro ele executa uma comparação de ponto flutuante (que atualiza cr , o registrador de condição), move o registro de condição para um GPR, desloca o bit "comparado a menos do que" e retorna. Leva quatro instruções.

Agora, considere esta função:

int compare_loose(double a, double b) { return a <= b; }

Isso requer o mesmo trabalho que compare_strict acima, mas agora há dois bits de interesse: "era menor que" e "era igual a". Isso requer uma instrução extra ( cror - bit do registrador de condição de cror ) para combinar esses dois bits em um. Então compare_loose requer cinco instruções, enquanto compare_strict requer quatro.

Você pode pensar que o compilador poderia otimizar a segunda função da seguinte forma:

int compare_loose(double a, double b) { return ! (a > b); }

No entanto isso incorretamente manipulará NaNs. NaN1 <= NaN2 e NaN1 > NaN2 precisam avaliar ambos para falso.


Talvez o autor desse livro sem nome tenha lido que a > 0 corre mais rápido que a >= 1 e acha que isso é verdade universalmente.

Mas é porque um 0 está envolvido (porque o CMP pode, dependendo da arquitetura, substituído por exemplo com OR ) e não por causa do < .


Você poderia dizer que a linha está correta na maioria das linguagens de script, já que o caractere extra resulta em um processamento de código um pouco mais lento. No entanto, como a resposta principal apontou, ela não deve ter efeito em C ++, e qualquer coisa que esteja sendo feita com uma linguagem de script provavelmente não está tão preocupada com a otimização.





relational-operators