執行資料平行處理的效能考量

當前的JDK8的Stream程式庫，標榜著一件事：只要簡單地將stream方法，改為parallelStream，就可以獲得平行處理的可能性，增加處理效能。實際上，事情似乎並沒有那麼簡單，在將程式重構為運用Stream程式庫並改用parallelStream，效能沒有增加或不升反降的情況很多，這究竟是怎麼一回事？

平行任務的重要性

平行（Parallelism）與並行（Concurrency）不同，如果兩個任務分配到一個CPU核心，在取得的時間片段中交互執行，稱之為並行。如果有兩個核心，兩個任務各分配到其中之一同時執行，稱之為平行。現今開發者對於並行設計應不陌生，利用並行運算處理多個流程，讓客戶端以為任務「同時」執行，或者是某任務被阻斷（Block）之時，切換另一任務執行，避免等待而浪費CPU執行時間，用以提升整體任務執行效率。

過去十年多以來，處理器著重在多核心的發展，就連個人電腦、智慧型手機等，多核心處理器的搭載已經是基本配備，在提升整體任務執行效率這方面，越來越多開發者注意到，設法將任務分配至多個核心上平行執行，成為另一個可行途徑。只不過，程式上要直接進行平行設計並不容易，直接面對低階的平行處理程式庫，容易使得開發者陷入混亂之中，所幸，對於一些平行處理模式，近來越來越多高階程式庫可供使用，這使得開發者可以專心地在平行任務的表達上著墨，不用面對低階細節，JDK8的平行Stream處理，就是實際的例子。

然而，即使辛苦地將既有的程式重構為Stream API版本，而後改用了parallelStream，效率也不會提升。

根據計算機科學界的〈Amdahl's law〉經驗法則，如果任務中沒有任何能平行處理的分量，那麼擁有再多的核心，應用程式本身也不會獲得任何的效率提升；然而，如果能將序列處理中的一半改為平行處理，在不考慮投入的核心數下，效率就會增加為兩倍。因此，Stream API這類高階程式庫的目的，就是讓開發者有機會更專心地思考，循序任務如何能進一步地平行化，而這通常意謂著開發者得重新設計，或者從另一個角度來看待任務。

思考分而治之的處理過程

在我先前專欄〈從Thread到MapReduce〉中曾談過，平行化是不斷解開「做什麼」與「何時做」之間相依性的策略。以Stream API來說，它可處理的平行類型是資料平行（Data parallelism），也就是將全部可處理的資料畫分為各個小塊，再各自進行平行處理。最簡單的例子就是發現循序時是對每個元素進行相同處理，像是將歌曲清單改為歌曲長度清單，就非常適合改為平行處理，而根據條件過濾元素也是其中一個例子。

利用Stream API，將資料處理過程重構，是個令資料處理過程得以「接近」分而治之（Divide and conquer）可行性的方式，然而，並非可重構為Sttream API的程式，就可以輕易改為parallelStream獲得效能，如果沒事先思考分而治之的過程，非但無法獲得效能提升，反而還會造成結果錯誤。

例如，將數字清單乘在一起，最後再乘以5，寫為numbers.stream().reduce(5, (acc, x) -> x * acc)結果正確，但stream方法改呼叫parallelStream就會產生錯誤，因為在分而治之的各個過程，都會乘上一次5，若改用parallelStream要得到正確結果，必須寫為5 * numbers.parallelStream().reduce(1, (acc, x) -> x * acc)。

有些操作整體看來，沒辦法平行處理，然而換個角度思考，或許就能找出平行處理某些步驟的可能性，〈Java 8 Lambdas〉中舉了個計算簡單移動平均（Simple moving average）的例子，以n日的移動平均計算來看，似乎必須循序地每n日計算出一個平均，然而，亦可事先對陣列使用Arrays.parallelPrefix做平行累計加總，之後再循序地減去各元素前置項並除以n，根據〈Amdahl's law〉，由於部份循序分量改為平行分量，這也有助於效能提升的可能性。

反過來說，使用了Stream API的處理過程中，如果有些操作涉及了循序處理，像是forEachOrdered、sorted、limit之類的有序操作，其成本有可能蓋過先前平行處理時爭取來的效率，因而使得整體效率沒有提升。如果順序不重要時，可考量使用unordered方法去除順序，某些操作像是過濾重複元素（Distinct）或群組（Group），在無序的資料來源上會比較有效率。

思考額外的成本負擔

無論如何，程式實際是運行於電腦之上，因而平行處理時必須有電腦資源上的考量。最基本的，平行處理必須分而治之，在將資料切為子資料的過程中，會有切割、建立新物件、結合為最終結果等成本考量。因而在資料量不大的情況下，分割結合成本高過於平行處理得到的效益時，改為平行處理反而使得效率低落。雖然常見的籠統建議都聲稱，一切以評測（Benchmark）結果為主，這並沒有錯，只不過在這之前，是否有個依據可供參考？

對此，Doug Lea在〈Stream Parallel Guidance〉文件中，給了一些建議。面對S.parallelStream().operation(F)，如果N為S的元素數量，而Q為F處理每個元素的成本，可大略使用F中的操作或行數來計算，如果N*Q超過10000，才有平行化的價值。因此，如果操作簡單如x -> x + 1，那麼至少得有10000個以上的元素，才有平行化的價值，相對地，如果每個元素涉及大量運算，那麼就越有平行化的價值。

在Java上得考量一種處理成本：基本資料型態與對應的包裹器型態間的轉換。例如，int與Integer之間的Boxing與Unboxing操作。如果實際上List中都是數值且進行數學運算，考慮使用mapToInt轉為專屬於int的IntStream，而後再進行數學運算，可免去不必要的Boxing與Unboxing成本。就JDK8的Stream程式庫來說，也不建議對I/O做平行處理。在想要免於I/O、同步處理等待之類情況下，其他並行、非同步I/O程式庫或CompletableFuture，會是比較好的選擇。

資料來源的結構也是一個考量，先前談過，可思考將有序打為無序後，是否對平行處理有益，另一方面，因為平行處理必須分而治之，在這之前採取易於畫分的資料結構作為來源，對平行處理會有幫助，例如支援隨機存取的陣列、ArrayList或具有一定範圍的IntStream.range，平行處理時會比較有效率；而HashSet、TreeSet等，因為涉及雜湊空間與樹平衡等考量，會是其次之選；然而，像是LinkedList這類鏈結資料，走訪畫分資料的成本是O(N)，就不適合作為平行處理的來源結構，長度無法確定的資料來源，像是Streams.iterate、BufferedReader.lines等，也不建議採用。

程式庫僅提供專注思考平行的機會

一匹馬拉著一輛載滿貨物的車，與將貨物平分到數輛車分別由數匹馬拉相比，後者會快一點到達目的地，不過前提是須有馬來拉車。因而，在單核心處理器上，基本上不需要平行處理；多核心處理器如果各有其他任務要忙，實際上，也可能無暇處理應用程式的平行任務。

增加更多的核心也不一定有幫助，因為如果每個核心只處理一點點任務，就沒什麼太大效益，根據〈Amdahl's law〉，核心增加後能得到的效益，存在一個極限值，也就是再增加核心也沒有用，這個極值是受限於程式中循序處理的部份。

因此，最終開發者還是得思考，如何將循序設計改為平行設計，像JDK8的Stream API這類的程式庫，基本上只是讓開發者不用關心低階層次如何處理平行，而能有更多空間來思考或訓練自己進行平行設計，而有些效能考量其實是從循序處理時就得累積建立，像是前述資料結構、元素處理成本的考量，只是將stream改為parallelStream，就想獲得效能提升，大概跟擲筊的意思沒兩樣！