2020-09-20

為什麼不推薦用 Java Stream 改寫迴圈

1. Stream
2. Note
3. Reading List

Java 8 開始推出了 stream 介面，搭配 lambda 可以達到函數式編程 (functional language) 的能力，但是也造成非常多的效能爆炸的憾事。尤其是在我們沒有深入了解官方實作的細節時，請別輕易地轉換到 stream 介面。

Stream

在 Stream 出現之前，我們可以透過 Iterator 的實作來達到串流的概念，如 guava 庫所提供的 FluentIterable 就是一個替代方案。公司內部則是因為維護問題自己實作了一個自己的庫，因此沒辦法輕易地用 guava 的項目。但其中一點很明顯的不同在於 parallel 並行特性，即使是 FluentIterable 中，我也未見相關的平行操作。

在自己實作庫、人手不足的團隊配置下，直接吹捧去使用現有的函數庫，那麼問題就容易出現在於轉換上。必須考慮「何時我們該去使用」，決定好使用場景，再決定是否要改寫。公司已經升級到了 JDK 11 的，在銜接官方的 stream 實作時，依舊造成顯著的效能退化，甚至還有嚴重的運行問題，導致 dead lock 等問題。

Static Initialization Block

class classA {
    static {
        getXXX().parallelStream().forEach(e -> doSomething(e));
    }
}

在 JDK 11 中，可能會無知地不小心在 static initialization block 中觸發 parallel 特性，此時會造成程式無法運行、卡住。這個問題在於 threading 之間調度時的鎖，另一部分則是 lambda 抓取變數造成的。目前在 bug JDK-8143380 回報系統上看出無意解決此問題，因為這是人為撰寫的問題。如果是呼叫大量的函數來初始化參數，很容易遇到不知道哪個函數區塊內偷偷開了平行計算。

像同事都把 stream() 都改寫成 parallelStream()，不管問題是大是小，這樣改寫有時候就造成莫名其妙的 Bug 發生，造成找了半天才發現問題。如果覺得著官方提供的項目都有公信力，而且不會做很蠢的事情，一直都可以很聰明地在平行與不平行取捨的話，那其實也不用設計 parallelStream() 給我們使用，統一一個 stream() 接口就好。

想到同事如此狂妄的想法「工程師不該考慮資源，從摩爾定律來看，硬體明年就會解決，我們要做出更好的 scalability 的寫法」，讓我整個火氣都上來，無法接受 用而不知 的習慣。在沒人力挺下，只能眼真真地看著代碼被改得亂七八糟。

Stream Cost

了解 Stream 基礎實作後，就會明白在沒有平行的狀況下，維護 stage 的狀態會是額外開銷，相較於手刻的 Iterator，很多沒有必要的狀態紀錄容易在非常簡單的迭代器中暴露。

Stream Concatentation

串流串接又是更可怕的實作技術，請參閱附錄文章 Efficient multiple-stream concatenation in Java。

                                       concat(concat(concat(a, b), c), d)
                                      /                                 \
               concat(concat(a, b), c)                                   d
              /                      \
  concat(a, b)                        c
 /           \
a             b

串接的實作像是二元樹。如果操作順序不當，馬上會產生一棵偏斜的二元樹，假設我們要取 a 裏頭的元素，則必須從根一路走到葉節點去。如果構造 $n$ 次操作，且每一個恰好為一個元素，蒐集所有的內容，時間複雜度為 $O(n^2)$。

因此，亂改寫遞迴構造器很容易出現問題，不如用原本的回傳值 List/Collection 把要的東西收集好，不支援惰性操作也好，舊的寫法依舊在 $O(n)$ 完成。若要支援惰性操作，使用 StreamBuilder 建立平衡的二元樹也能在 $O(n \log n)$ 最慘複雜度下完成迭代。

這個問題並不是開 parallelStream() 解決，必須從根本的複雜度去分析，

Iterator to Stream

從內建的 Collection 到 Stream 大部分都由官方做得很好，用不著花太多的心思去思考如何實作，直接呼叫相關函數即可。如果工作需要自己的 Iterator 變成 Stream 就沒有這麼好運。必須了解什麼是 Spliterator，而 Spliterator 是怎麼實作的，會有什麼樣的介面，而它是從何支援 parallelStream 這一項特性。

假設您已經詳讀 Spliterators.java 下的所有代碼，如自動建造函數

1	static <T> Spliterator<T> spliteratorUnknownSize(Iterator<? extends T> iterator, int characteristics)

標示不確定迭代器實際運行的元素個數，好比在 stream 的 flatMap() 和 filter() 後，無法得知下一階段的元素多寡。在這些情況下只能透過這一類函數構造。然而官方預設的行為卻造成了嚴重的效能問題，它要求建造一個 IteratorSpliterator，而為了支援平行特性，平行通常需要透過高效的拆分陣列完成工作分配，因此會呼叫 Spliterator::trySplit 不斷地拆分，從源代碼中我們可以得知在未知大小的狀況下，則建立 new Object[1024] 預處理資料結構，即使在沒有開啟 parallelStream，依舊按照相同的運行流程。

有人說在 Java 開 new Object[1024] 很快，而最慘情況迭代器就只有一個元素，甚至沒有任何的狀況下，用最蠢的實作只消耗了一個迭代器的宣告開銷，而轉換串流卻消耗了整整數千個位元組，這是個效能損耗。就算 GC 很強，也不代表它能發現這麼複雜的操作，它整整跨足了超過一個函數區塊。

工作中因為繪製處理，需要運算數億次，若每一次都宣告這麼多餘的陣列，那麼莫虛有內存損耗高達幾十 GB，GC 若要運行 10 次，畫面繪製需要多一分鐘都是有可能的，將數秒不到的計算整整拖累下去。

Lazy Evaluation

惰性計算是 stream 的主要特性之一，從另一個術語按需計算 (on-demand)。即使是官方提供的庫也有一些小 Bug 造成假的惰性計算。最常見的像是 flatMap、map 和 filter 混用的時候，最後使用 findFirst 操作。從代碼上，我們會預期差不多就是找到一個元素之前的所有計算，而從回報系統裡面下關鍵字去找，會發現不少多餘的計算發生。

同事老是說「我們自己的庫超慢的，用 stream 比較快。」

言下之意，只是沒有遇到官方庫的 Bug，而你看到了庫的 Bug 卻從沒打算解決。

最常見的迭代器實作，忘了 Lazy Evaluation 的寫法如下：

class MyIterator<T> implements Iterator<T> {
    ...
    @Override
    public T next() {
        if (!hasNext())
            throw new NoSuchElementException();
        T val = nextVal;
        findNext(); // on-demand ?
        return val;
    }
    @Override
    public boolean hasNext() {...}
    private void findNext() {
        ... // time complexity ?
    }
}

很明顯地，透過 findNext() 我們可能只拿了第一個元素，在不需要第二個元素的狀況下，卻耗費了線性時間。

Note

還有一些問題，下一次再聊聊吧。

Morris' Blog