Date: Wed, 13 Sep 2000 23:07:59  JST
From: SHUDO Kazuyuki <shudoh at muraoka.info.waseda.ac.jp>
Subject: [JavaHouse-Brewers:36368] Tail recursion elimination (Re:
 =?ISO-2022-JP?B?GyRCJWolcyUvJWolOSVIJE4lNyVqJSIlaSUkJTokRxsoQg==?=
 EXCEPTION_STACK_OVERFLOW)
To: java-house-brewers at java-house.etl.go.jp (JavaHouse Brewers ML)
Message-Id: <20000913231149D.shudoh at muraoka.info.waseda.ac.jp>

首藤です。

> > 末尾再帰の最適化を実装しているインタプリタ、JIT は
> > 稀なんじゃないかと予想します。

風間さん wrote:

> たとえば，IBM System Journalの論文には，以下のような記述があります．

> The tail recursion
> elimination, a special case of tail call optimization, converts the
> method invocation into the branch to the beginning of the method

むむっ。この論文のこの部分、以前読みました。

「たいして効果ないだろうに…
  さすが IBM の JIT チーム、思い付くことはひと通りやってるな」
と思いました。

> このような最適化をおこなえる高性能な処理系も，
> すでに登場しつつあるのではないでしょうか?

というわけで、この、tail recursion elimination (末尾再帰の除去) を
shuJIT にも実装しました。実装してみたら…あら簡単。
static bind 可能なメソッド呼び出し(*) が末尾再帰だった場合、
呼び出しの代わりにメソッド先頭へのジャンプを行うようにしました。

(*) static, final, private メソッドの呼び出し。

IBM の JIT はおそらく、条件さえ揃えば virtual 呼び出しでも
ジャンプに変換してくれると思います。
(virtual 呼び出しの versioning をするから)


> もちろん，一口にJavaの処理系と言っても千差万別ですから，
> まだサポートしていない処理系も多いとは思いますが，

いくつかの Java 実行系をテストしました。
非常に深い再帰呼び出しを行って、StackOverflowError が発生した場合は、
末尾再帰の除去を行っていない、と判断しました。

以下、すべて Linux 用の実行系です。
JIT の名前しか書いてないものでは、
Blackdown JDK 1.2.2 FCS を使いました。

* StackOverflowError が発生したもの:
  →末尾再帰の除去を行わない。

  Sun JDK 1.3.0 RC1 Client VM
  Sun JDK 1.3.0 RC1 Server VM
  Inprise JBuilder JIT 1.2.15
  TYA 1.7v2
  OpenJIT 1.1.14

* StackOverflowError が発生しなかったもの:
  →おそらく、末尾再帰の除去を行う。

  IBM JDK 1.3.0
  IBM JDK 1.1.8
  sunwjit.so (JDK 1.2.2 付属)


> 同時に性能にも極端な差がつきつつあると思います．

まったくです。
ちょっともう、IBM や Sun と性能で勝負する気にはなれないです。

たとえば、K6-2 / 400 MHz, Linux での SPECjvm98 の結果はこうです。
それぞれに得手不得手はありますが、
総合スコアでは IBM と Sun の HotSpot VM の結果がとても良いです。

  IBM JDK 1.3		20.4
  HotSpot Server VM	18.4
  HotSpot Client VM	15.3
  OpenJIT 1.1.14	 7.18
  JBuilder JIT 1.2.15	 6.28
  shuJIT 0.6.6		 6.06
  TYA 1.7v2		 5.79
  インタプリタ		 2.19

Linpack benchmark だと、shuJIT も健闘しています。
Pentium II / 333 MHz で次の通りです。

  HotSpot Client VM	15.969
  shuJIT 0.6.6		13.733
  OpenJIT 1.1.13	13.464
  TYA 1.7v2		11.444
  JBuilder JIT 1.2.15	11.257
  OpenJIT 1.1.14	10.899
  IBM JDK 1.3		 5.675
  HotSpot Server VM	 3.503  (% java -server -Xbatch Linpack)
  インタプリタ		 2.393
  HotSpot Server VM	 2.297

IBM と HotSpot Server VM の結果が芳しくないのは、
プログラムの実行時間がとても短いために最適化が進む前に
実行が終わってしまうことが理由だと思います。


(参考)

  * Java JIT コンパイラ (IBM 東京基礎研)
    http://www.trl.ibm.co.jp/projects/jit/
  * Jalapeno 仮想マシン (IBM developerWorks の記事)
    http://www.jp.ibm.com/developerworks/java/jalape-vm-index-j.html (日本語)
    http://www-4.ibm.com/software/developer/library/jalapeno/        (英語)
  * OpenJIT: A Reflective JIT Compiler for Java
    http://www.openjit.org/
  * JBuilder JIT
    http://www.borland.com/jbuilder/linux/
  * Albrecht Cleine 氏 (TYA の作者) のページ
    http://sax.sax.de/~adlibit/
  * shuJIT
    http://www.shudo.net/jit/index-j.html

そういえば、ElectricalFire や Japhar の開発はどうなっているのだろう？

  * A Compiler for the Java Platform
    http://www.mozilla.org/projects/ef/
  * Japhar: A portable interpreter for Java bytecodes
    http://www.japhar.org/


SHUDO Kazuyuki/首藤一幸   私をたばねないで あらせいとうの花のように
  shudoh at muraoka.info.waseda.ac.jp