over 4 years ago

最近比較懶一點,所以今天還是只看一個小東西。比較Arrays這個工具類別在J2SE 7J2SE 8的API文件,會發現Arrays多了幾組靜態函式:stream(T[])setAll(T[], IntFunction<T>)parallelSetAll(T[], IntFunction<T>)parallelPrefix(T[], BinaryOperator<T>)spliterator(T[] array)parallelSort(T[], Comparator<T>)stream(T[])先前已經介紹過了,這裡只是把一個陣列包裝成stream來使用。

setAll(T[], IntFunction<T>)parallelSetAll(T[], IntFunction<T>)的功能是一樣的:用IntFunction的回傳值填滿整個array,IntFunction接受一個整數作為參數(即array的索引值)。這類函式在產生特定數列時挺好用的,例如用來產生等差數列或等比數列。兩個函式只差在後者是以平行處理的方式填滿array,速度較快(也較耗資源)。

Code List 1 - Use setAll(T[], IntFunction) to generate the arithmetic and geometric sequences
public static int[] generateArithmeticSequence(int initValue, int diff, int length) {
    int[] sequence = new int[length];
    Arrays.setAll(sequence, index -> {
        return index == 0? initValue : initValue + (index - 1) * diff;
    });
    return sequence;
}

public static int[] generateGeometricSequence(int initValue, int factor, int length) {
    int[] sequence = new int[length];
    Arrays.setAll(sequence, index -> {
        return (int)(initValue * Math.pow(factor, index));
    });
    return sequence;
}

parallelPrefix(T[], BinaryOperator<T>)可以用目前索引的前一個數值(binary operator的left值)和目前索引所指的值(binary operator的right值)計算出新的數值(有趣的是,Arrays沒提供非parallel的版本),回傳值會填入原陣列中,所以binary operator的left值都會是變更後的值。官方的例子假設元數列式[2, 1, 0, 3],然後BinaryOperator<T>做加法運算,則運算後的數列是[2, 3, 3, 6],6是根據陣列的第三個數(left值)加上第四個數(right值)取代原有的第四個數。

spliterator(T[] array)是用來切割陣列,我猜當呼叫parallelSort(T[], Comparator<T>)或是用stream(T[] array)取得stream物件後,再次呼叫parallel()時,內部會用`spliterator(T[])取得Spliterator物件管理陣列的切割,用來做平行處理。

Arrays的其他函式都介紹完了,該看今天的重點:parallelSort(T[], Comparator<T>)。在很早之前Arrays就有提供排序的函式,內部用的是merge sort演算法,使用時只需要提供比較任意兩物件順序的Comparator即可,這次新增的parallelSort(T[], Comparator<T>)就是平行處理的版本,所以我比較想知道平行處理版本所帶來的效能增益有多少?

這裡先如Code List 2宣告一個SortStrategy<T>的介面,然後在Code List 3及Code List 4中分別提供使用非平行處理的SimpleSortStrategy實作和使用平行處理的ParallelSortStrategy實作。接著Code List 5提供一個函式generateRandomValues(int)產生指定數量的亂數數列,

Code List 2 - The SortStrategy interface
package java8.arrays;

import java.util.Comparator;

public interface SortStrategy<T> {

    public void sort(T[] values, Comparator<T> comparator);
}
Code List 3 - The SimpleSortStrategy implementation
package java8.arrays;

import java.util.Arrays;
import java.util.Comparator;

public class SimpleSortStrategy<T> implements SortStrategy<T> {

    @Override
    public void sort(T[] values, Comparator<T> comparator) {
        Arrays.sort(values, comparator);
    }
}
Code List 4 - The ParallelSortStrategy implementation
package java8.arrays;

import java.util.Arrays;
import java.util.Comparator;

public class ParallelSortStrategy<T extends Comparable> implements SortStrategy<T> {

    @Override
    public void sort(T[] values, Comparator<T> comparator) {
        Arrays.parallelSort(values, comparator);
    }
}
Code List 5 - Random sequence generation
public static List<Integer> generateRandomValues(int size) {
    ArrayList<Integer> values = new ArrayList<Integer>();
    for(int index = 1; index <= size; index++) {
        values.add(index);
    }
    Collections.shuffle(values);
    return values;
}

事前準備完後就可以測試有沒有平行處理的差異了,Code List 6的程式可以透過參數決定陣列的最小數量,以及測試要跑幾次,每次都會將陣列的數量加倍,藉此觀察加速是否和數量有關,例如數量越多加速越多?由於比較的次數和交換的次數都會影響到時間,所以Code List 6先用generateRandomValues(int)產生一個亂數list,每種strategy執行前才轉為陣列(轉換不列入時間計算),確保每個strategy都是用到相同亂數順序的陣列。測試的環境和先前測試Lazy Evaluation & Parallel Stream相似,唯一的不同點是JVM從1.8.0-b132升級到1.8.0_05-b13。

Code List 6 - The experiment scenario
public static void main(String[] arguments) {
    int testRuns = 5;
    int startArraySize = 1000000;
    if(arguments.length == 2) {
        testRuns = Integer.parseInt(arguments[0]);
        startArraySize = Integer.parseInt(arguments[1]);
    }

    List<SortStrategy> strategies = new ArrayList<SortStrategy>();
    strategies.add(new SimpleSortStrategy());
    strategies.add(new ParallelSortStrategy());
    for(int testRun = 1, arraySize = startArraySize; testRun <= testRuns; testRun++, arraySize *= 2) {
        List<Integer> values = generateRandomValues(arraySize);
        for(SortStrategy strategy : strategies) {
            Integer[] array = values.toArray(new Integer[0]);
            long startTime = System.currentTimeMillis();
            strategy.sort(array, new IntegerComparator());
            long usedTime = System.currentTimeMillis() - startTime;
            System.out.println(strategy.getClass().getSimpleName() + " used " + usedTime + " ms to sort " + arraySize + " elements");
        }
    }
}

結果列於Table 1,測試的陣列大小從1百萬個整數起跳,跑了7個測試到64百萬個數字,但跑第七個測試(64百萬個數字)時會拋出OutOfMemoryError而失敗,因此Table 1只列到排序32百萬個數字的六筆比較數據。

Table 1 - The experiment result

Strategy 1 M 2 M 4 M 8 M 16 M 32 M
SimpleSortStrategy 539 760 1781 4120 8700 23016
ParallelSortStrategy 200 286 663 1515 3374 7724
2.70x 2.66x 2.69x 2.72x 2.58x 2.98x

從Table 1很明顯可以看到parallelSort(T[], Comparator<T>大概可以帶來2.5倍到接近3倍的效能增益(和數量無關)。所以,結論是當需要處理大量資料的排序時,真的可以考慮使用parallelSort(T[], Comparator<T>

← Quick Glance of Java 8 - Base64 Quick Glance of Java 8 - Parallel Array Sort →