java - 如何加速Java中的数组交集？

Question

下面的数组排序时没有重复(包含唯一的正整数)小尺寸(小于 5000)和交集(见下文)被调用十亿次，因此任何微优化都很重要。这article在 C 中很好地描述了如何加速以下代码语言。

int i = 0, j = 0, c = 0, la = a.length, lb = b.length;
intersection = new int[Math.min(la, lb)];
while (i < la && j < lb) {
    if (a[i] < b[j]) i++;
    else if (a[i] > b[j]) j++;
    else {
        intersection[c] = a[i];
        i++; j++; c++;
    }
}
int[] intersectionZip = new int[c];
System.arraycopy(intersection, 0, intersectionZip, 0, c);

我猜在 Java 中是不可能调用那些低级指令的。但是他们提到“可以使用无分支实现来改进这种方法”。怎么做呢？使用 switch ？或者可以替代 a[i] < b[j] , a[i] > b[j]或 a[i] == b[i]与整数操作数的二元运算比较？

二进制搜索方法(具有复杂性 O(la log(lb)) )并非如此，因为 la不是 <<比lb .有趣的是如何改变 if声明。

Answer 1

我不认为您可以做很多事情来提高 Java 代码的性能。但是，我会注意到它做的事情与 C 版本不同。 C 版本将交集放入调用者预先分配的数组中。 Java 版本自己分配数组......然后在完成后重新分配并复制到一个较小的数组。

我想，您可以更改 Java 版本以对输入数组进行两次传递，第一次传递计算出输入数组需要有多大……但它是有助于还是阻碍将取决于输入。

您可能还可以针对其他特殊情况进行优化；例如如果一个数组中可能有很长的数字，而另一个数组中的那个范围内没有任何数字，您也许可以“乐观地”尝试一次性跳过多个数字；即，将 i 或 j 增加一个大于 1 的数字。

---

But they mention that "it is possible to improve this approach using branchless implementation". How one would do it? Using switch?

不是 Java 开关...或条件表达式，因为它们在转换为 native 代码时都涉及分支。

我认为他指的是这样的东西:Branchless code that maps zero, negative, and positive to 0, 1, 2

FWIW 尝试在 Java 中做这种事情是个坏主意。问题在于，像这样的棘手代码序列的性能取决于硬件架构、指令集、时钟计数等细节，这些细节因平台而异。 Java JIT 编译器的优化器可以很好地优化您的代码……但是如果您包含棘手的序列:

1. 它们将如何转换为 native 代码并不明显或不可预测，并且
2. 您可能会发现这种棘手的做法实际上会阻碍 JIT 编译器本来可以进行的有用优化。

话虽如此，Java 的某些 future 版本可能包含一个 super 优化器并非不可能……就像上面链接的问答中提到的那样……能够自动生成无分支序列。但请记住， super 优化的执行成本非常高。