为什么Java8中的最小粒度定义为8192,以便从Parallel Sort切换到Arrays.sort,而不管数据类型如何

Question

我正在阅读Java 8中引入的并行排序的概念.根据文档.

如果指定数组的长度小于最小粒度,则使用适当的Arrays.sort方法对其进行排序.

但是规范没有规定这个最低限度.
当我查找代码时,java.util.Arrays它被定义为

private static final int MIN_ARRAY_SORT_GRAN = 1 << 13; 

即,数组中的8192个值

根据这里提供的解释.我理解为什么值被硬编码为8192.

它的设计考虑了当前的CPU架构.默认情况下启用
该-XX:+UseCompressedOops选项,任何RAM少于32GB的系统都将使用32位(4字节)指针.现在,对于数据部分,L1 Cache大小为32KB,我们可以将32KB/4Bytes = 8KB的数据一次传递给CPU进行计算.这相当于一次处理8192个字节的数据.

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

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

整数变量为4Bytes(32位).理想情况下,8192字节,我们可以同时在CPU缓存中存储8192/4 = 2048个数字. 因此,在这种情况下,最小粒度假设为2048.

为什么所有parallelSort函数都使用Java(包括byte [],int [],long []等),使用8192作为默认min.为了执行并行排序所需的值的数量？
它应该根据传递给parallelSort函数的类型而有所不同吗？

Answer 1

首先,您似乎误读了链接的解释.L1数据缓存为32Kb,因此int[]理想情况下适合:32768/4=8192int可以放入L1缓存中.

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

我没有在审核线程中找到有关此特定值的明确解释.以前它是256,然后它作为JDK-8014076更新的一部分更改为8192 .我认为它只是在一些合理的测试套件上表现出最佳性能.为不同的案例保留单独的阈值会增加更多的复杂性.可能测试表明它没有得到回报.注意,对于Object[]数组来说理想阈值是不可能的,因为比较函数是用户指定的并且可能具有任意复杂性 对于足够复杂的比较函数,即使非常小的数组并行化也许是合理的.