java - 为什么在 Java8 中将最小粒度定义为 8192 以便从并行排序切换到 Arrays.sort 而不管数据类型

Question

我正在研究 Java 8 中引入的并行排序概念。 根据 doc .

If the length of the specified array is less than the minimum granularity, then it is sorted using the appropriate Arrays.sort method.

然而，规范并未指定此最低限制。
当我在 java.util.Arrays 中查找代码时，它被定义为

private static final int MIN_ARRAY_SORT_GRAN = 1 << 13; 

即数组中的 8192 个值

根据提供的解释 here . 我理解为什么该值被硬编码为 8192。

It was designed keeping the current CPU architecture in mind.
With the -XX:+UseCompressedOops option being enabled by default, any system with less than 32GB RAM would be using 32bit(4bytes) pointers. Now, with a L1 Cache size of 32KB for data portion, we can pass 32KB/4Bytes = 8KB of data at once to CPU for computation. That's equivalent to 8192 bytes of data being processed at once.

因此对于一个正在对字节数组进行排序的函数 parallelSort(byte[]) 这是有道理的。您可以将最小并行排序限制保持为 8192 个值(对于字节数组，每个值 = 1 个字节)。

但是如果你考虑public static void parallelSort(int[] a)

一个整型变量是 4 字节(32 位)。所以理想情况下，在 8192 字节中，我们可以一次在 CPU 缓存中存储 8192/4 = 2048 个数字。 因此本例中的最小粒度假设为 2048。

为什么 Java 中的所有 parallelSort 函数(例如 byte[]、int[]、long[] 等)都使用 8192 作为默认最小值。执行并行排序需要多少个值？
它不应该根据传递给 parallelSort 函数的类型而变化吗？

Answer 1

首先，您似乎误读了链接的解释。 L1 数据缓存为 32Kb，因此对于 int[] 它非常适合:32768/4=8192 int 可以放入 L1 缓存中。

其次，我认为给出的解释不正确。它专注于指针，所以它主要说的是对象数组的排序，但是当你比较对象数组中的数据时，你总是需要解引用这些指针来访问真正的数据。如果您的对象具有非原始字段，您将不得不进一步取消引用它们。例如，如果您对字符串数组进行排序，您不仅要访问数组本身，还要访问 String 对象和存储在其中的 char[] 数组。所有这些都需要许多额外的缓存行。

我在 review thread 中没有找到关于这个特定值的任何明确解释对于这个改变。以前是 256，然后作为 JDK-8014076 的一部分更改为 8192更新。我认为它只是在一些合理的测试套件上显示出最佳性能。为不同的情况保持单独的阈值会增加更多的复杂性。可能测试表明它没有返回。请注意，对于 Object[] 数组来说，理想的阈值是不可能的，因为比较函数是用户指定的，并且可能具有任意复杂性。对于足够复杂的比较函数，并行化甚至非常小的数组可能是合理的。