3

作为图像处理功能的一部分，我需要计算图像中两条线之间的平方和。

这部分代码占用了 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++ 编写的代码完全保存运行速度总体快了两倍（！），据我所知，应该没有重要的原因为什么这个 Java 代码不会那么快，特别是当边界检查可以移出时编译器的循环。

如何优化这些东西以像 C++ 代码一样执行 - 最后它是整数运算，它在 Java 中应该不会慢很多

编辑：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

diff值的范围大于（-128..127）的原因是java在计算之前自动扩大到，因为目标变量是一个.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 一样快，而英特尔编译器由于某种原因做得非常糟糕，但是 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[]两者的版本来做到这一点，a并b使用这些重写你的循环。

于 2012-09-29T12:50:32.437 回答
-1

如果数组 a 或 b 的大小为“size”，则可以避免 for 条件：

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

两条线是直的还是弯的？您可以发布问题的图形表示，还是数组的数字示例？也许有更好的几何解决方案？

于 2012-09-28T22:35:17.187 回答