about 2 years ago

Translated from "For Faster Java Collections, Make Them Lazy" by Mike Duigou, Java Magazine March/April 2016, page 28-33. Copyright Oracle Corporation.

延遲,讓Java容器更快

如何透過對ArrayList與HashMap加入延遲操作以增進效率與減少記憶體使用量

Java 核心函式庫的社群已經努力透過延遲的方式改善 Java Collections Framework,在軟體中,延遲性是一種架構性或系統性的方式,延後產生結果,一直等到結果是真正確定被需要的時候。許多運算可以被拆解成大量的副運算,延遲性延緩副運算的執行直到其他副運算或整個運算需要那些副運算的結果。

以非延遲性方式完成一個運算是執行整個一連串副運算然後結合其結果產生最終的結果,更有效率的延遲方式是一開始就結合副運算的結果,當您發現需要一個結果,但因為其副運算還未執行而不存在時,您才執行該副運算取得部分的結果,剛開始,您從沒有任何已完成的結果開始,不斷地累積副運算完成的結果,讓額外的副運算完成,最終完成整個運算的結果。如果您有個運算的結果,其中若干個副運算因為它們對於決定最終結果而言是不需要的,其結果從未計算,延遲性就能成功節省時間。

任何時間,一個運算的結果有潛在性或可能對最終結果而言是不需要的,延遲該運算到其結果是真正有需要的時候是有意義的。延遲性的常見例子是表示式的計算,細想下列程式:

int x = 5;
int y = 3;
if (x < 2 && y < 7) {
    ...

計算這表示式最簡單的方式是計算每一個子句然後結合其結果:

5 < 2 => FALSE
3 < 7 => TRUE
FALSE && TRUE => FALSE

注意到,如果第一個子句的結果是 false,則整個表示式的結果永遠會是 false,因此我們不需要煩惱第二個子句的計算直到第一個子句的結果是 true,對 Java 程式來說,Java Language Specification 規定表示式的子句從左到右依序計算,如果任何子句對其結果是不需要的,就不會被計算,這通常會節省計算,通常也是很有用:

if (foo != null && foo.bar() == 3) {

在這例子中,要呼叫 bar() 函式的前提是 foo 是非空值,如果 foo 是空值,企圖計算表示式的第二個子句會導致拋出 NullPointerException,Java 的延遲運算規則確保第二個子句只在第一個子句的結果是 true 才執行,邏輯的 AND (&&) 運算可以視作與巢狀等效,因此

if (foo && bar && baz) {

和下面是等效的

if (foo)
    if (bar)
        if (baz)

這重寫的巢狀條件是同樣讓它更清楚為什麼某些不需要的子句不用計算,延遲運算同樣適用在邏輯的 OR (||) 運算上,例如:

if (true || something) {

這條件表示式中的 something 子句永遠不會被計算,因為表示式的結果可以在它被計算前直接決定。

表示式延遲運算的例子在寫有效率的,或者可能更重要的是簡潔的程式是很有用的,其他形式的延遲性一樣有助益,但程式的流程決策與能得到的助益之間的關聯不是那麼直接或立即。

如果一個計算的結果是偶而或時常被捨棄不被使用,那直到它是必要前,避免使用其需要的資源去計算它是很有意義的,最明顯能被節省的資源是 CPU 週期,但延遲性能同樣避免配置記憶體以節省記憶體,或是避免使用非必要的檔案、sockets、執行緒、資料庫連線等以節省系統資源,根據情境,這些節省的資源可以是很龐大的。

實作延遲性可以是一個改善系統效能的關鍵最佳化策略,透過避免非必要的工作來提升效能,而不是改善執行該工作的效率,延遲性類似減少應用程式對資料庫的查詢次數能改善 30% 效能,與之對比,在相同程式中,改善資料庫查詢效能只能改善 3% [譯注:這應該是在查詢本身寫的就不錯的前提下才成立]。如果可行,將您的時間花在前者,會比較有效果。

在少數的應用程式中,我發現延遲性在記憶體使用量提供至少 20% 的節省量及減少小量的記憶體重整次數。

延遲性容器的挑戰

在已大幅最佳化的 Java Collections Framework 中,實作延遲性成為分析程式行為後的結果,Oracle Performance Scalability and Reliability (PSR) 團隊分析某些 Oracle 框架與在些框架上執行的應用程式,PSR 團隊發現應用程式與中介軟體都常配置 ArrayListHashMap,但擁有該容器的物件,在整個生命週期中,卻不曾使用過它們,大約 2% 的 ArrayListHashMap 不曾接收到任何元素,更進一步分析發現,容器不是總是被使用,只有某些情況下使用,PSR團隊完成某些工作想了解:是否能重構這些應用程式,在一個共同的基礎類別下,用不同類別處理容器被使用與不被使用的情境,將容器只會部分被使用的情況定義在一個子類別中,這方式並不是那麼容易實現,因為很多情況類似下列的例子:

public abstract class RestRequest {

    protected final Map<String, String> httpHeaders = new HashMap<>();
    protected final Map<String, List<String>> httpParams = new HashMap<>();
    protected final Set<Cookie> httpCookies = new HashSet<>();

RestRequest 是個虛構的範例類別,在應用程式中用來處理HTTP REST查詢,REST是透過HTTP通訊建立API的一種常用方式,在這例子中,每個 RestRequest 物件是一種特殊格式化的 HTTP 請求,代表一個到主機應用程式提供的 REST API 呼叫,RestRequest 實體需呈現接收到的 HTTP 訊息中重要的部分,包含 HTTP 標頭 (httpHeaders)、來自查詢字串或表單資料的 HTTP 參數 (httpParams) 及 HTTP Cookies (httpCookies),這些類型 HTTP 特性可能呈現在一個 HTTP 訊息中,但確切的使用則由每個應用程式的 REST API 與使用 REST API 的客戶端決定。

因為對任一個請求而言,HTTP 特性的使用是不確定的,包含 RestRequest 中針對任一個潛在特性的資料結構都是不確定的,HTTP 標頭、參數及 cookies 都是常見且是 HTTP 協定需要的部份,但應用程式並沒有被強迫使用全部的特性,甚至可能全都不用,有些 REST API 可能使用 HTTP 參數,而其他可能使用 cookies 或標頭,一個可能應付選擇性需求的方式是提供多種 RestRequest 類別的變形,表達 HTTP 特性所有可能被使用的組合,然後,這將會是擾人且不方便使用。即使確定某種特定的請求會使用某個特定 HTTP 特性,通常這特性只在少部分的請求中被使用,像是相同的請求,已認證的使用者可能使用 cookies,但未認證的使用者則未必使用,可能大多數的請求來自未認證的使用者。

讓程式邏輯較簡單的方式是有一個 RestRequest 類別且有 httpParams 欄位,總是初始化並可以使用,不論是否被使用 (待會會回到這點)。

由於框架或應用程式無法重構以消除這不可缺少但不經常使用 [譯註:我個人原文中的 in 位置錯了,若照翻,不可缺少但經常使用,語意上怪怪的] 的 httpParamshttpCookies 欄位,因此需要替代方案。

整體的目標是除非需要不然避免在類別中持有像 httpParams 這種欄位的成本以改善應用程式的效能,一種方案是在 RestRequest 中延遲 httpParams 欄位的初始化,即只有在需要時才建立 HahspMap,這將在所有要用到 httpParams 的地方需要額外的保護檢查:

if( httpParams != null )

但因為 RestRequest 的設計是可以被繼承的,所有繼承 RestRequest 的子類別在使用 httpParams 時,將需有類似的檢查,因為有許多既有的程式沒有這些檢查,讓 RestRequest 突然停止欄位的初始化是不合理的。

允許 httpParams 有時候可以是空值,多出來的保護檢查可能會造成程式的邏輯變複雜,若在 RestRequest 的其他欄位使用同樣的方法,RestRequet 的函式與子類別將過度或重複地檢查 RestRequest哪些特性有被使用,隨著時間,不可避免地,錯誤會在忘記檢查 RestRequest 的其他部分時偷偷溜進來,忘記一個對可能是空值的檢查可能耗費您一整天!

有一個解法,通常很有用,但不適合在這個案例中,維持 httpParams 的宣告不變

protected final Map<String, List<String>> httpParams;

但將初始化移到建構子中,在建構子中,如果可以判斷請求沒有使用 HTTP 參數,則可以將 httpParams 欄位初始化為 Collections.emptyMap(),不用為每個請求單獨建立一個 HashMap 實體 (在 Collections 工具類別中,使用像 Collections.emptyMap() 和其他 emptyList()emptySet() 相似的輔助函式,以提供空容器來說是一個效率高的方式,這些空容器常用來取代建立一個獨立實體但沒有內容的情況,它們常會比回傳一個空值要好,因為不是回傳空值,對空值得檢查就可以被消除。)

在首次進行於框架與應用程式中透過避免建立 HashMapArrayList 實體的方式加入延遲性後,很清楚的,最有效率的方式是在 Java Collection Framework 本身的內部實作延遲性。

Java 8 同樣新引入一個顯著的延遲性實作:Streams API,這函式庫將延遲性作為核心原則。

更新 Java Collections

對 Java 基礎類別例如 ArrayListHashMap 進行修改是一件很嚴肅的事情,有眾多的程式員及無數程式碼使用這些類別,不論版本,程式員與程式都預期 Java 會提供可靠、一致的行為和效能,Java Collections Framework 是與開發員和與程式承諾提供特定行為的合約,實質上,不可能在更新或新的釋出版本中,以改變合約的方式改善 JDK 類別的功能,對 API 合約進行小的微調是可能的,但大多數能讓 Java Colletions Framework 改善都是內部改變,即使是內部改變,也必須小心考慮以確保這些改變不會造成副作用與非預期的行為改變。

稍早,我提到像 RestRequest 這樣有些欄位可能是空的類別難以使用,可能是空的 public 或 proected 欄位,使用它們之前需額外空座,任何試圖讀取欄位都要一個檢查,確認欄位不是空的,在允許空值的程式中,沒有一致性地檢查空值是常見的錯誤,一般會建議不允許 protected 或 public 欄位是空值,當欄位是 private,處理可能是空值的情況是較能控制的,因為所有指向此欄位的參考都在同一個檔案中,且較容易理解在不同的物件狀態下可能的值。

ArrayListHashMap 都使用 package private 陣列欄位作為核心的資料結構儲放元素或項目,除了 ArrayListHashMap 物件本身,這陣列是 ArrayList 唯一配置的記憶體,對空的或接近空的 HashMaps 來說,這陣列是最大的記憶體配置,以延遲性更新這兩個類別的重點是增加檢查陣列欄位可能是空值。

延遲性加到 ArrayListHashMap 中最主要的助益是它延後或可能避免配置陣列的記憶體,直到有第一個元素加到容器中,為背後的陣列配置記憶體在某些應用程式中成本是很高的,對其他應用程式來說,特別是未使用的容器本身是短生命週期的,甚至不知道記憶體已被配置,其助益就是節省初始化所需的計算。

由於欄位指向一個陣列,JVM 在索取某個位置的元素或取得陣列長度時就已經要檢查陣列是否為空值,增加的保護檢查是暗地檢查空值的明確版本,這意味著,增加這保護檢查不會對效能造成損失。

第二個要考慮的是額外的保護檢查與不同方式的配置邏輯,可能改變 HotSopt 如何內嵌函式或更重要的是不內嵌函式,這可能暗中損害效能,內嵌是 HotSopt 為小函式最佳化的一種方法,當 HotSopt 編譯一段呼叫一個短的函式或是小函式的程式碼時,它常會以該函式的實際內容取代函式的呼叫,HotSpot 有個大小上限決定是否要內嵌,試驗發現,我們在關鍵的函式加入延遲性並未接近內嵌上限,且在幾個地方重複使用既有的內部函式,可以改善 HotSpot 內嵌的效果,仍有少數非關鍵的函式,在加入延遲性後有稍微變慢,不過,在一般的評測與效能測試中,這變動產生效能的淨成長,到目前為止,我還沒發現任何案例在加入延遲性後,產生明顯不預期的副作用。

結論

在評估一個 JVM 應用程式的記憶體使用量時,除了總使用量外,還需要考慮到更多面向,因為 JVM 使用垃圾回收機制管理記憶體,您還必須考慮記憶體的配置率與垃圾回收的壓力,記憶體配置率指的是應用程式配置的新物件數量與配置的記憶體大小之間的比例,應用程式在記憶體配置率上變化很大,且它是影響生產量的一個關鍵因素,和配置率相關的是垃圾回收機制花在未使用的物件上的消耗,垃圾回收的壓力指的是您需要犧牲多少生產力,用在垃圾回收機制上,確保應用程式總是有足夠的空閒記憶體空間,一般來說,大幅降低配置率同時能減少必要的記憶體回收數量。

在一般框架的應用程式中,將 ArrayListHashMap 改成延遲初始化能產生大約 1% 到 2% 的記憶體使用量與配置率,幾乎沒有可量測的效能增益,同樣重要的,沒有應用程式增加記憶體使用量或降低效能,在少數的應用程式中,我發現延遲性在記憶體使用量提供至少 20% 的節省量及減少小量的記憶體重整次數,對某些應用程式來說,這是明顯的助益,同時對大多數的應用程式來說,能提高少許的助益,且沒有已知因延遲性改善所造成的負面影響。

再次思考 RestRequest 範例,用延遲性改變 ArrayListHashMap 的使用會改變行為與效能嗎?RestRequestArrayListHashMap 欄位仍然是非條件是初始化的 final 實體,這意味著 RestRequest 的使用方式未改變,程式不需要為欄位可能是空值而加檢查,實際上,即使,我們仍希望越多的容器實體可以是延遲初始化,這會延後建立元素陣列,以節省記憶體與 CPU 週期。

在任何以改善超過 20 年以上的軟體系統,像是 Java,這很難找到任何實作上的改變能單方面對任何情況造成助益,仔細思量這變化,我能確定一般對 ArrayListHashMap 的使用沒負面影響,在關鍵函式像 HashMap.get() 效能分析通常測試其 Java bytecode 與 CPU 週期的消耗,這些函式每年在數百萬的 JVM 中被執行數百萬兆次,有些微小的效能消耗變動,將消耗從一個執行路徑移到另一個較晚的路徑上,是可以被接受的,但任何效能的下降可能是不可接受的,可能需要從其他更大的效能增益來補償。

問題的分析從觀察應用程式與框架的行為開始,希望有某個方式能減少未使用容器的消耗,這種從上而下的效能分析,到目前為止,是改善應用程式效能最好的方式。

延遲性的其他可能已經考慮用在 Java Collections Framework,最期待發生的改變會是 HashMap 如何建立與改變其容器的大小,HashMap 典型的使用模式建議其實作在較少元素的情況下 (及在有較多元素的容器中第一次呼叫 get() 時) 使用不同的資料結構能會來帶助益。

有 Java 函式庫有其他使用延遲性的例子,最常見的是在 hashCode 函式中快取雜湊值計算的結果,這為 String 與其他類別帶來明顯的效能助益,其他快取的案例同樣被加入,有些快取避免重複的計算以改善效能,有些則是多次運算產生相同資料結構作為結果以節省記憶體,額外的快取與其他延遲的初始化,只有被證實是有幫助的就會被加到後續的 Java 更新中,同樣,當快取是浪費的或是為維護快取造成額外的消耗則會被移除,大多數的情況,因為它們不會改變 API,加到 Java 函式庫的延遲性改善可以帶來助益且沒有不好的影響。

Java 8 同樣新引入一個顯著的延遲性實作:Streams API,這函式庫將延遲性作為核心原則,且頻繁地較宣告式方式提供更好的效能。

延遲性是一個重要的最佳化方式,並已經為 Java 函式庫帶來顯著的助益,如果您需要為一個正在使用的函式庫改善效能,當其他主要的最佳化方式像是改善演算法,已經被使用過了,您應該考慮它。

Learn More
How laziness affects the sizes of an ArrayList allocation

譯者的告白
這次標題的翻譯,我換了好幾個版本,最一開始是:懶,讓 Java Collection 更快,但總覺得沒有抓到原文的重點,後來是用反義詞讓整個意思更清楚 (或是說故意造成反差)。

突然跳到 March/April 雙月刊是因這篇文章讓我想起,先前在幫公司的產品進行最佳化時,就是用延遲性改善效能,在我那台舊舊的開發機上,讓 App 的冷啟動時間從 10~12 秒改善到 5~6 秒,不過這方法其實需要很多設計想法上的改變,若一開始沒考慮到,之後修改的成本或是可能造成的副作用 (如文章中所說的空值檢查或是 API 變動) 就需要考慮進去,雖然說有個說法是 premature optimization is the root of all evil,但如果 Performance 是架構設計時列為重要的 factor 時 (不一定總是總要的),即使不立即實作,設計時也要想著最佳化這件事。

← 用 GitHub 與其他服務進行軟體生命專案管理 《激發員工潛力的薩提爾教練模式:學會了,你的部屬就會自己找答案!》書摘 →