Java fork-join性能

Question

我有合併排序的示例實現，其中一個使用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

恕我直言，主要原因不是線程產卵和池化造成的開銷。

我認爲多線程版本運行速度慢，主要是因爲你不斷創造新的陣列，所有的時間，數百萬次。最後，你用一個元素創建了100萬個數組，這讓垃圾收集器頭痛不已。

您所有的DivideTask s只能在陣列的不同部分（兩半）上操作，所以只需發送一個範圍並使其在該範圍內操作。

此外，您的並行策略使得不可能使用巧妙的「幫助程序陣列」優化（請注意順序版本中的helper陣列）。這種優化將「輸入」數組與「輔助」數組進行合併，從而不會爲每個合併操作創建一個新數組：一種節省內存的技術，如果不採取措施， t通過遞歸樹的級別並行化。

對於課堂作業，我必須並行化MergeSort，並通過按遞歸樹級別進行並行處理，從而設法獲得了很好的加速。不幸的是，代碼使用C語言，並使用OpenMP。如果你想我可以提供它。

Answer 2

沒有看太深的代碼，產生一個新的線程是昂貴的。如果你沒有太多的工作要做，那麼僅憑性能原因就不值得。通常在這裏談論，但是一個單獨的線程可能會循環數千次，然後纔會產生新線程並開始運行（特別是在Windows上）。

請參考Doug Lea's paper（下2.設計），其中他說：

「不過，java.lang.Thread類（以及POSIX並行線程，在其Java線程通常基於）是次優用於支持叉/加入程序的車輛「

Answer 3

正如gd1指出的，你正在做很多數組分配和複製;這會讓你付出代價。你應該在同一個數組的不同部分上工作，注意沒有任何子任務在另一個子任務正在工作的部分上工作。

但除此之外，fork/join方法會帶來一定的開銷（與任何併發一樣）。事實上，如果您查看RecursiveTask的javadoc，他們甚至會指出，他們的簡單示例執行起來會很慢，因爲分叉太細。

長話短說，你應該有更少的細分，其中每個細分更多。更一般地說，任何時候你有更多的非阻塞線程比核心，吞吐量不會改善，事實上開銷將開始削減它。

Answer 4

約叉工作還發現以下信息/加入 Dan Grossman's Introduction to Fork/Join