110

概要：

最速で計算する方法を探しています

(int) x / (int) y

の例外を取得せずにy==0。代わりに、任意の結果が必要です。

バックグラウンド：

画像処理アルゴリズムをコーディングするとき、(累積された) アルファ値で割る必要があることがよくあります。最も単純なバリアントは、整数演算を使用する単純な C コードです。私の問題は、通常、結果ピクセルのゼロ除算エラーが発生すること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];

しかし、これは明らかに、より大きな範囲ではうまく機能しません。

最後の質問は次のとおりだと思います: 他のすべての値を変更せずに、0 を他の整数値に変更する最速のビットいじりハックは何ですか?

明確化

分岐のコストが高すぎるとは 100% 確信が持てません。ただし、さまざまなコンパイラが使用されているため、最適化をほとんど行わないベンチマークを好みます (これには疑問があります)。

確かに、コンパイラはビット操作に関しては優れていますが、C では「ドント ケア」の結果を表現できないため、コンパイラは最適化の全範囲を使用することはできません。

コードは完全に C と互換性がある必要があります。主なプラットフォームは、gcc と clang を使用する Linux 64 ビットと MacOS です。

4

4 に答える 4

107

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

これは非常に人気のある質問と回答であることが判明したので、もう少し詳しく説明します。上記の例は、コンパイラが認識するプログラミング イディオムに基づいています。上記の場合、ブール式は整数演算で使用され、条件フラグの使用はこの目的のためにハードウェアで発明されました。一般に、条件フラグはイディオムを使用して C でのみアクセスできます。そのため、(インライン) アセンブリに頼らずに C で移植可能な多倍長整数ライブラリを作成することは非常に困難です。私の推測では、ほとんどのまともなコンパイラは上記のイディオムを理解するでしょう。

上記のコメントのいくつかでも述べられているように、分岐を回避する別の方法は、述語実行です。したがって、私は philipp の最初のコードと私のコードを取り、それを ARM のコンパイラと、述語実行を特徴とする ARM アーキテクチャ用の GCC コンパイラで実行しました。どちらのコンパイラも、コードの両方のサンプルで分岐を回避します。

ARM コンパイラを使用した Philipp のバージョン:

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

GCCを使用したフィリップのバージョン：

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

ARM コンパイラを使用した私のコード:

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

GCCを使用した私のコード:

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

このバージョンの ARM には除算用のハードウェアがないため、すべてのバージョンで除算ルーチンへの分岐が必要ですが、y == 0述語実行によってテストが完全に実装されます。

于 2013-05-27T17:14:32.197 に答える
21

GCC 4.7.2 を使用する Windows での具体的な数値を次に示します。

#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);
}

意図的に を呼び出していないことに注意してください。そのsrand()ため、rand()常にまったく同じ結果が返されます。-DCHECK=0また、 は単にゼロをカウントするだけなので、どのくらいの頻度で出現したかが明確になることに注意してください。

さて、さまざまな方法でコンパイルしてタイミングを合わせます。

$ 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

表に要約できる出力を示します。

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

ゼロがほとんどない場合、-DCHECK=2バージョンのパフォーマンスは低下します。ゼロがより多く出現し始めると、-DCHECK=2ケースのパフォーマンスが大幅に向上し始めます。他のオプションのうち、実際には大きな違いはありません。

-O3しかし、それは別の話です。

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

そこでは、チェック 2 には他のチェックと比較して欠点がなく、ゼロがより一般的になっても利点が維持されます。

ただし、実際に測定して、コンパイラと代表的なサンプル データで何が起こるかを確認する必要があります。

于 2013-05-27T18:13:10.090 に答える
13

プラットフォームを知らなければ、最も効率的な方法を正確に知る方法はありませんが、一般的なシステムでは、これが最適に近い場合があります (Intel アセンブラー構文を使用):

(除数が でecx、被除数が であると仮定しeaxます)

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

4 つの非分岐シングル サイクル命令と除算。最後に商がeax入り、余りが入りますedx。(これは、人の仕事をさせるためにコンパイラを送りたくない理由を示しています)。

于 2013-05-27T17:44:27.967 に答える