É uma comparação 1 10 mais barata que 1 1000000?

64

Eu usei apenas ~ 1 bilhão como a contagem de z-index em CSS e estava pensando nas comparações que devem ser feitas. Existe uma diferença no desempenho no nível da ALU nas comparações entre números muito grandes e muito pequenos?

Por exemplo, um desses dois trechos seria mais caro que o outro?

snippet 1

for (int i = 0; i < 10000000; i++){
    if (i < 10000000000000) {
        //do nothing
    }
}

snippet 2

for (int i = 0; i < 10000000; i++){
    if (i < 1000) {
        //do nothing
    }
}
    
por Viziionary 02.02.2015 / 15:52
fonte

7 respostas

81

Cada processador em que trabalhei faz comparação subtraindo um dos operandos do outro, descartando o resultado e deixando os sinalizadores do processador (zero, negativo, etc.) sozinhos. Como a subtração é feita como uma única operação, o conteúdo dos operandos não importa.

A melhor maneira de responder à pergunta com certeza é compilar seu código em assembly e consultar a documentação do processador de destino para as instruções geradas. Para os atuais processadores da Intel, isso seria o Manual do Desenvolvedor de Software das Arquiteturas Intel 64 e IA-32 .

A descrição da instrução CMP ("compare") está no volume 2A, página 3-126 ou na página 618 do PDF e descreve sua operação como:

temp ← SRC1 − SignExtend(SRC2);
ModifyStatusFlags; (* Modify status flags in the same manner as the SUB instruction*)

Isso significa que o segundo operando é estendido, se necessário, subtraído do primeiro operando e o resultado colocado em uma área temporária no processador. Em seguida, os sinalizadores de status são definidos da mesma maneira que seriam para a instrução SUB ("subtract") (página 1492 do PDF).

Não há menção na documentação de CMP ou SUB de que os valores dos operandos têm alguma influência sobre a latência, portanto, qualquer valor usado é seguro.

    
por 02.02.2015 / 17:20
fonte
24

Is there a difference in performance on the ALU level in comparisons between very large numbers vs very small ones?

É muito improvável, a menos que passar de um número pequeno para um grande número altere seu tipo numérico, digamos, de um int para um long . Mesmo assim, a diferença pode não ser significativa. É mais provável que você veja a diferença se a sua linguagem de programação alterna silenciosamente para aritmética de precisão arbitrária por baixo das capas. / p>

No entanto, seu compilador em particular pode estar executando algumas otimizações inteligentes das quais você não está ciente. A maneira como você descobre é medir. Executar um profiler no seu código; Veja quais comparações levam mais tempo. Ou simplesmente inicie e pare um cronômetro.

    
por 02.02.2015 / 16:47
fonte
18

Muitos processadores possuem instruções "pequenas" que podem realizar operações aritméticas, incluindo comparações, em certos operandos especificados imediatamente. Operandos diferentes desses valores especiais devem usar um formato de instrução maior ou, em alguns casos, usar uma instrução "carregar valor da memória". No conjunto de instruções ARM Cortex-M3, por exemplo, existem pelo menos cinco maneiras pelas quais um valor pode ser comparado a uma constante:

    cmp r0,#1      ; One-word instruction, limited to values 0-255

    cmp r0,#1000   ; Two-word instruction, limited to values 0-255 times a power of 2

    cmn r0,#1000   ; Equivalent to comparing value with -1000
                   ; Two-word instruction, limited to values 0-255 times a power of 2

    mov r1,#30000  ; Two words; can handle any value 0-65535
    cmp r0,r1      ; Could use cmn to compare to values -1 to -65535

    ldr r1,[constant1000000] ; One or two words, based upon how nearby the constant is
    cmp r0,r1
    ...

constant1000000:
    dd  1000000

A primeira forma é a menor; a segunda e terceira forma podem ou não ser executadas tão rapidamente, dependendo da velocidade da memória da qual o código é buscado. A quarta forma de forma quase certamente será mais lenta que as três primeiras e a quinta forma ainda mais lenta, mas a última pode ser usada com qualquer valor de 32 bits.

Nos processadores x86 mais antigos, as instruções de comparação de formato curto seriam executadas mais rapidamente que as de formato longo, mas muitos processadores mais recentes converterão os formulários longos e curtos na mesma representação quando forem buscados pela primeira vez e armazenarão essa representação uniforme em o cache. Assim, enquanto os controladores embarcados (como aqueles encontrados em muitas plataformas móveis) terão uma diferença de velocidade, muitos computadores baseados em x86 não terão.

Note também que em muitos casos onde uma constante é usada strongmente dentro de um loop, um compilador só precisará carregar a constante em um registrador uma vez - antes do loop iniciar - renderizando as diferenças de temporização discutidas. Por outro lado, existem algumas situações, mesmo em pequenos loops, onde isso nem sempre acontece; Se um loop é pequeno, mas muito executado, ocasionalmente pode haver um grande desempenho entre comparações envolvendo valores imediatos curtos e aqueles envolvendo os mais longos.

    
por 02.02.2015 / 19:22
fonte
5

A resposta curta para esta pergunta é, no , não há diferença de tempo para comparar dois números com base na magnitude desses números, supondo que estejam armazenados no mesmo tipo de dados (por exemplo, 32- bits ints ou ambos os 64-bit longs.)

Além disso, até o tamanho da palavra da ALU , é incrivelmente improvável que comparar dois inteiros entre si levar mais de 1 ciclo de clock, pois esta é uma operação trivial equivalente a uma subtração. Eu acho que toda arquitetura que eu já lidei tinha uma comparação inteira de ciclo único.

Os únicos casos em que posso pensar que encontrei onde uma comparação de dois números não era uma operação de ciclo único são os seguintes:

  • Instruções onde há realmente uma latência de memória na busca de operandos, mas isso não tem nada a ver com o funcionamento da comparação (e geralmente não é possível em arquiteturas RISC, embora normalmente seja possível em projetos CISC, como x86 / x64 .)
  • As comparações de ponto flutuante podem ser multi-ciclo, dependendo da arquitetura.
  • Os números em questão não se encaixam no tamanho da palavra da ULA e, portanto, a comparação deve ser dividida em várias instruções.
por 02.02.2015 / 19:01
fonte
4

@Responda RobertHarvey é boa; considere esta resposta um complemento ao seu.

Você também deve considerar Predição de ramos :

In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures such as x86.

Basicamente, no seu exemplo, se a instrução if dentro do loop sempre retorna a mesma resposta, o sistema pode otimizá-lo adivinhando corretamente o caminho que ele irá ramificar. No seu exemplo, como a instrução if no primeiro caso sempre retorna o mesmo resultado, ela será executada um pouco mais rapidamente que o segundo caso.

Excelente pergunta do Stack Overflow sobre o assunto

    
por 02.02.2015 / 17:00
fonte
3

Depende da implementação, mas seria muito, muito improvável .

Admito que não li os detalhes de implementação dos vários mecanismos de navegação, e o CSS não especifica nenhum tipo específico de armazenamento para números. Mas acredito que é seguro assumir que todos os principais navegadores estão usando números de ponto flutuante de precisão dupla de 64 bits ("duplos", para emprestar um termo de C / C ++) para lidar com a maioria de suas necessidades numéricas em CSS. , porque é isso que o JavaScript usa para números e, portanto, usar o mesmo tipo facilita a integração.

Do ponto de vista do computador, todas as duplas carregam a mesma quantidade de dados: 64 bits, seja o valor 1 ou -3.14 ou 1000000 ou 1e100 . A quantidade de tempo necessária para realizar uma operação nesses números não depende do valor real desses números, porque está sempre trabalhando na mesma quantidade de dados. Há uma desvantagem em fazer as coisas dessa maneira, pois as duplas não podem representar com precisão todos os números (ou até mesmo todos os números dentro de sua faixa), mas podem chegar perto o suficiente para a maioria dos assuntos e os tipos de CSS não são numericamente demandando o suficiente para precisar de mais precisão do que isso. Combine isso com os benefícios da compatibilidade direta com o JavaScript, e você tem um caso muito strong para as duplas.

Não é impossível que alguém implemente CSS usando uma codificação de tamanho variável para números. Se alguém usasse uma codificação de tamanho variável, então comparando com números pequenos seria mais barato do que comparar com números grandes, porque números grandes têm mais dados para processar . Esses tipos de codificações podem ser mais precisos do que binários, mas também são muito mais lentos, e para o CSS em particular, os ganhos de precisão provavelmente não são suficientes para valer o impacto no desempenho. Eu ficaria muito surpreso ao saber que qualquer navegador fez as coisas dessa maneira.

Agora, em teoria, existe uma exceção possível a tudo o que eu disse acima: comparar com zero é geralmente mais rápido do que comparar com outros números . Isto não é porque o zero é curto (se esse fosse o motivo, então 1 deveria ser tão rápido, mas não é). É porque o zero deixa você enganar. É o único número onde todos os bits estão desligados, então se você sabe que um dos valores é zero, você não precisa nem olhar para o outro valor como um número: se algum dos bits de então não é igual a zero, e então você só precisa olhar um bit para ver se é maior ou menor que zero.

    
por 04.02.2015 / 03:37
fonte
0

Se esse código fosse interpretado toda vez que fosse executado, haveria uma diferença, pois levaria mais tempo para separar e interpretar 10000000000000 em comparação com 1000 . No entanto, essa é a primeira otimização óbvia dos intérpretes nesse caso: tokenize uma vez e interprete os tokens.

    
por 04.02.2015 / 01:50
fonte