“IF” é caro?

98

Não consigo, por nada, lembrar o que exatamente nosso professor disse naquele dia e espero que você provavelmente saiba.

O módulo é "Estruturas de dados e algoritmos" e ele nos disse algo parecido com:

O ifextrato é o mais caro [algo]. [algo] registra [algo].

Sim, tenho uma memória horrível e realmente sinto muito, mas estou pesquisando no Google há horas e nada aconteceu. Alguma ideia?

pek
fonte
29
Pedir ao seu professor é uma opção?
Michael Myers
7
Por que você não manda um e-mail para seu professor? É improvável que alguém no SO saiba o que seu professor disse, a menos que eles estivessem lá no momento (ou o próprio professor lê o SO).
Bill Karwin
11
E, claro, um link para a resposta ferroviária
bobobobo
As instruções if ou especialmente as expressões "?:" Em linguagens de colchetes influenciadas por C podem ser implementadas por instruções especiais de execução condicional em, por exemplo, processadores x86 e arm. Estas são instruções que executam ou não algumas operações com base em um teste anterior. Usar essas instruções excelentes evita a necessidade de instruções de salto / ramificação / 'goto' condicionais. Uma grande melhoria de desempenho em algumas situações, tornando o fluxo do programa completamente previsível, uma vez que ele simplesmente segue em linha reta, sem (possivelmente imprevisível) saltar para diferentes pontos no código.
Cecil Ward
Um bom compilador pode às vezes precisar de um empurrãozinho na direção certa para usar instruções condicionais em vez de ser burro e usar saltos condicionais, reorganizando o código e possivelmente usando uma aritmética inteligente em uma expressão ou um? : expressão. Não brinque com isso a menos que você realmente conheça sua asm e tenha lido, por exemplo, os guias de otimização da Agner Fog. Os compiladores às vezes acertam, independentemente de se as declarações ou? : expressões são usadas.
Cecil Ward

Respostas:

185

No nível mais baixo (no hardware), sim, se são caros. Para entender o porquê, você precisa entender como funcionam os pipelines .

A instrução atual a ser executada é armazenada em algo tipicamente chamado de ponteiro de instrução (IP) ou contador de programa (PC); esses termos são sinônimos, mas termos diferentes são usados ​​com arquiteturas diferentes. Para a maioria das instruções, o PC da próxima instrução é apenas o PC atual mais o comprimento da instrução atual. Para a maioria das arquiteturas RISC, as instruções têm comprimento constante, de modo que o PC pode ser incrementado em um valor constante. Para arquiteturas CISC, como x86, as instruções podem ter comprimento variável, de modo que a lógica que decodifica a instrução precisa descobrir quanto tempo a instrução atual dura para encontrar a localização da próxima instrução.

Para instruções de desvio , entretanto, a próxima instrução a ser executada não é o próximo local após a instrução atual. Ramificações são gotos - elas dizem ao processador onde está a próxima instrução. Ramificações podem ser condicionais ou incondicionais e o local de destino pode ser fixo ou calculado.

Condicional versus incondicional é fácil de entender - um desvio condicional só é obtido se uma certa condição for mantida (como se um número é igual a outro); se o desvio não for obtido, o controle prossegue para a próxima instrução após o desvio normalmente. Para ramificações incondicionais, a ramificação é sempre tomada. Ramificações condicionais aparecem em ifinstruções e nos testes de controle fore whileloops. Ramificações incondicionais aparecem em loops infinitos, chamadas de função, retornos de função breake continueinstruções, a infame gotoinstrução e muito mais (essas listas estão longe de ser exaustivas).

O alvo da filial é outra questão importante. A maioria das ramificações tem um destino de ramificação fixo - elas vão para um local específico no código que é fixado em tempo de compilação. Isso inclui ifinstruções, loops de todos os tipos, chamadas de função regulares e muito mais. Os ramos calculados calculam o destino do ramo em tempo de execução. Isso inclui switchinstruções (às vezes), retorno de uma função, chamadas de função virtual e chamadas de ponteiro de função.

Então, o que tudo isso significa para o desempenho? Quando o processador vê uma instrução de ramificação aparecer em seu pipeline, ele precisa descobrir como continuar a preencher seu pipeline. Para descobrir quais instruções vêm após a ramificação no fluxo do programa, ele precisa saber duas coisas: (1) se a ramificação será tomada e (2) o destino da ramificação. Descobrir isso é chamado de previsão de ramificação e é um problema desafiador. Se o processador adivinhar corretamente, o programa continua em velocidade total. Se, em vez disso, o processador adivinhar incorretamente , ele apenas gastou algum tempo computando a coisa errada. Agora, ele precisa liberar seu pipeline e recarregá-lo com instruções do caminho de execução correto. Resumindo: um grande sucesso de desempenho.

Portanto, o motivo pelo qual se as declarações são caras é devido a erros de previsão do ramo . Isso está apenas no nível mais baixo. Se você está escrevendo um código de alto nível, não precisa se preocupar com esses detalhes. Você só deve se preocupar com isso se estiver escrevendo um código extremamente crítico para o desempenho em C ou assembly. Se for esse o caso, escrever código sem ramificação pode frequentemente ser superior ao código que ramifica, mesmo se várias instruções adicionais forem necessárias. Existem alguns truques-girando bit que você pode fazer para calcular coisas como abs(), min()e max()sem ramificação.

Adam Rosenfield
fonte
20
Não são apenas erros de previsão do ramo. Ramificações também inibem a reordenação de instruções, no nível do compilador e também, até certo ponto, no nível da CPU (para uma CPU fora de ordem, é claro). Boa resposta detalhada embora.
jalf
5
Se as linguagens de alto nível são traduzidas para as linguagens de baixo nível e você está escrevendo um código muito centrado no desempenho, você ainda não ganha nada escrevendo um código que evita as declarações if? Este conceito não se aplica a linguagens de nível superior?
c ..
18

"Caro" é um termo muito relativo, especialmente em relação a um "if extrato ", pois você também deve levar em conta o custo da doença. Isso pode variar de algumas instruções curtas de CPU até o teste do resultado de uma função que chama um banco de dados remoto.

Eu não me importaria com isso. A menos que você esteja fazendo programação embarcada, você provavelmente não deve se preocupar com o custo de " if". Para a maioria dos programadores é só não vai nunca ser o fator determinante no desempenho do seu aplicativo.

Joel Coehoorn
fonte
1
Definitivamente relativo ... cmp / cond jmp ainda é mais rápido do que um mul em muitos processadores.
Brian Knoblauch
4
Sim, concordo que não devo me preocupar com isso. Não estou tentando otimizar nada aqui. Estou apenas tentando descobrir e aprender. ;)
pek
15

Ramificações, especialmente em microprocessadores de arquitetura RISC, são algumas das instruções mais caras. Isso ocorre porque em muitas arquiteturas, o compilador prevê qual caminho de execução será mais provável e coloca essas instruções em seguida no executável, de forma que já estarão no cache da CPU quando o desvio acontecer. Se o branch for para o outro lado, ele terá que voltar para a memória principal e buscar as novas instruções - isso é bastante caro. Em muitas arquiteturas RISC, todas as instruções são um ciclo, exceto para ramificação (que geralmente é de 2 ciclos). Não estamos falando de um grande custo aqui, então não se preocupe com isso. Além disso, o compilador otimizará melhor do que você em 99% do tempo: ) Uma das coisas realmente impressionantes sobre a arquitetura EPIC (Itanium é um exemplo) é que ela armazena em cache (e começa a processar) instruções de ambos os lados do branch e, em seguida, descarta o conjunto de que não precisa, uma vez que o resultado do branch é conhecido. Isso economiza o acesso extra à memória de uma arquitetura típica no caso de ela se ramificar ao longo do caminho imprevisto.

rmeador
fonte
13

Confira o artigo Melhor desempenho por meio da eliminação de ramificações no desempenho das células. Outro divertido é este post sobre seleções sem ramificações no Blog de Detecção de Colisão em Tempo Real.

Além das excelentes respostas já postadas em resposta a esta pergunta, gostaria de lembrar que, embora as declarações "if" sejam consideradas operações de baixo nível caras, tentando utilizar técnicas de programação sem ramificação em um ambiente de nível superior , como uma linguagem de script ou uma camada de lógica de negócios (independentemente da linguagem), pode ser ridiculamente inadequada.

Na grande maioria das vezes, os programas devem ser escritos para maior clareza primeiro e otimizados para desempenho em segundo lugar. Existem vários domínios de problemas onde o desempenho é fundamental, mas o simples fato é que a maioria dos desenvolvedores não está escrevendo módulos para uso no núcleo de um mecanismo de renderização ou uma simulação de dinâmica de fluidos de alto desempenho que roda por semanas a fio. Quando a principal prioridade é que sua solução "simplesmente funcione", a última coisa em sua mente deve ser se você pode ou não economizar na sobrecarga de uma instrução condicional em seu código.

Parappa
fonte
De fato! Também se pode acrescentar que, ao codificar em uma linguagem que incentiva chamadas (basicamente, qualquer coisa diferente de assembler ou C sem stdlib), a interferência de pipeline de técnicas de programação normais irá superar qualquer dúvida sobre ramificação condicional.
Ross Patterson
10

ifem si não é lento. A lentidão é sempre relativa, aposto pela minha vida que você nunca sentiu a sobrecarga de uma declaração se. Se você for fazer um código de alto desempenho, pode querer evitar ramificações de qualquer maneira. O que torna mais iflento é que o processador está pré-carregando o código depois, ifbaseado em alguma heurística e outros enfeites. Ele também impedirá que os pipelines executem o código diretamente após a ifinstrução de desvio no código de máquina, uma vez que o processador ainda não sabe qual caminho será seguido (em um processador com pipelines, várias instruções são intercaladas e executadas). O código executado pode ter que ser executado ao contrário (se a outra ramificação foi tomada. É chamada branch misprediction), ou deve noopser preenchido nesses locais para que isso não aconteça.

Se ifé mau, então switché mau também, e &&, ||também. Não se preocupe com isso.

Johannes Schaub - litb
fonte
7

No nível mais baixo possível ifconsiste em (depois de calcular todos os pré-requisitos específicos do aplicativo para particular if):

  • alguma instrução de teste
  • pule para algum lugar no código se o teste for bem-sucedido, prossiga caso contrário.

Custos associados a isso:

  • uma comparação de baixo nível - geralmente 1 operação de cpu, super barato
  • salto potencial - o que pode ser caro

Reveja porque os saltos são caros:

  • você pode pular para um código arbitrário que mora em qualquer lugar da memória, se descobrir que não está armazenado em cache pela cpu - temos um problema, porque precisamos acessar a memória principal, que é mais lenta
  • CPUs modernas fazem predição de ramos. Eles tentam adivinhar se terão sucesso ou não e executam o código adiante no pipeline, portanto, acelere as coisas. Se a predição falhar, todos os cálculos feitos à frente pelo pipeline devem ser invalidados. Essa também é uma operação cara

Entao, para resumir:

  • Pode ser caro, se você realmente se preocupa com desempenho.
  • Você deve se preocupar com isso se, e somente se, estiver escrevendo raytracer em tempo real ou simulação biológica ou algo semelhante. Não há razão para se preocupar com isso na maior parte do mundo real.
Marcin
fonte
Leve isso para o próximo nível: e quanto às instruções if aninhadas e / ou compostas? A despesa pode se tornar bastante perceptível rapidamente se alguém escrever muitas declarações if como esta. E, uma vez que para a maioria dos desenvolvedores, as declarações if parecem uma operação fundamental, evitar a ramificação condicional complicada geralmente é relegado a uma preocupação estilística. As preocupações estilísticas ainda são importantes, mas muitas vezes no calor do momento podem ser a primeira preocupação a ser ignorada.
Jaydel
7

Os processadores modernos têm longos canais de execução, o que significa que várias instruções são executadas em vários estágios ao mesmo tempo. Eles nem sempre sabem o resultado de uma instrução quando a próxima começa a ser executada. Quando eles se deparam com um salto condicional (if), às vezes têm que esperar até que o pipeline esteja vazio antes de saber para que lado o ponteiro de instrução deve seguir.

Eu penso nisso como um longo trem de carga. Pode transportar muita carga rapidamente em linha reta, mas faz curvas mal.

Pentium 4 (Prescott) tinha um famoso pipeline de 31 estágios.

Mais na Wikipedia

Guge
fonte
3
1 para a metáfora do trem de carga - vou me lembrar disso na próxima vez que preciso explicar os pipelines do processador.
Daniel Pryden
6

Talvez a ramificação elimine a pré-busca da instrução da CPU?

activout.se
fonte
Em minha ... "pesquisa" eu aprendi sobre tabelas de salto e ramificação para as declarações switch, mas nada sobre as declarações if. Você poderia elaborar um pouco sobre isso?
pek
IIRC, a CPU geralmente faz a pré-busca de instruções ao longo de um único caminho de execução provável, mas uma instrução 'if' que causa um desvio do caminho de execução previsto invalidará as instruções pré-buscadas e a pré-busca terá que reiniciar.
activout.se
Qualquer processador decente deve ter recursos de previsão de ramificação que tentem adivinhar se uma ramificação será obtida ou não, e a instrução de pré-busca com base na previsão (que geralmente é muito boa). O GCC tem até extensões C que permitem a um programador fornecer dicas para preditores de ramificação.
mipadi
2
Além disso, a CPU geralmente olha para a frente para começar a executar as instruções futuras mais cedo (não apenas pré-buscá-las), e o compilador tenta reordenar as instruções, e isso se torna perigoso entre os ramos, então você pode realmente interromper o agendamento de instruções com muitos ramos. O que prejudica o desempenho.
jalf
6

Observe também que dentro de um loop não é necessariamente muito caro.

A CPU moderna assume na primeira visita de uma instrução if, que o "if-body" deve ser obtido (ou dito de outra forma: ele também assume que um loop-body deve ser obtido várias vezes) (*). Na segunda e nas próximas visitas, ele (a CPU) pode talvez olhar para a Tabela de histórico de filial e ver como a condição estava da última vez (era verdade? Era falsa?). Se fosse falso da última vez, a execução especulativa prosseguirá para o "senão" do if, ou além do loop.

(*) A regra é, na verdade, " ramificação direta não tomada, ramificação anterior tomada ". Em uma instrução if, há apenas um salto [para frente] (para o ponto após o corpo if) se a condição for avaliada como falsa (lembre-se: a CPU assume, de qualquer forma, não dar um desvio / salto), mas em um loop , pode haver uma ramificação para a frente para a posição após o loop (a não ser executada) e uma ramificação para trás na repetição (a ser executada).

Essa também é uma das razões pelas quais uma chamada para uma função virtual ou uma chamada de ponteiro de função não é tão pior quanto muitos supõem ( http://phresnel.org/blog/ )

Sebastian Mach
fonte
5

Como apontado por muitos, os desvios condicionais podem ser muito lentos em um computador moderno.

Dito isso, há muitos ramos condicionais que não residem em declarações if, você nem sempre pode dizer o que o compilador vai fazer, e se preocupar com quanto tempo as declarações básicas vão levar é quase sempre a coisa errada façam. (Se você souber o que o compilador gerará de maneira confiável, talvez não tenha um bom compilador de otimização.)

David Thornley
fonte
4

A única coisa a que posso imaginar que isso se refira é o fato de que uma ifinstrução geralmente pode resultar em um desvio. Dependendo das especificações da arquitetura do processador, as ramificações podem causar paralisações no pipeline ou outras situações não ideais.

No entanto, isso é extremamente específico da situação - a maioria dos processadores modernos tem recursos de previsão de ramificação que tentam minimizar os efeitos negativos da ramificação. Outro exemplo seria como a arquitetura ARM (e provavelmente outras) pode lidar com a lógica condicional - o ARM tem execução condicional no nível de instrução, então a lógica condicional simples resulta em nenhuma ramificação - as instruções simplesmente são executadas como NOPs se as condições não forem atendidas.

Tudo isso dito - acerte sua lógica antes de se preocupar com essas coisas. O código incorreto é tão inoportuno quanto você pode obter.

Michael Burr
fonte
Ouvi dizer que as instruções condicionais do ARM inibem o ILP, então eles podem estar apenas empurrando o problema.
JD
3

CPUs são profundamente canalizadas. Qualquer instrução de desvio (if / for / while / switch / etc) significa que a CPU não sabe realmente qual instrução carregar e executar a seguir.

A CPU trava enquanto espera para saber o que fazer ou dá um palpite. No caso de uma CPU mais antiga, ou se a suposição estiver errada, você terá que sofrer uma paralisação do pipeline enquanto ele carrega a instrução correta. Dependendo da CPU, isso pode chegar a 10-20 instruções com perda de capacidade.

CPUs modernas tentam evitar isso fazendo uma boa previsão de branch e executando vários caminhos ao mesmo tempo, e mantendo apenas o caminho real. Isso ajuda muito, mas só pode ir até certo ponto.

Boa sorte na aula.

Além disso, se você precisa se preocupar com isso na vida real, provavelmente está fazendo design de sistema operacional, gráficos em tempo real, computação científica ou algo semelhante vinculado à CPU. Perfil antes de se preocupar.

tfinniga
fonte
2

Escreva seus programas da maneira mais clara, simples e limpa que não seja obviamente ineficiente. Isso faz o melhor uso do recurso mais caro, você. Seja escrevendo ou depurando posteriormente (requer compreensão) o programa. Se o desempenho não for suficiente, meçaonde estão os gargalos e veja como mitigá-los. Apenas em ocasiões extremamente raras você terá que se preocupar com instruções individuais (fonte) ao fazer isso. Desempenho significa selecionar os algoritmos e estruturas de dados certos na primeira linha, programação cuidadosa e obter uma máquina rápida o suficiente. Use um bom compilador, você ficaria surpreso ao ver o tipo de reestruturação de código que um compilador moderno faz. A reestruturação do código para o desempenho é uma espécie de medida de último recurso, o código fica mais complexo (portanto, mais problemático), mais difícil de modificar e, portanto, mais caro.

Vonbrand
fonte
0

Eu tive essa discussão com um amigo meu uma vez. Ele estava usando um algoritmo de círculo muito ingênuo, mas alegou que era mais rápido que o meu (o tipo que calcula apenas 1/8 do círculo) porque o meu usava if. No final, a instrução if foi substituída por sqrt e de alguma forma isso foi mais rápido. Talvez porque a FPU tenha sqrt embutido?

Demur Rumed
fonte
-1

O mais caro em termos de uso de ALU? Ele usa registros da CPU para armazenar os valores a serem comparados e leva tempo para buscar e comparar os valores cada vez que a instrução if é executada.

Portanto, uma otimização disso é fazer uma comparação e armazenar o resultado como uma variável antes que o loop seja executado.

Apenas tentando interpretar as palavras que faltam.


fonte