提高Java代碼的性能

2019-11-18 15:15:53

字體：大中小

供稿：網(wǎng)友

　　診斷 java 代碼：提高 Java 代碼的性能

尾遞歸轉(zhuǎn)換能加快應(yīng)用程序的速度，但不是所有的 JVM 都會做這種轉(zhuǎn)換
Eric E. Allen (eallen@cyc.com)
Java 開發(fā)帶頭人，Cycorp，Inc.

很多算法用尾遞歸方法表示會顯得格外簡明。編譯器會自動把這種方法轉(zhuǎn)換成循環(huán)，以提高程序的性能。但在 Java 語言規(guī)范中，并沒有要求一定要作這種轉(zhuǎn)換，因此，并不是所有的 Java 虛擬機（JVM）都會做這種轉(zhuǎn)換。這就意味著在 Java 語言中采用尾遞歸表示可能導(dǎo)致巨大的內(nèi)存占用，而這并不是我們期望的結(jié)果。Eric Allen 在本文中闡述了動態(tài)編譯將會保持語言的語義，而靜態(tài)編譯則通常不會。他說明了為什么這是一個重要問題，并提供了一段代碼來幫助判定您的即時（JIT）編譯器是否會在保持語言語義的同時做尾遞歸代碼轉(zhuǎn)換。
尾遞歸及其轉(zhuǎn)換
相當(dāng)多的程序包含有循環(huán)，這些循環(huán)運行的時間占了程序總運行時間的很大一部分。這些循環(huán)經(jīng)常要反復(fù)更新不止一個變量，而每個變量的更新又經(jīng)常依靠于其它變量的值。

快速跟蹤代碼
清單 1. 把 Integer 集的 Iterator 中的元素相乘的失敗嘗試
這個程序中有一個錯誤，并在運行時拋出了一個異常 ? 這個異常提供了一條有價值的線索。
清單 2. 試圖捕捉不正確的調(diào)用
Example2 類中覆蓋的方法 PRodUCtHelp 努力捕捉對 productHelp 的不正確調(diào)用，但卻引入了一個新的錯誤。

清單 3. 動態(tài)編譯比靜態(tài)編譯更好地保持了語言的語義
假如您用兩個不同的靜態(tài)編譯器編譯這段代碼，其中一個結(jié)果代碼將拋出一個異常，而另一個則不會。真讓人莫名其妙。

清單 4. 您的 JIT 會在保持語言語義的同時轉(zhuǎn)換尾遞歸代碼嗎？
一個告訴您如何判定您的 JIT 是否會做這種轉(zhuǎn)換的樣本。

清單 5. 一個動態(tài)轉(zhuǎn)換
這段代碼演示了名義上完善的編譯器將會做怎樣的轉(zhuǎn)換

假如把迭代看成是尾遞歸函數(shù)，那么，就可以把這些變量看成是函數(shù)的參數(shù)。簡單提醒一下：假如一個調(diào)用的返回值被作為調(diào)用函數(shù)的值立即返回，那么，這個遞歸調(diào)用就是尾遞歸；尾遞歸不必記住調(diào)用時調(diào)用函數(shù)的上下文。

由于這一特點，在尾遞歸函數(shù)和循環(huán)之間有一個很好的對應(yīng)關(guān)系：可以簡單地把每個遞歸調(diào)用看作是一個循環(huán)的多次迭代。但因為所有可變的參數(shù)值都一次傳給了遞歸調(diào)用，所以比起循環(huán)來，在尾遞歸中可以更輕易地得到更新值。而且，難以使用的 break 語句也經(jīng)常為函數(shù)的簡單返回所替代。

但在 Java 編程中，用這種方式表示迭代將導(dǎo)致效率低下，因為大量的遞歸調(diào)用有導(dǎo)致堆棧溢出的危險。

解決方案比較簡單：因為尾遞歸函數(shù)實際上只是編寫循環(huán)的一種更簡單的方式，所以就讓編譯器把它們自動轉(zhuǎn)換成循環(huán)形式。這樣您就同時利用了這兩種形式的優(yōu)點。

但是，盡管大家都熟知如何把一個尾遞歸函數(shù)自動轉(zhuǎn)換成一個簡單循環(huán)，Java 規(guī)范卻不要求做這種轉(zhuǎn)換。不作這種要求的原因大概是：通常在面向?qū)ο蟮恼Z言中，這種轉(zhuǎn)換不能靜態(tài)地進行。相反地，這種從尾遞歸函數(shù)到簡單循環(huán)的轉(zhuǎn)換必須由 JIT 編譯器動態(tài)地進行。

要理解為什么會是這樣，考慮下面一個失敗的嘗試：在 Integers 集上，把 Iterator 中的元素相乘。

因為下面的程序中有一個錯誤，所以在運行時會拋出一個異常。但是，就象在本專欄以前的許多文章中已經(jīng)論證的那樣，一個程序拋出的精確異常（跟很棒的錯誤類型標(biāo)識符一樣）對于找到錯誤藏在程序的什么地方并沒有什么幫助，我們也不想編譯器以這種方式改變程序，以使編譯的結(jié)果代碼拋出一個不同的異常。

清單 1. 一個把 Integer 集的 Iterator 中的元素相乘的失敗嘗試
import java.util.Iterator;

public class Example {

public int product(Iterator i) {
return productHelp(i, 0);
}

int productHelp(Iterator i, int accumulator) {
if (i.hasNext()) {
return productHelp(i, accumulator * ((Integer)i.next()).intValue());
}
else {
return accumulator;
}
}
}

注重 product 方法中的錯誤。product 方法通過把 accumulator 賦值為 0 調(diào)用 productHelp。它的值應(yīng)為 1。否則，在類 Example 的任何實例上調(diào)用 product 都將產(chǎn)生 0 值，不管 Iterator 是什么值。

假設(shè)這個錯誤終于被改正了，但同時，類 Example 的一個子類也被創(chuàng)建了，如清單 2 所示：

清單 2. 試圖捕捉象清單 1 這樣的不正確的調(diào)用

import java.util.*;

class Example {

public int product(Iterator i) {
return productHelp(i, 1);
}

int productHelp(Iterator i, int accumulator) {
if (i.hasNext()) {
return productHelp(i, accumulator * ((Integer)i.next()).intValue());
}
else {
return accumulator;
}
}
}

// And, in a separate file:

import java.util.*;

public class Example2 extends Example {
int productHelp(Iterator i, int accumulator) {
if (accumulator < 1) {
throw new RuntimeException("accumulator to productHelp must be >= 1");
}
else {
return super.productHelp(i, accumulator);
}
}

public static void main(String[] args) {
LinkedList l = new LinkedList();
l.add(new Integer(0));
new Example2().product(l.listIterator());
}
}

類 Example2 中的被覆蓋的 productHelp 方法試圖通過當(dāng) accumulator 小于“1”時拋出運行時異常來捕捉對 productHelp 的不正確調(diào)用。不幸的是，這樣做將引入一個新的錯誤。假如 Iterator 含有任何 0 值的實例，都將使 productHelp 在自身的遞歸調(diào)用上崩潰。

現(xiàn)在請注重，在類 Example2 的 main 方法中，創(chuàng)建了 Example2 的一個實例并調(diào)用了它的 product 方法。由于傳給這個方法的 Iterator 包含一個 0，因此程序?qū)⒈罎ⅰ?

然而，您可以看到類 Example 的 productHelp 是嚴(yán)格尾遞歸的。假設(shè)一個靜態(tài)編譯器想把這個方法的正文轉(zhuǎn)換成一個循環(huán)，如清單 3 所示：

清單 3. 靜態(tài)編譯不會優(yōu)化尾調(diào)用的一個示例
int productHelp(Iterator i, int accumulator) {
while (i.hasNext()) {
accumulator *= ((Integer)i.next()).intValue();
}
return accumulator;
}

于是，最初對 productHelp 的調(diào)用，結(jié)果成了對超類的方法的調(diào)用。超方法將通過簡單地在 iterator 上循環(huán)來計算其結(jié)果。不會拋出任何異常。

用兩個不同的靜態(tài)編譯器來編譯這段代碼，結(jié)果是一個會拋出異常，而另一個則不會，想想這是多么讓人感到困惑。

您的 JIT 會做這種轉(zhuǎn)換嗎？
因此，如清單 3 中的示例所示，我們不能期望靜態(tài)編譯器會在保持語言語義的同時對 Java 代碼執(zhí)行尾遞歸轉(zhuǎn)換。相反地，我們必須依靠 JIT 進行的動態(tài)編譯。JIT 會不會做這種轉(zhuǎn)換是取決于 JVM。

要判定您的 JIT 會否轉(zhuǎn)換尾遞歸的一個辦法是編譯并運行如下小測試類：

清單 4. 判定您的 JIT 能否轉(zhuǎn)換尾遞歸
public class TailRecursionTest {

private static int loop(int i) {
return loop(i);
}

public static void main(String[] args) {
loop(0);
}
}

我們來考慮一下這個類的 loop 方法。這個方法只是盡可能長時間地對自身作遞歸調(diào)用。因為它永遠不會返回，也不會以任何方式影響任何外部變量，因此如清單 5 所示替換其代碼正文將保留程序的語義。

清單 5. 一個動態(tài)轉(zhuǎn)換

public class TailRecursionTest {

private static int loop(int i) {
while (true) {
}
}

public static void main(String[] args) {
loop(0);
}
}

而且，事實上這也就是足夠完善的編譯器所做的轉(zhuǎn)換。

假如您的 JIT 編譯器把尾遞歸調(diào)用轉(zhuǎn)換成迭代，這個程序?qū)o限期地運行下去。它所需的內(nèi)存很小，而且不會隨時間增加。

另一方面，假如 JIT 不做這種轉(zhuǎn)換，程序?qū)芸旌谋M堆棧空間并報告一個堆棧溢出錯誤。

我在兩個 Java SDK 上運行這個程序，結(jié)果令人驚奇。在 SUN 公司的 Hotspot JVM（版本 1.3 ）上運行時，發(fā)現(xiàn) Hotspot 不執(zhí)行這種轉(zhuǎn)換。缺省設(shè)置下，在我的機器上運行時，不到一秒鐘堆棧空間就被耗盡了。

另一方面，程序在 IBM 的 JVM（版本 1.3 ）上咕嚕嚕運行時卻沒有任何問題，這表明 IBM 的 JVM 以這種方式轉(zhuǎn)換代碼。

總結(jié)
記住：我們不能寄希望于我們的代碼會總是運行在會轉(zhuǎn)換尾遞歸調(diào)用的 JVM 上。因此，為了保證您的程序在所有 JVM 上都有適當(dāng)?shù)男阅埽鷳?yīng)始終努力把那些最自然地符合尾遞歸模式的代碼按迭代風(fēng)格編寫。

但是請注重：就象我們的示例所演示的那樣，以這種方式轉(zhuǎn)換代碼時很輕易引入錯誤，不論是由人工還是由軟件來完成這種轉(zhuǎn)換。

參考資料

參與本專欄的討論論壇。

欲了解 Hotspot 的更多信息，請參閱 SUN 的有關(guān)文檔。

試試 IBM developer kit for Java version 1.3。我想您會對它的性能感到滿足的。

欲具體了解尾遞歸及其到迭代的轉(zhuǎn)換，請參閱 CMU Common Lisp User′s Manual（CMU Common Lisp 用戶手冊）。雖然這本手冊是（當(dāng)然是）為 Common Lisp 寫的，但其中關(guān)于尾遞歸的討論也適用于其他語言，包括 Java 語言。

對提高您 Java 代碼的性能有愛好？在二月底于紐約召開的國際 Java 開發(fā)大會上，性能專家 Peter Haggar 在他的音頻演示中討論了這個問題的本質(zhì)。

閱讀 Eric 關(guān)于診斷 Java 代碼的完整系列。

關(guān)于作者
Eric Allen 在 Cornell 大學(xué)獲得了計算機科學(xué)及數(shù)學(xué)的學(xué)士學(xué)位。他目前是 Cycorp，Inc 的主要 Java 軟件開發(fā)人員帶頭人，編程部的副經(jīng)理，還是位于 JavaWorld 的 Java 初學(xué)者論壇的主持人。他還是 Rice 大學(xué)編程語言小組的兼職研究生。他的研究涉及在源程序和字節(jié)碼層次上的正規(guī)語義模型和 Java 語言擴展的開發(fā)。目前，他正在為 NextGen 編程語言實現(xiàn)一種從源代碼到字節(jié)碼的編譯器，這也是 Java 語言的泛型運行時類型的一種擴展。可通過 eallen@cyc.com 與 Eric 聯(lián)系。

上一篇：通過---JAVA程序--打開文本！

下一篇：探索Application Server的世界