Java 8 初探 - Parallel Array Sort

此為過去的舊文，2014 年 5 月 18 日初次發表於 logdown。

最近比較懶一點，所以今天還是只看一個小東西。比較 Arrays 這個工具類別在 J2SE 7 和 J2SE 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[]) 在Java 8 初探 - Stream已經介紹過了，這裡只是把一個陣列包裝成 stream 來使用。

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

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>) 就是平行處理的版本，所以我比較想知道平行處理版本所帶來的效能增益有多少？

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

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

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

Table 1 - The experiment result

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