Resumo:
Estou procurando a maneira mais rápida de calcular
(int) x / (int) y
sem obter uma exceção para y==0
. Em vez disso, quero apenas um resultado arbitrário.
Fundo:
Ao codificar algoritmos de processamento de imagem, geralmente preciso dividir por um valor alfa (acumulado). A variante mais simples é o código C simples com aritmética de inteiros. Meu problema é que normalmente obtenho uma divisão por erro zero para pixels de resultado com alpha==0
. No entanto, estes são exatamente os pixels em que o resultado não importa em absoluto: Não me importo com os valores de cor dos pixels com alpha==0
.
Detalhes:
Estou procurando algo como:
result = (y==0)? 0 : x/y;
ou
result = x / MAX( y, 1 );
x e y são inteiros positivos. O código é executado um grande número de vezes em um loop aninhado, então estou procurando uma maneira de me livrar da ramificação condicional.
Quando y não excede o intervalo de bytes, fico feliz com a solução
unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];
Mas isso obviamente não funciona bem para intervalos maiores.
Eu acho que a pergunta final é: Qual é o hack de twiddling de bits mais rápido, alterando 0 para qualquer outro valor inteiro, enquanto deixa todos os outros valores inalterados?
Esclarecimentos
Não estou 100% certo de que a ramificação é muito cara. No entanto, diferentes compiladores são usados, então eu prefiro benchmarking com poucas otimizações (o que é realmente questionável).
Com certeza, os compiladores são ótimos quando se trata de manipulação de bits, mas não posso expressar o resultado "não me importo" em C, então o compilador nunca será capaz de usar toda a gama de otimizações.
O código deve ser totalmente compatível com C, as plataformas principais são Linux 64 bits com gcc & clang e MacOS.
fonte
y += !y
? Nenhum ramo necessário para computar isso. Você poderia compararx / (y + !y)
contrax / max(y, 1)
e talvez tambémy ? (x/y) : 0
. Acho que não haverá ramificação em nenhum deles, pelo menos com as otimizações ativadas.0
seções alfa forem enormes e contíguas. Existe um lugar para brincar com micro otimizações, e operações por pixel é exatamente esse lugar.Respostas:
Inspirado por alguns dos comentários, eliminei o branch no meu Pentium e
gcc
compilador usandoO compilador basicamente reconhece que pode usar um sinalizador de condição do teste na adição.
Conforme solicitação da montagem:
Como essa se tornou uma pergunta e resposta tão popular, vou elaborar um pouco mais. O exemplo acima é baseado no idioma de programação que um compilador reconhece. No caso acima, uma expressão booleana é usada na aritmética integral e o uso de sinalizadores de condição é inventado no hardware para esse propósito. Em geral, os sinalizadores de condição são acessíveis apenas em C por meio do idioma. É por isso que é tão difícil fazer uma biblioteca de inteiros de precisão múltipla portátil em C sem recorrer ao assembly (embutido). Meu palpite é que a maioria dos compiladores decentes entenderá o idioma acima.
Outra forma de evitar desvios, como também observado em alguns dos comentários acima, é a execução predicada. Portanto, peguei o primeiro código de philipp e o meu código e o executei no compilador do ARM e no compilador GCC para a arquitetura ARM, que apresenta execução predicada. Ambos os compiladores evitam o desvio em ambas as amostras de código:
Versão de Philipp com o compilador ARM:
Versão de Philipp com GCC:
Meu código com o compilador ARM:
Meu código com GCC:
Todas as versões ainda precisam de um desvio para a rotina de divisão, pois esta versão do ARM não possui hardware para uma divisão, mas o teste para
y == 0
é totalmente implementado por meio de execução predicada.fonte
constexpr
e evitar moldes desnecessários como este:template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); }
E se você quiser255
,(lhs)/(rhs+!rhs) & -!rhs
|
não&
. Ooops -( (lhs)/(rhs+!rhs) ) | -!rhs
deve definir seu valor para0xFFFFFFF
ifrhs
is0
, andlhs/rhs
ifrhs!=0
.Aqui estão alguns números concretos, no Windows usando GCC 4.7.2:
Observe que não estou chamando intencionalmente
srand()
, de modo querand()
sempre retorna exatamente os mesmos resultados. Observe também que-DCHECK=0
apenas conta os zeros, de modo que é óbvio com que freqüência apareceu.Agora, compilando e sincronizando de várias maneiras:
mostra a saída que pode ser resumida em uma tabela:
Se os zeros forem raros, a
-DCHECK=2
versão terá um desempenho ruim. À medida que zeros começam a aparecer mais, o-DCHECK=2
case começa a ter um desempenho significativamente melhor. Entre as outras opções, realmente não há muita diferença.Pois
-O3
, porém, é uma história diferente:Nesse caso, o cheque 2 não tem nenhuma desvantagem em comparação com os outros cheques e mantém os benefícios conforme os zeros se tornam mais comuns.
Você realmente deve medir para ver o que acontece com seu compilador e seus dados de amostra representativos, no entanto.
fonte
d=0
aleatórias, em vez de fazer quase sempred!=0
, e você verá mais falhas de previsão de ramificação. A previsão de ramos é ótima se um ramo é quase sempre seguido, ou se seguir um ramo ou outro é realmented
iteração é o loop interno, então osd == 0
casos são distribuídos uniformemente. E 50% dos casos sãod == 0
realistas?0.002%
dos casosd==0
realista? Eles são distribuídos por toda parte, a cada 65.000 iterações que você acertad==0
. Embora50%
possa não acontecer com frequência,10%
ou1%
poderia acontecer facilmente, ou mesmo90%
ou99%
. O teste conforme exibido apenas testa realmente "se você basicamente nunca, nunca descer um galho, a previsão de desvio torna a remoção do galho inútil?", Para o qual a resposta é "sim, mas isso não é interessante".Sem conhecer a plataforma, não há como saber o método mais eficiente exato, no entanto, em um sistema genérico isso pode ser próximo do ideal (usando a sintaxe do montador Intel):
(suponha que o divisor esteja dentro
ecx
e o dividendo esteja dentroeax
)Quatro instruções de ciclo único não ramificadas mais a divisão. O quociente estará dentro
eax
e o restante estaráedx
no final. (Isso meio que mostra porque você não quer enviar um compilador para fazer o trabalho de um homem).fonte
De acordo com este link , você pode simplesmente bloquear o sinal SIGFPE com
sigaction()
(não tentei sozinho, mas acredito que deve funcionar).Esta é a abordagem mais rápida possível se os erros de divisão por zero forem extremamente raros: você só paga pelas divisões por zero, não pelas divisões válidas, o caminho de execução normal não é alterado de forma alguma.
No entanto, o sistema operacional estará envolvido em todas as exceções ignoradas, o que é caro. Eu acho que você deve ter pelo menos mil divisões boas por divisão por zero que você ignora. Se as exceções forem mais frequentes do que isso, você provavelmente pagará mais ignorando as exceções do que verificando cada valor antes da divisão.
fonte