Qual é a divisão inteira mais rápida que suporta a divisão por zero, não importa qual seja o resultado?

109

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.

philipp
fonte
22
Como você determinou que o if-branch é muito caro?
Djechlin
7
Como você determinou que não é uma filial?
leemes
13
+1 para a criação de perfil, com a previsão de ramo moderna você pode não precisar disso. Além disso, por que você está codificando seus próprios algoritmos de processamento de imagem?
TC1
8
"Qual é o truque de torção mais rápido ..." Talvez y += !y? Nenhum ramo necessário para computar isso. Você poderia comparar x / (y + !y)contra x / max(y, 1)e talvez também y ? (x/y) : 0. Acho que não haverá ramificação em nenhum deles, pelo menos com as otimizações ativadas.
leemes
6
Qualquer um que pense que a previsão moderna de branch significa que você não precisa fazer isso não criou o perfil de código de eliminação de branch suficiente que roda em um nível por pixel. A previsão moderna de ramos é aceitável se as 0seções alfa forem enormes e contíguas. Existe um lugar para brincar com micro otimizações, e operações por pixel é exatamente esse lugar.
Yakk - Adam Nevraumont

Respostas:

107

Inspirado por alguns dos comentários, eliminei o branch no meu Pentium e gcccompilador usando

int f (int x, int y)
{
        y += y == 0;
        return x/y;
}

O compilador basicamente reconhece que pode usar um sinalizador de condição do teste na adição.

Conforme solicitação da montagem:

.globl f
    .type   f, @function
f:
    pushl   %ebp
    xorl    %eax, %eax
    movl    %esp, %ebp
    movl    12(%ebp), %edx
    testl   %edx, %edx
    sete    %al
    addl    %edx, %eax
    movl    8(%ebp), %edx
    movl    %eax, %ecx
    popl    %ebp
    movl    %edx, %eax
    sarl    $31, %edx
    idivl   %ecx
    ret

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:

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

Versão de Philipp com GCC:

f:
        subs    r3, r1, #0
        str     lr, [sp, #-4]!
        moveq   r0, r3
        ldreq   pc, [sp], #4
        bl      __divsi3
        ldr     pc, [sp], #4

Meu código com o compilador ARM:

f PROC
        RSBS     r2,r1,#1
        MOVCC    r2,#0
        ADD      r1,r1,r2
        B        __aeabi_idivmod

Meu código com GCC:

f:
        str     lr, [sp, #-4]!
        cmp     r1, #0
        addeq   r1, r1, #1
        bl      __divsi3
        ldr     pc, [sp], #4

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.

Bryan Olivier
fonte
Você poderia nos mostrar o código assembler resultante? Ou como você determinou que não há nenhum ramo?
Haatschii
1
Impressionante. Pode ser feito constexpre 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ê quiser 255,(lhs)/(rhs+!rhs) & -!rhs
Yakk - Adam Nevraumont
1
@leemes mas eu quis dizer |não &. Ooops - ( (lhs)/(rhs+!rhs) ) | -!rhsdeve definir seu valor para 0xFFFFFFFif rhsis 0, and lhs/rhsif rhs!=0.
Yakk - Adam Nevraumont
1
Isso foi muito inteligente.
Theodoros Chatzigiannakis
1
Ótima resposta! Costumo recorrer à montagem para este tipo de coisas, mas é sempre horrível de manter (para não falar menos portátil;)).
Leo
20

Aqui estão alguns números concretos, no Windows usando GCC 4.7.2:

#include <stdio.h>
#include <stdlib.h>

int main()
{
  unsigned int result = 0;
  for (int n = -500000000; n != 500000000; n++)
  {
    int d = -1;
    for (int i = 0; i != ITERATIONS; i++)
      d &= rand();

#if CHECK == 0
    if (d == 0) result++;
#elif CHECK == 1
    result += n / d;
#elif CHECK == 2
    result += n / (d + !d);
#elif CHECK == 3
    result += d == 0 ? 0 : n / d;
#elif CHECK == 4
    result += d == 0 ? 1 : n / d;
#elif CHECK == 5
    if (d != 0) result += n / d;
#endif
  }
  printf("%u\n", result);
}

Observe que não estou chamando intencionalmente srand(), de modo que rand()sempre retorna exatamente os mesmos resultados. Observe também que -DCHECK=0apenas conta os zeros, de modo que é óbvio com que freqüência apareceu.

Agora, compilando e sincronizando de várias maneiras:

$ for it in 0 1 2 3 4 5; do for ch in 0 1 2 3 4 5; do gcc test.cc -o test -O -DITERATIONS=$it -DCHECK=$ch && { time=`time ./test`; echo "Iterations $it, check $ch: exit status $?, output $time"; }; done; done

mostra a saída que pode ser resumida em uma tabela:

Iterations  | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.612s | -        | -        | -         | -         | -
Check 2      | 0m0.612s | 0m6.527s | 0m9.718s | 0m13.464s | 0m18.422s | 0m22.871s
Check 3      | 0m0.616s | 0m5.601s | 0m8.954s | 0m13.211s | 0m19.579s | 0m25.389s
Check 4      | 0m0.611s | 0m5.570s | 0m9.030s | 0m13.544s | 0m19.393s | 0m25.081s
Check 5      | 0m0.612s | 0m5.627s | 0m9.322s | 0m14.218s | 0m19.576s | 0m25.443s

Se os zeros forem raros, a -DCHECK=2versã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:

Iterations  | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.646s | -        | -        | -         | -         | -
Check 2      | 0m0.654s | 0m5.670s | 0m9.905s | 0m14.238s | 0m17.520s | 0m22.101s
Check 3      | 0m0.647s | 0m5.611s | 0m9.085s | 0m13.626s | 0m18.679s | 0m25.513s
Check 4      | 0m0.649s | 0m5.381s | 0m9.117s | 0m13.692s | 0m18.878s | 0m25.354s
Check 5      | 0m0.649s | 0m6.178s | 0m9.032s | 0m13.783s | 0m18.593s | 0m25.377s

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
4
Faça com que 50% das entradas sejam d=0aleatórias, em vez de fazer quase sempre d!=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 é realmente
difícil
@Yakk A diteração é o loop interno, então os d == 0casos são distribuídos uniformemente. E 50% dos casos são d == 0realistas?
2
Está fazendo 0.002% dos casos d==0realista? Eles são distribuídos por toda parte, a cada 65.000 iterações que você acerta d==0. Embora 50%possa não acontecer com frequência, 10%ou 1%poderia acontecer facilmente, ou mesmo 90%ou 99%. 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".
Yakk - Adam Nevraumont
1
Não, porque as diferenças serão efetivamente invisíveis devido ao ruído.
Joe
3
A distribuição de zeros não se relaciona com a distribuição encontrada na situação do questionador. As imagens que contêm uma mistura de 0 alfa e outras têm orifícios ou formato irregular, mas (geralmente) isso não é ruído. Supor que você não sabe nada sobre os dados (e considerá-los como ruído) é um erro. Este é um aplicativo do mundo real com imagens reais que podem ter 0 alfa. E uma vez que é provável que uma linha de pixels tenha todo a = 0 ou todo a> 0, tirar vantagem da predicação de ramo pode muito bem ser o mais rápido, especialmente quando a = 0 ocorre muito e divisões (lentas) (15+ ciclos !) são evitados.
DDS de
13

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 ecxe o dividendo esteja dentro eax)

mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx

Quatro instruções de ciclo único não ramificadas mais a divisão. O quociente estará dentro eaxe o restante estará edxno final. (Isso meio que mostra porque você não quer enviar um compilador para fazer o trabalho de um homem).

Tyler Durden
fonte
onde fica a divisão?
Yakk - Adam Nevraumont
1
isso não faz a divisão, apenas polui o divisor, de modo que a divisão por zero é impossível
Tyler Durden
@Jens Timmerman Desculpe, escrevi isso antes de adicionar a instrução div. Eu atualizei o texto.
Tyler Durden
1

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.

cmaster - reintegrar monica
fonte