2013年3月19日 星期二

Java 的 method call 要付出多少代價?

原文網址:http://plumbr.eu/blog/how-expensive-is-a-method-call-in-java

我們都遇到過這種場景: 看著設計不良的 code,聽著寫出這 code 的人辯稱:「你不能為了設計犧牲效能啊!」 而你就是無法說服那個人放棄那有 500 行的 method, 理由是一連串的呼叫有可能降低效能。

嗯... 在 1996 年的時候可能是真的吧? 但是後來 JVM 已經進化成為一個神奇的軟體了。 要發現 JVM 有多神奇的方法之一是鑽進 VM 了解更多最佳化的原理。 應用在 JVM 的技術是相當廣泛的, 不過讓我們看看其中一個技術「inline method」的細節。 用下面這個例子來解說最容易了:

int sum(int a, int b, int c, int d) {
    return sum(sum(a, b),sum(c, d));
}

int sum(int a, int b) {
    return a + b; 
}

執行這段程式碼時,JVM 會判斷是否可以將它替換成更有效的方式, 像是 inlined

int sum(int a, int b, int c, int d) {
    return a + b + c + d;
}

請注意,這個最佳化是 VM 在做的,不是 compiler。 第一時間可能很難明白為甚麼會這樣? 畢竟就上頭的例子,你會疑惑: 為甚麼在 compile 階段暫緩最佳化可以產生更有效率的 bytecocde 呢? 但是考慮其他沒有那麼明顯的案例,JVM 還是實作最佳化的首選:

  • JVM 除了有 static 的分析資料,也有執行期的資料。 在執行期,JVM 可以根據哪些 method 最常執行、 哪些載入動作是多餘的、什麼時候用 copy propagation 是安全的...... 來做出更好的決策。

  • JVM 可以得到底層架構的資訊, 像是 CPU 是幾核心、heap size、設定檔, 然後根據這些資訊來做出最佳選擇。

讓我們透過實際例子來理解這些假設。我弄了一個小型測試程式, 用幾種不同的方法加總 1024 個整數。

  • 用一個 array 裝 1024 個整數,然後用迴圈取得加總結果。 這是一個相對來講合理的實作方式。 實作的檔案是 InlineSummarizer.java

  • 用遞迴的方式作 divide and conquer: 我把原來的 1024個 element 用遞迴的方法分成兩半, 第一層遞迴得到兩個長度為 512 的 array、 第二層遞迴得到四個長度為 256 的 array...... 以此類推。 為了計算 1024 個整數的總和,我製造出 1023 個額外的 method 呼叫。 實作的檔案是 RecursiveSummarizer.java

  • 幼稚的 divide and conquer 方式: 雖然也是對 array 作分割,不過是透過額外的實際 method 來作切半的動作。 所以我呼叫 sum512()sum256()sum128()、......、sum2()` 直到我計算完所有的 element。 跟遞迴的方法一樣,我製造出 1023 個額外的 method 呼叫。 實作的檔案是 IterativeSummarizer.java

然後我用一個 test class 來執行這些程式。 第一個結果是沒有最佳化過的程式碼:

first diagram

我們可以看到 inline 是最快的,額外產生 1023 個 method 的方法慢了約 25000ns。 但是解讀這張圖時要記得:這是 JIT 還沒有對程式碼作徹底最佳化的結果。 在 2010 年間,我用我的 MB Pro 根據各個實作方式的不同, 做了 200 到 3000 次的測試。

更實際的結果如下:我把所有加總的實作方式執行超過 1000000 次, 然後排除 JIT 沒有運作的部份,來展現它魔法:

second diagram

我們可以看到即使 inline 還是表現比較好, 但是 iterative 的方式也展現了不錯的速度。 但是 recursive 就有顯著的差異,當 iterative 的方法僅有 20% 的 overhead, RecursiveSummarizer 花了 inline 方法所需時間的 3.4 倍。 顯然我們必須知道:當你使用遞迴時,JVM 無法提供協助、也不能使用 inline method call。 所以當你使用遞迴時,請注意這個限制。

撇開遞迴不談,method 的 overhead 是幾乎不存在的。 在 1023 個額外的 method 呼叫卻只有差 205ns。 不要忘了測量單位是 ns(10^-9 秒)。 因此,感謝 JIT,我們可以放心地忽略大多數 method 呼叫所產生的 overhead。

當你的同事又再用「call stack 的 pop 沒有效率」這種藉口 來掩飾他的骯髒程式碼,讓他先去上一下 JIT 速成班吧! 如果你想整備齊全以防堵同事的荒謬理由,請訂閱我們的 RSSTwitter, 我們很高興提供你更多案例研究。

1 則留言: