3

画像処理機能の一部として、画像内の 2 つの線の間の平方和を計算する必要があります。

コードのこの部分は、実行時間の 96% を占めます。

for(int dx=0;dx<size;dx++) {
    int left = a[pa+dx];
    int right = b[pb+dx];
    int diff = (left & 0xFF) - (right & 0xFF);
    sum += diff*diff;
}

どこ：

  • a、bタイプですbyte[]
  • sumはlong
  • sizeでありint、一般的に大きな値を持っています (約 400)

Java 7 64 ビットを実行しています。 性能が良くないa[pa+dx]ようなものに交換しようとしました。a[pa++]

正確に保存を行う C++ で書かれたまったく同じコードは、全体的に 2 倍速く実行されます (!)。私が見る限り、特に境界チェックがコンパイラによるループ。

このようなものを C++ コードと同様に実行するように最適化するにはどうすればよいですか?

編集: C++ サンプルは次のようになります。

unsigned char const *srcptr=&a[pa];
unsigned char const *tgtptr=&b[pb];
for(int dx=0;dx < size;dx++) {
    int p1=*srcptr++;
    int p2=*tgtptr++;
    int diff = p1 - p2;
    sum += diff * diff;
}

HotSpot オプティマイザを作成して、上記の C++ コードと同じくらい高速なコードを作成する方法を見つけたいと思います。最終的に、行を最適化するのは非常に単純で簡単です。

4

4 に答える 4

2

& 0xFFほんのわずかですが、差を計算する必要はありません。差は、符号付きでも符号なしでも同じです。

100 - -1 = 101  // signed
228 - 127 = 101 // unsigned

次に、よりタイトなループ本体になります。

for (int dx = 0; dx < size; dx++) {
    int diff = a[pa+dx] - b[pb+dx];
    sum += diff*diff;
}

編集：

符号付きバイト演算と符号なしバイト演算に関して混乱があるようです。それらが同じである疑いがある場合は、これを実行します。

byte a = -128;
byte b = 127;
int diff = a - b;
System.out.println(diff); // -255

a = 127;
b = -128;
diff = a - b;
System.out.println(diff); // 255

差分値の範囲が(-128..127)より大きい理由は、宛先変数が.bytebyteint int

于 2012-09-28T19:36:40.607 に答える
1

異なるC++コンパイラと異なるJavaバージョンを使用して同じアルゴリズムをテストした後、GCCは非常に優れたコンパイラであり、IntelやClangよりもコードを最適化するという結論に達しました。

これらは、C ++およびJavaで実装された同じアルゴリズムの実行時間です（上の行が実行時間の96％の場合：

Intel 12.1  1:58
GCC 4.6     0:43
GCC 4.4     0:43
Clang       1:20
Java 7      1:20
Java 6      1:23

これは、Javaがclangと同じくらい高速に実行され、何らかの理由でIntelコンパイラが非常に悪い仕事をすることを示していますが、gccが最良の結果をもたらすため、JavaがほとんどのC++コンパイラよりも高速に実行されることは期待できません。

これはgccによって生成されたアセンブリであることに注意してください。

.L225:
    movzbl  (%rcx), %r8d
    movzbl  (%rsi), %r10d
    addl    $1, %edx
    addq    $1, %rcx
    addq    $1, %rsi
    subl    %r10d, %r8d
    imull   %r8d, %r8d
    movslq  %r8d, %r8
    addq    %r8, %rax
    cmpl    %edx, %ebp
    ja      .L225

そしてこれはclangによって生成されたものです：

.LBB0_26:
    movzbl  (%r11), %r13d
    movzbl  (%r14), %esi
    subl    %r13d, %esi
    imull   %esi, %esi
    movslq  %esi, %rsi
    addq    %rsi, %rcx
    incq    %r11
    incq    %r14
    decq    %r12
    jne     .LBB0_26

違いはなんですか？GCCは、パイプラインで並列に実行できるように命令を再配置します。次に例を示します。

    movzbl  (%rcx), %r8d
    movzbl  (%rsi), %r10d
    addl    $1, %edx
    addq    $1, %rcx
    addq    $1, %rsi

結論として、Javaの実行時間は問題ありません。

編集： Intelコンパイラにオプションを提供した後-xHost（現在のCPUに最適化）、実行時間は56秒に改善されました（mmx命令を使用）が、それでもgccほど高速ではありませんが、Javaより少し優れています

于 2012-09-29T11:15:55.203 に答える
1

& 0xFFをループの外に 移動します。

これを行うには、とint[]の両方のバージョンを計算し、これらを使用してループを書き直します。ab

于 2012-09-29T12:50:32.437 に答える
-1

配列 a または b のサイズが "size" の場合、for 条件を回避できます。

try{
    for (int dx = 0; ; dx++) {
        ...
        ...
    }
}catch(ArrayIndexOutOfBoundException e){}

2本の線は直線ですか、それとも曲線ですか? 問題のグラフ表現、または配列の数値例を投稿できますか? 多分より良い幾何学的解決策がありますか？

于 2012-09-28T22:35:17.187 に答える