Java fork-join性能

Question

我有Merge-Sort的示例实现，一个使用Fork-Join，另一个是直接递归函数。

看起来fork-join比直接递归慢，为什么？

import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

class DivideTask extends RecursiveTask<int[]> {
    private static final long serialVersionUID = -7017440434091885703L;
    int[] arrayToDivide;

    public DivideTask(int[] arrayToDivide) {
        this.arrayToDivide = arrayToDivide;
    }

    @Override
    protected int[] compute() {
        //List<RecursiveTask> forkedTasks = new ArrayList<>();

        /*
         * We divide the array till it has only 1 element. 
         * We can also custom define this value to say some 
         * 5 elements. In which case the return would be
         * Arrays.sort(arrayToDivide) instead.
         */
        if (arrayToDivide.length > 1) {

            List<int[]> partitionedArray = partitionArray();

            DivideTask task1 = new DivideTask(partitionedArray.get(0));
            DivideTask task2 = new DivideTask(partitionedArray.get(1));
            invokeAll(task1, task2);

            //Wait for results from both the tasks
            int[] array1 = task1.join();
            int[] array2 = task2.join();

            //Initialize a merged array
            int[] mergedArray = new int[array1.length + array2.length];

            mergeArrays(task1.join(), task2.join(), mergedArray);

            return mergedArray;
        }
        return arrayToDivide;
    }

    private void mergeArrays(int[] array1, int[] array2, int[] mergedArray) {

        int i = 0, j = 0, k = 0;

        while ((i < array1.length) && (j < array2.length)) {

            if (array1[i] < array2[j]) {
                mergedArray[k] = array1[i++];
            } else {
                mergedArray[k] = array2[j++];
            }

            k++;
        }

        if (i == array1.length) {
            for (int a = j; a < array2.length; a++) {
                mergedArray[k++] = array2[a];
            }
        } else {
            for (int a = i; a < array1.length; a++) {
                mergedArray[k++] = array1[a];
            }
        }
    }

    private List<int[]> partitionArray() {
        int[] partition1 = Arrays.copyOfRange(arrayToDivide, 0, arrayToDivide.length / 2);

        int[] partition2 = Arrays.copyOfRange(arrayToDivide, arrayToDivide.length / 2, arrayToDivide.length);
        return Arrays.asList(partition1, partition2);
    }
}

public class ForkJoinTest {
    static int[] numbers;
    static final int SIZE = 1_000_000;
    static final int MAX = 20;

    public static void main(String[] args) {
        setUp();

        testMergeSortByFJ();
        testMergeSort();
    }

    static void setUp() {
        numbers = new int[SIZE];
        Random generator = new Random();
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = generator.nextInt(MAX);
        }
    }

    static void testMergeSort() {
        long startTime = System.currentTimeMillis();

        Mergesort sorter = new Mergesort();
        sorter.sort(numbers);

        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Mergesort Time:" + elapsedTime + " msec");
    }

    static void testMergeSortByFJ() {
        //System.out.println("Unsorted array: " + Arrays.toString(numbers));
        long t1 = System.currentTimeMillis();
        DivideTask task = new DivideTask(numbers);
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        forkJoinPool.invoke(task);
        //System.out.println("Sorted array: " + Arrays.toString(task.join()));
        System.out.println("Fork-Join Time:" + (System.currentTimeMillis() - t1) + " msec");
    }
 }

class Mergesort {
    private int[] msNumbers;
    private int[] helper;

    private int number;

    private void merge(int low, int middle, int high) {

        // Copy both parts into the helper array
        for (int i = low; i <= high; i++) {
            helper[i] = msNumbers[i];
        }

        int i = low;
        int j = middle + 1;
        int k = low;
        // Copy the smallest values from either the left or the right side back
        // to the original array
        while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {
                msNumbers[k] = helper[i];
                i++;
            } else {
                msNumbers[k] = helper[j];
                j++;
            }
            k++;
        }
        // Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            msNumbers[k] = helper[i];
            k++;
            i++;
        }

    }

    private void mergesort(int low, int high) {
        // Check if low is smaller then high, if not then the array is sorted
        if (low < high) {
            // Get the index of the element which is in the middle
            int middle = low + (high - low) / 2;
            // Sort the left side of the array
            mergesort(low, middle);
            // Sort the right side of the array
            mergesort(middle + 1, high);
            // Combine them both
            merge(low, middle, high);
        }
    }

    public void sort(int[] values) {
        this.msNumbers = values;
        number = values.length;
        this.helper = new int[number];
        mergesort(0, number - 1);
    }
}

Answer 1

我的主要原因不是由于线程产生和池化而产生的开销。

我认为多线程版本运行缓慢的主要原因是，你一直在不断地创建新的数组，数百万次。最终，您用一个元素创建了一百万个数组，这让垃圾收集器很头疼。

所有的DivideTask都只能在数组的不同部分(两部分)上操作，所以只需向它们发送一个范围，并使它们在该范围上操作。

此外，您的并行化策略使得不可能使用巧妙的“助手数组”优化(请注意顺序版本中的helper数组)。这种优化将"input“数组与进行合并的"helper”数组进行交换，这样就不会为每个合并操作创建一个新的数组:这是一种节省内存的技术，如果不按递归树的级别进行并行化就无法做到这一点。

对于类作业，我必须并行化MergeSort，并且通过按递归树的级别并行化，我设法获得了很好的加速。不幸的是，代码是用C语言编写的，并使用了OpenMP。如果你愿意，我可以提供给你。

Answer 2

正如gd1所指出的，您正在进行大量的数组分配和复制；这将耗费您的成本。相反，您应该在同一数组的不同部分上工作，要注意没有任何子任务在另一个子任务正在处理的部分上工作。

但除此之外，fork/join方法(与任何并发方法一样)都会带来一定的开销。事实上，如果你看看RecursiveTask的javadoc，他们甚至指出他们的简单示例执行起来会很慢，因为forking太细粒度了。

长话短说，你应该有更少的细分，每个细分都做得更多。更普遍的是，任何时候你有比核心更多的非阻塞线程，吞吐量不会提高，实际上开销会开始消耗它。

Answer 3

如果不深入研究您的代码，派生新线程的成本是很高的。如果您没有太多的工作要做，那么仅仅出于性能原因就不值得这样做。这里说得非常笼统，但在新线程产生并开始运行之前，单个线程可能会循环数千次(特别是在Windows上)。

请参考Doug Lea's paper (在2.设计下)，其中他声明：

但是，java.lang.Thread类(以及Java线程通常基于的POSIX pthread)不是支持fork/join程序的最佳工具