<É mais rápido que <=?

1574

É 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 algo a ver com o código de máquina gerado, caso isso seja verdade.

snoopy
fonte
153
Não vejo razão para que essa pergunta deva ser encerrada (e especialmente não excluída, como os votos estão mostrando no momento), dada sua importância histórica, a qualidade da resposta e o fato de que as outras questões principais de desempenho permanecem abertas. No máximo, deve estar bloqueado. Além disso, mesmo que a pergunta em si seja desinformada / ingênua, o fato de ela aparecer em um livro significa que a desinformação original existe em fontes "confiáveis" em algum lugar, e essa pergunta é construtiva, pois ajuda a esclarecer isso.
Jason C #
32
Você nunca nos disse a que livro se refere.
Jonathon Reinhart
160
Digitar <é duas vezes mais rápido que digitar <=.
Deqing
6
Era verdade em 8086.
Joshua
7
O número de votos positivos mostra claramente que existem centenas de pessoas que otimizam demais.
M93a

Respostas:

1704

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 normalmente implementadas em duas instruções da máquina:

  • A testou cmpinstrução, que defineEFLAGS
  • E uma Jccinstrução (jump) , dependendo do tipo de comparação (e layout do código):
    • jne - Salte se não for igual -> ZF = 0
    • jz - Salte se zero (igual) -> ZF = 1
    • jg - Salte 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 é jguma jgeinstrução versus uma instrução. Os dois levarã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 complicado de responder, mas eis o que posso dar: Na Referência do conjunto de instruções da Intel , todos estão agrupados sob uma instrução comum Jcc(Salte se a condição for atendida). O mesmo agrupamento é feito em conjunto no Manual de Referência da Otimização , no Apêndice C. Latência e Taxa de Transferência.

Latência - O número de ciclos de clock 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 emissão 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 Jccsão:

      Latency   Throughput
Jcc     N/A        0.5

com a seguinte nota de rodapé Jcc:

7) A seleção das instruções de salto condicional 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 as ramificações são previstas com sucesso, a latência de jccé efetivamente zero.

Portanto, nada nos documentos da Intel trata uma Jccinstrução de maneira diferente das outras.

Se pensarmos nos circuitos reais usados ​​para implementar as instruções, podemos assumir que haveria portas AND / OR simples nos diferentes bits EFLAGS, para determinar se as condições são atendidas. Portanto, não há razão para que uma instrução que teste dois bits deva levar mais ou menos tempo do que uma que teste apenas um (Ignorando o atraso de propagação da porta, que é muito menor que o período do relógio).


Editar: Ponto flutuante

Isso também vale para o ponto flutuante x87: (Praticamente o mesmo código acima, mas com em doublevez de 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
Jonathon Reinhart
fonte
239
@Dyppl, na verdade, jge jnlesão as mesmas instruções 7F:-)
Jonathon Reinhart
17
Sem mencionar que o otimizador pode modificar o código se de fato uma opção for mais rápida que a outra.
Elazar Leibovich
3
só porque algo resulta na mesma quantidade de instruções não significa necessariamente que a soma do tempo total de execução de todas essas instruções será a mesma. Na verdade, mais instruções podem ser executadas mais rapidamente. As instruções por ciclo não são um número fixo, variam de acordo com as instruções.
jontejj
22
@jontejj Estou muito ciente disso. Você leu minha resposta? Não afirmei nada sobre o mesmo número de instruções, afirmei que elas são compiladas para essencialmente as mesmas instruções , exceto que uma instrução de salto está olhando para um sinalizador e a outra instrução de salto está olhando para dois sinalizadores. Acredito ter dado evidências mais que suficientes para mostrar que elas são semanticamente idênticas.
Jonathon Reinhart
2
@jontejj Você faz uma observação muito boa. Para obter a maior visibilidade possível dessa resposta, eu provavelmente deveria fazer uma limpeza. Obrigado pelo feedback.
Jonathon Reinhart
593

Historicamente (estamos falando dos anos 80 e início dos 90), havia algumas arquiteturas nas quais isso era verdade. O problema principal é que a comparação de números inteiros é inerentemente implementada por meio de subtrações de números 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 < Ba subtração precisar emprestar um valor alto para que a subtração esteja correta, assim como você carrega e empresta ao adicionar e subtrair manualmente. Esse bit "emprestado" era geralmente chamado de bit de transporte e seria testável por uma instrução de ramificação. Um segundo bit chamado zero seria definido se a subtração fosse idêntica a zero, o que implicava igualdade.

Geralmente, havia pelo menos duas instruções de ramificação condicional, uma para ramificar no bit de transporte 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

Portanto, implementar uma ramificação para A < Bpode ser feito em uma instrução, porque o bit de transporte é claro apenas neste caso, ou seja,

;; 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 ou igual, precisamos fazer uma verificação adicional do sinalizador zero para entender 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, o uso de 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 na proporção de 1: 1 da CPU para a memória, mas hoje é quase totalmente irrelevante hoje.

Lucas
fonte
10
Além disso, arquiteturas como x86 implementam instruções como jge, que testam os sinalizadores zero e sinal / transporte.
greyfade
3
Mesmo se for verdade para uma determinada arquitetura. Quais são as chances que nenhum dos escritores do compilador já notou e adicionou uma otimização para substituir o mais lento pelo mais rápido?
Jon Hanna
8
Isso é verdade no 8080. Ele tem instruções para pular em zero e pular em menos, mas nenhuma que possa testar as duas simultaneamente.
4
Este também é o caso da família de processadores 6502 e 65816, que também se estende ao Motorola 68HC11 / 12.
27512 Lucas
31
Mesmo no 8080 um <=teste pode ser implementada em uma instrução com trocando os operandos e testando para not <(a equivalente >=) Esta é a desejada <=com operandos trocados: cmp B,A; bcs addr. Esse é o raciocínio este teste foi omitido pela Intel, que considerou redundante e você não podia pagar instruções redundantes nesses momentos :-)
Gunther Piez
92

Supondo que estamos falando de tipos inteiros internos, não há como um ser mais rápido que o outro. Eles são obviamente semanticamente idênticos. Ambos pedem que o compilador faça exatamente a mesma coisa. Somente um compilador horrivelmente quebrado geraria código inferior para um deles.

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

David Schwartz
fonte
6
+1 eu concordo. Nem <nem <=tem velocidade até que o compilador decide qual a velocidade que eles têm. Essa é uma otimização muito simples para os compiladores quando você considera que eles geralmente já executam otimização de código morto, otimização de chamada de cauda, ​​içamento de loop (e desenrolamento, às vezes), paralelização automática de vários loops, etc. Por que perder tempo pensando em otimizações prematuras ? Obter um protótipo em execução, perfil para determinar onde as otimizações mais significativos mentir, executar as otimizações em ordem de importância e perfil novamente ao longo do caminho para medir o progresso ...
autista
Ainda existem alguns casos extremos em que uma comparação com um valor constante pode ser mais lenta em <=, por exemplo, quando a transformação de (a < C)para (a <= C-1)(para alguma constante C) faz Ccom que seja mais difícil codificar no conjunto de instruções. Por exemplo, um conjunto de instruções pode ser capaz de representar constantes assinadas de -127 a 128 em uma forma compacta nas comparações, mas as constantes fora desse intervalo precisam ser carregadas usando uma codificação mais longa e mais lenta ou outra instrução inteiramente. Portanto, uma comparação como essa (a < -127)pode não ter uma transformação direta.
BeeOnRope 16/06
@BeeOnRope O problema não era se a execução de operações diferentes devido à presença de constantes diferentes poderia afetar o desempenho, mas se a expressão da mesma operação usando constantes diferentes poderia afetar o desempenho. Portanto, não estamos comparando a > 127a a > 128porque você não tem escolha lá, você use o que você precisa. Estamos comparando a > 127a a >= 128, que não pode exigir codificação ou instruções diferentes, porque elas têm a mesma tabela de verdade. Qualquer codificação de um é igualmente uma codificação do outro.
David Schwartz
Eu estava respondendo de uma maneira geral para a sua afirmação de que "Se houve alguma plataforma onde [<= foi mais lento] o compilador deve sempre converter <=para <para constantes". Até onde eu sei, essa transformação envolve mudar a constante. Por exemplo, a <= 42é compilado como a < 43porque <é mais rápido. Em alguns casos extremos, essa transformação não seria proveitosa porque a nova constante pode exigir instruções mais ou mais lentas. Claro a > 127e a >= 128são equivalentes e um compilador deve codificar as duas formas na (mesma) maneira mais rápida, mas isso não é inconsistente com o que eu disse.
BeeOnRope 16/06
67

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 if é do GCC na plataforma x86_64 no Linux.

Os escritores de compiladores são pessoas bastante inteligentes, e pensam nessas coisas e em muitas outras que a maioria de nós considera um dado adquirido.

Percebi que, se não for uma constante, o mesmo código de máquina será gerado nos dois casos.

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

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3
Adrian Cornish
fonte
9
Observe que isso é específico para x86.
Michael Petrotta
10
Eu acho que você deve usá-la if(a <=900)para demonstrar que ele gera exatamente a mesma asm :)
Lipis
2
@AdrianCornish Desculpe .. Eu editei .. é mais ou menos o mesmo .. mas se você alterar o segundo se for <= 900, o código ASM será exatamente o mesmo :) É praticamente o mesmo agora .. mas você sabe .. para o TOC :)
Lipis
3
@Boann Isso pode ser reduzido a se (verdadeiro) e eliminado completamente.
Qsario 27/08
5
Ninguém apontou que essa otimização se aplica apenas a comparações constantes . Posso garantir que isso não será feito para comparar duas variáveis.
Jonathon Reinhart
51

Para código de ponto flutuante, a comparação <= pode realmente 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 isso faz uma comparação de ponto flutuante (que atualiza cr , o registro de condições), depois move o registro de condições para um GPR, muda o bit "comparado menos que" para o local e depois retorna. São necessárias quatro instruções.

Agora considere esta função:

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

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

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

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

No entanto, isso irá lidar incorretamente com NaNs. NaN1 <= NaN2e NaN1 > NaN2precisa avaliar como falso.

ridiculous_fish
fonte
Felizmente, ele não funciona assim em x86 (x87). fucomipdefine ZF e CF.
Jonathon Reinhart
3
@ JonathonReinhart: Acho que você está entendendo mal o que o PowerPC está fazendo - o registro de condições cr é equivalente a sinalizadores como ZFe CFno x86. (Embora o CR seja mais flexível.) O que o pôster está falando é mover o resultado para um GPR: que requer duas instruções no PowerPC, mas o x86 possui uma instrução de movimentação condicional.
Dietrich Epp
@DietrichEpp O que pretendi adicionar após minha declaração foi: O que você pode pular imediatamente com base no valor do EFLAGS. Desculpe por não ser claro.
Jonathon Reinhart
1
@ JonathonReinhart: Sim, e você também pode pular imediatamente com base no valor do CR. A resposta não está falando sobre pular, e é daí que vêm as instruções extras.
Dietrich Epp
34

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

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

glglgl
fonte
1
Claro, em uma compilação de "depuração", mas que seria necessário um compilador ruim para (a >= 1)executar mais lento do que (a > 0), uma vez que o primeiro pode ser trivialmente transformou a este último pelo otimizador ..
BeeOnRope
2
@BeeOnRope Às vezes fico surpreso com as coisas complicadas que um otimizador pode otimizar e com as coisas fáceis que deixa de fazê-lo.
glglgl
1
De fato, e sempre vale a pena verificar a saída asm para as poucas funções em que isso importaria. Dito isto, a transformação acima é muito básica e foi realizada mesmo em compiladores simples por décadas.
BeeOnRope 16/06
32

No mínimo, se isso fosse verdade, um compilador poderia otimizar trivialmente a <= b para! (A> b) e, mesmo que a comparação em si fosse realmente mais lenta, com todos, exceto o compilador mais ingênuo, você não notaria diferença .

Eliot Ball
fonte
Por que! (A> b) é a versão otimizada de a <= b. Não é! (A> b) 2 operação em uma?
Abhishek Singh
6
@AbhishekSingh NOTé feito apenas por outra instrução ( jevs. jne)
Pavel Gatnar
15

Eles têm a mesma velocidade. Talvez em alguma arquitetura especial o que ele disse esteja certo, mas na família x86 pelo menos eu sei que eles são iguais. Porque, para fazer isso, a CPU fará uma subtração (a - b) e depois verificará os sinalizadores do registro do sinalizador. Dois bits desse registrador são chamados ZF (sinalizador zero) e SF (sinalizador), e são feitos em um ciclo, porque o fazem com uma operação de máscara.

Masoud
fonte
14

Isso seria altamente dependente da arquitetura subjacente na qual o C é compilado. Alguns processadores e arquiteturas podem ter instruções explícitas para igual ou menor que e igual a, que são executadas em diferentes números de ciclos.

Isso seria bastante incomum, pois o compilador poderia contorná-lo, tornando-o irrelevante.

Telgin
fonte
1
Se havia uma diferença nos cyles. 1) não seria detectável. 2) Qualquer compilador que se preze já estaria fazendo a transformação da forma lenta para a forma mais rápida sem alterar o significado do código. Portanto, a instrução resultante plantada seria idêntica.
Martin York
Concordado completamente, seria uma diferença bastante trivial e boba em qualquer caso. Certamente nada a mencionar em um livro que deve ser independente de plataforma.
Telgin 28/08/12
@lttlrck: Entendi. Levou um tempo (bobo). Não, eles não são detectáveis, porque há muitas outras coisas acontecendo que tornam sua medição impossível. Paradas do processador / falhas de cache / sinais / troca de processos. Assim, em uma situação normal do SO, as coisas no nível de ciclo único não podem ser fisicamente mensuráveis. Se você pode eliminar toda essa interferência de suas medições (executá-lo em um chip com memória interna e sem sistema operacional), ainda tem a granularidade de seus temporizadores para se preocupar, mas teoricamente, se você executá-lo por tempo suficiente, poderá ver alguma coisa.
Martin York
12

TL; DRResposta

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

Resposta completa

Outras respostas se concentraram em arquitetura x86 , e eu não conheço bem a arquitetura ARM (que seu assembler de exemplo parece) o suficiente para comentar especificamente sobre o código gerado, mas este é um exemplo de micro-otimização 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-otimização é um exemplo de culto à carga programação de , e não das melhores práticas de engenharia de software.

Provavelmente existem algumas arquiteturas em que isso é uma otimização, mas eu sei de pelo menos uma arquitetura em que o oposto pode ser verdadeiro. A venerável arquitetura do Transputer tinha apenas instruções de código de máquina iguais ou maiores que ou iguais a , portanto todas as comparações tiveram 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 maneira que, na prática, nenhuma comparação tivesse vantagem sobre outras. No pior caso, pode ser necessário adicionar uma instrução reversa (REV) para trocar os dois itens principais na pilha de operandos . Essa era uma instrução de byte único que demorou um único ciclo para ser executada, assim teve a menor sobrecarga possível.

Se uma micro-otimização como essa é uma otimização ou uma anti-otimização depende da arquitetura específica que você está usando, por isso é geralmente 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 inapropriado e parece que é exatamente isso que o livro que você está lendo está defendendo.

Mark Booth
fonte
6

Você não deve perceber a diferença, mesmo que exista. Além disso, na prática, você terá que fazer um adicional a + 1ou a - 1manter a condição, a menos que use algumas constantes mágicas, o que é uma prática muito ruim em todos os aspectos.

shinkou
fonte
1
Qual é a má prática? Incrementando ou diminuindo um contador? Como você armazena a notação de índice então?
precisa saber é o seguinte
5
Ele quer dizer se você está fazendo uma comparação de 2 tipos de variáveis. Claro que é trivial se você estiver definindo o valor para um loop ou algo assim. Mas se você tem x <= y, e y é desconhecido, seria mais lento "otimizá-lo" para x <y + 1
JustinDanielson
@JustinDanielson concordou. Sem mencionar feio, confundindo, etc.
Jonathon Reinhart
4

Você poderia dizer que a linha está correta na maioria das linguagens de script, pois 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á preocupada com a otimização.

Ecksters
fonte
Eu discordo um pouco. Em programação competitiva, as linguagens de script geralmente oferecem a solução mais rápida para um problema, mas técnicas corretas (leia-se: otimização) devem ser aplicadas para obter uma solução correta.
Tyler Crompton
3

Quando eu escrevi essa resposta, eu só estava olhando para a pergunta do título sobre <vs. <= em geral, não é o exemplo específico de uma constante a < 901vs. a <= 900. Muitos compiladores sempre diminuem a magnitude das constantes convertendo entre <e <=, por exemplo, porque o operando imediato x86 possui uma codificação de 1 byte mais curta para -128..127.

Para o ARM e especialmente o AArch64, a capacidade de codificação imediata depende da capacidade de rotacionar um campo estreito para qualquer posição em uma palavra. Então, cmp w0, #0x00f000seria codificável, enquanto cmp w0, #0x00effffpode não ser. Portanto, a regra de redução do tamanho para comparação versus uma constante em tempo de compilação nem sempre se aplica ao AArch64.


<vs. <= em geral, inclusive para condições variáveis ​​de tempo de execução

Na linguagem assembly na maioria das máquinas, uma comparação para <=tem o mesmo custo que uma comparação para <. Isso se aplica se você estiver ramificando-o, fazendo booleano para criar um número inteiro 0/1 ou usando-o como predicado para uma operação de seleção sem ramificação (como x86 CMOV). As outras respostas abordaram apenas essa parte da pergunta.

Mas esta pergunta é sobre os operadores C ++, a entrada para o otimizador. Normalmente, ambos são igualmente eficientes; o conselho do livro parece totalmente falso porque os compiladores sempre podem transformar a comparação que eles implementam em asm. Mas há pelo menos uma exceção em que o uso <=pode criar acidentalmente algo que o compilador não pode otimizar.

Como condição de loop, há casos em que <=é qualitativamente diferente de <, quando impede o compilador de provar que um loop não é infinito. Isso pode fazer uma grande diferença, desativando a vetorização automática.

O estouro não assinado é bem definido como base 2, ao contrário do UB (estouro assinado). Os contadores de loop assinados geralmente estão seguros disso com os compiladores que otimizam com base no UB de overflow com sinal não acontecendo: ++i <= sizesempre acabará sempre se tornando falso. ( O que todo programador C deve saber sobre comportamento indefinido )

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

Os compiladores só podem otimizar de maneira a preservar o comportamento (definido e legalmente observável) da fonte C ++ para todos os possíveis valores de entrada , exceto aqueles que levam a um comportamento indefinido.

(Um simples i <= sizetambém criaria o problema, mas pensei que calcular um limite superior era um exemplo mais realista de introduzir acidentalmente a possibilidade de um loop infinito para uma entrada que você não se importa, mas que o compilador deve considerar.)

Nesse caso, size=0leva a upper_bound=UINT_MAXe i <= UINT_MAXé sempre verdade. Portanto, esse loop é infinito size=0, e o compilador deve respeitar isso, mesmo que você como programador provavelmente nunca pretenda passar size = 0. Se o compilador puder incorporar essa função em um chamador, onde poderá provar que size = 0 é impossível, então ótimo, ele poderá otimizar como poderia i < size.

Asm like if(!size) skip the loop; do{...}while(--size);é uma maneira normalmente eficiente de otimizar um for( i<size )loop, se o valor real de inão for necessário dentro do loop ( por que os loops são sempre compilados no estilo "do ... while" (salto de cauda)? ).

Mas isso não pode ser infinito: se inserido com size==0, obtemos 2 ^ n iterações. (A iteração sobre todos os números inteiros não assinados em um loop C torna possível expressar um loop sobre todos os números inteiros não assinados, incluindo zero, mas não é fácil sem um sinalizador carry do jeito que está no asm.)

Com a possibilidade de envolver o contador de loop, os compiladores modernos simplesmente "desistem" e não otimizam de maneira tão agressiva.

Exemplo: soma dos números inteiros de 1 a n

O uso de i <= nderrotas não assinadas derrota o reconhecimento de expressões idiomáticas do clang que otimiza sum(1 .. n)loops com um formulário fechado com base na n * (n+1) / 2fórmula de Gauss .

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

x86-64 asm de clang7.0 e gcc8.2 no Godbolt compiler explorer

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

Mas para a versão ingênua, obtemos apenas um loop estúpido do clang.

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}
# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

O GCC não usa um formulário fechado de qualquer maneira, portanto a escolha da condição do loop não o prejudica ; vetoriza automaticamente com adição de número inteiro SIMD, executando 4 ivalores em paralelo nos elementos de um registro XMM.

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.

Ele também possui um loop escalar simples que eu acho que ele usa para muito pequeno ne / ou para o caso de loop infinito.

BTW, esses dois loops desperdiçam uma instrução (e um uop nas CPUs da família Sandybridge) na sobrecarga do loop. sub eax,1/ em jnzvez de add eax,1/ cmp / jcc seria mais eficiente. 1 uop em vez de 2 (após a fusão macro de sub / jcc ou cmp / jcc). O código após os dois loops grava EAX incondicionalmente, portanto não está usando o valor final do contador de loops.

Peter Cordes
fonte
Belo exemplo artificial. E o seu outro comentário sobre um efeito potencial na execução fora de ordem devido ao uso do EFLAGS? É puramente teórico ou pode realmente acontecer que um JB leve a um pipeline melhor do que um JBE?
Rustyx
@rustyx: comentei isso em algum lugar sob outra resposta? Os compiladores não vão emitir código que causa paradas de sinalização parcial, e certamente não para um C <ou <=. Mas com certeza, test ecx,ecx/ bt eax, 3/ jbeirá pular se ZF estiver definido (ecx == 0) ou se CF estiver definido (bit 3 de EAX == 1), causando uma parada parcial de sinalizador na maioria das CPUs, porque os sinalizadores que lê não são todos vem da última instrução para escrever qualquer sinalizador. Na família Sandybridge, na verdade, ele não pára, só precisa inserir um uop em fusão. cmp/ testescrevo todos os sinalizadores, mas btdeixa o ZF inalterado. felixcloutier.com/x86/bt
Peter Cordes
2

Somente se as pessoas que criaram os computadores forem ruins com lógica booleana. O que eles não deveriam ser.

Toda comparação ( >= <= > <) pode ser feita na mesma velocidade.

O que toda comparação é, é apenas uma subtração (a diferença) e ver se é positivo / negativo.
(Se msbestiver definido, o número é negativo)

Como verificar a >= b? Sub a-b >= 0Verifique se a-bé positivo.
Como verificar a <= b? Sub 0 <= b-aVerifique se b-aé positivo.
Como verificar a < b? Sub a-b < 0Verifique se a-bé negativo.
Como verificar a > b? Sub 0 > b-aVerifique se b-aé negativo.

Simplificando, o computador pode fazer isso por baixo do capô para a operação fornecida:

a >= b== msb(a-b)==0
a <= b== msb(b-a)==0
a > b== msb(b-a)==1
a < b==msb(a-b)==1

e, claro, o computador não seria realmente precisa fazer o ==0ou ==1qualquer um.
para o ==0que poderia apenas inverter o msbdo circuito.

Enfim, eles certamente não teriam feito a >= bser calculado como a>b || a==blol

Poça
fonte