當前的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,就想獲得效能提升,大概跟擲筊的意思沒兩樣!

作者簡介


Advertisement

更多 iThome相關內容