Parallel Mergesort 基准测试 - 确定找到的阈值

Question

我正在尝试确定停止细分我的 Mergesort 实现的合理阈值。但是，我得到的结果是阈值应该在 10 7 < x < 10 8之间，这是荒谬的，因为 java 使用的默认阈值约为 8192。它基本上告诉我细分几乎总是不好的，更高的阈值更好，因为它执行的拆分更少。它目前所做的工作是对一个大小为 10 8且随机范围为0to的浮点数数组进行排序1000。对每个测试的阈值重复使用相同的随机数组。public class ParallelMergeSort extends SortStrategy {    @Override    public long sort(float[] a, int cores, int threshold) {        System.gc();        long start = System.nanoTime();        RecursiveAction mainTask = new SortTask(a, 0, a.length - 1);        SortTask.threshold = threshold;        ForkJoinPool pool = new ForkJoinPool(cores);        pool.invoke(mainTask);        return System.nanoTime() - start;    }    private static class SortTask extends RecursiveAction {        private float[] a;        private int left, right;        private static int threshold;        SortTask(float[] a, int left, int right) {            this.a = a;            this.left = left;            this.right = right;        }        @Override        protected void compute() {            if (left < right) {                if ((right - left) < threshold) {                    Arrays.sort(a, left, right + 1);                } else {                    int mid = (left + right)/2;                    invokeAll(                        new SortTask(a, left, mid),                        new SortTask(a, mid + 1, right)                    );                    // Merge                    int n1 = mid - left + 1;                    int n2 = right - mid;                    float a1[] = new float[n1];                    float a2[] = new float[n2];                    // Fill sub arrays                    for (int i = 0; i < n1; ++i)                        a1[i] = a[left + i];                    for (int j = 0; j < n2; ++j)                        a2[j] = a[mid + 1 + j];                }            }        }    }}我知道由于 JIT，JVM 可能不可靠，但它应该只影响前几次迭代，不是吗？寻找有关算法的建议或为什么我的结果与我的预期相差甚远。

Answer 1

最佳阈值是允许与系统中的内核一样多的线程并行运行的阈值。

如果你的系统有cores核心，阈值应该是 test 应该初始化为

SortTask.threshold = cores > 0 ? (a.length + cores - 1) / cores : a.length;

由于最后几个合并阶段不能并行运行，因此速度提升将小于内核数量。

^{由于您正在对包含 10 8}个元素的数组进行排序，因此最佳阈值确实在 10 ⁷和 10 ⁸之间，除非您有 10 个以上的内核。