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&nbsp;=&nbsp;cores&nbsp;>&nbsp;0&nbsp;?&nbsp;(a.length&nbsp;+&nbsp;cores&nbsp;-&nbsp;1)&nbsp;/&nbsp;cores&nbsp;:&nbsp;a.length;由于最后几个合并阶段不能并行运行，因此速度提升将小于内核数量。由于您正在对包含 10 8个元素的数组进行排序，因此最佳阈值确实在 10&nbsp;7和 10&nbsp;8之间，除非您有 10 个以上的内核。