결과가 무엇이든 상관없이 0으로 나누기를 지원하는 가장 빠른 정수 나누기는 무엇입니까?

결과가 무엇이든 상관없이 0으로 나누기를 지원하는 가장 빠른 정수 나누기는 무엇입니까?

---

요약:

가장 빠른 계산 방법을 찾고 있습니다

(int) x / (int) y

에 대한 예외를받지 않고 y==0. 대신 임의의 결과를 원합니다.

---

배경:

이미지 처리 알고리즘을 코딩 할 때 종종 (누적 된) 알파 값으로 나눌 필요가 있습니다. 가장 간단한 변형은 정수 산술을 사용하는 일반 C 코드입니다. 내 문제는 일반적으로 결과 픽셀에 대해 0으로 나누기 오류가 발생한다는 것입니다 alpha==0. 그러나 이것은 결과가 전혀 중요하지 않은 픽셀입니다 alpha==0. 나는로 픽셀의 색상 값에 신경 쓰지 않습니다 .

---

세부:

나는 다음과 같은 것을 찾고있다 :

result = (y==0)? 0 : x/y;

또는

result = x / MAX( y, 1 );

x 및 y는 양의 정수입니다. 코드는 중첩 루프에서 여러 번 실행되므로 조건부 분기를 제거하는 방법을 찾고 있습니다.

y가 바이트 범위를 초과하지 않으면 솔루션에 만족합니다.

unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];

그러나 이것은 분명히 더 큰 범위에서는 잘 작동하지 않습니다.

마지막 질문은 다음과 같습니다. 가장 빠른 비트 twiddling 핵은 0을 다른 정수 값으로 변경하고 다른 모든 값은 변경하지 않고 그대로 있습니까?

---

설명

분기가 너무 비싸다는 것을 100 % 확신하지 못합니다. 그러나 다른 컴파일러가 사용되므로 최적화가 거의없는 벤치마킹을 선호합니다 (실제로 의심의 여지가 있음).

확실히, 비트 twiddling에 관해서는 컴파일러가 훌륭하지만 C에서 "무관심"결과를 표현할 수 없으므로 컴파일러는 전체 범위의 최적화를 사용할 수 없습니다.

코드는 C와 완벽하게 호환되어야하며, 주 플랫폼은 gcc & clang 및 MacOS가있는 Linux 64 비트입니다.

---

Pentium과 gcc컴파일러를 사용하여 분기를 제거 한 의견 중 일부에서 영감을 얻었습니다.

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

컴파일러는 기본적으로 추가시 테스트의 조건 플래그를 사용할 수 있음을 인식합니다.

요청에 따라 어셈블리 :

.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

As this turned out to be such a popular question and answer, I'll elaborate a bit more. The above example is based on programming idiom that a compiler recognizes. In the above case a boolean expression is used in integral arithmetic and the use of condition flags are invented in hardware for this purpose. In general condition flags are only accessible in C through using idiom. That is why it so hard to make a portable multiple precision integer library in C without resorting to (inline) assembly. My guess is that most decent compilers will understand the above idiom.

Another way of avoiding branches, as also remarked in some of the above comments, is predicated execution. I therefore took philipp's first code and my code and ran it through the compiler from ARM and the GCC compiler for the ARM architecture, which features predicated execution. Both compilers avoid the branch in both samples of code:

Philipp's version with the ARM compiler:

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

Philipp's version with GCC:

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

My code with the ARM compiler:

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

My code with GCC:

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

All versions still need a branch to the division routine, because this version of the ARM doesn't have hardware for a division, but the test for y == 0 is fully implemented through predicated execution.

---

Here are some concrete numbers, on Windows using 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);
}

Note that I am intentionally not calling srand(), so that rand() always returns exactly the same results. Note also that -DCHECK=0 merely counts the zeroes, so that it is obvious how often appeared.

Now, compiling and timing it various ways:

$ 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

shows output that can be summarised in a table:

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

If zeroes are rare, the -DCHECK=2 version performs badly. As zeroes start appearing more, the -DCHECK=2 case starts performing significantly better. Out of the other options, there really isn't much difference.

For -O3, though, it is a different story:

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

There, check 2 has no drawback compared the other checks, and it does keep the benefits as zeroes become more common.

You should really measure to see what happens with your compiler and your representative sample data, though.

---

Without knowing the platform there is no way to know the exact most efficient method, however, on a generic system this may close to the optimum (using Intel assembler syntax):

(assume divisor is in ecx and the dividend is in eax)

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

Four unbranched, single-cycle instructions plus the divide. The quotient will be in eax and the remainder will be in edx at the end. (This kind of shows why you don't want to send a compiler to do a man's job).

---

According to this link, you can just block the SIGFPE signal with sigaction() (I have not tried it myself, but I believe it should work).

This is the fastest possible approach if divide by zero errors are extremely rare: you only pay for the divisions by zero, not for the valid divisions, the normal execution path is not changed at all.

However, the OS will be involved in every exception that's ignored, which is expensive. I think, you should have at least a thousand good divisions per division by zero that you ignore. If exceptions are more frequent than that, you'll likely pay more by ignoring the exceptions than by checking every value before the division.

참고URL : https://stackoverflow.com/questions/16777456/what-is-the-fastest-integer-division-supporting-division-by-zero-no-matter-what