Digamma - Tracing JIT Compiler for Ypsilon

Scheme Inside Ypsilon Inside Digamma

ネイティブコード生成についていろいろと考えていましたが、Tracing JITと呼ばれるものを試してみることにしました。

Tracing JITでポイントとなるのはインタープリタとコンパイル済みのコードの切り替えに起因するオーバヘッドかと思います。またYpsilonではConcurrent GCの性能を落としてはいけないという制約がありますのでなかなか難しいです。

でも、面白いことにConcurrent GCとTraicing JITが上手くかみ合うとネイティブコンパイラの性能を越えるケースも出てくるようです。

まず、Ikarusより速くなるという特別なケースを紹介しましょう。

(define map-1
  (lambda (proc lst)
    (if (null? lst)
        '()
        (cons (proc (car lst))
              (map-1 proc (cdr lst))))))

(define minus (lambda (x) (- x)))
(define lst (make-list 1000000 1))
(define sink #f)
(time (set! sink (map-1 minus lst)))

結果は・・・

Linux ubuntu-core2 2.6.27-11-generic #1 SMP Thu Jan 29 19:24:39 UTC 2009 i686 GNU/Linux
   
Ikarus
  5 collections
  269 ms elapsed cpu time, including 168 ms collecting
  273 ms elapsed real time, including 168 ms collecting
  20558328 bytes allocated

Ypsilon 0.9.6-trunk/r417
  0.303697 real    0.536033 user    0.000000 sys

Ypsilon 0.9.6-trunk/r417 + Digamma(Tracing JIT)
  0.211938 real    0.416026 user    0.000000 sys (*1)

これはmap-1だけをコンパイルしてminusはインタープリタで実行した場合の結果です。minusが1000000回ほど実行されることを考えれば、何かを間違えていると思えるような結果ですね :D（念のため繰り返しますが、これはあくまで特別なケースですよ！）

map-1のASTは
http://codepad.org/DJjuXVd6
Digammaで生成したコードはこんな感じです（ライブラリ部分は省略しています）
http://codepad.org/kWQQ7u2z

map-1ではメモリアロケーションとGCの影響が大きいので、こんどはfor-each-1を使ってコンパイル済みコードの特性を見てみることにします。

(define for-each-1
  (lambda (proc lst)
    (if (null? lst)
        (unspecified)
        (begin
          (proc (car lst))
          (for-each-1 proc (cdr lst))))))

(define lst (make-list 1000000 1))
(time (for-each-1 - lst)) ; *Ikarusでは(define unspecified void)が必要

結果は・・・

Linux ubuntu-core2 2.6.27-11-generic #1 SMP Thu Jan 29 19:24:39 UTC 2009 i686 GNU/Linux

Ikarus
  no collections
  24 ms elapsed cpu time, including 0 ms collecting
  23 ms elapsed real time, including 0 ms collecting
  0 bytes allocated

Ypsilon 0.9.6-trunk/r417
  0.075264 real    0.076004 user    0.000000 sys

Ypsilon 0.9.6-trunk/r417 + Digamma(Tracing JIT)
  0.037176 real    0.040003 user    0.000000 sys

さすがに、これでIkarusに勝とうというのは甘いですね :p
でもなかなかいい仕事しています :)

for-each-1のASTは
http://codepad.org/FZMo8jOV
生成されるコードは正しく末尾再帰なものになります。
http://codepad.org/5nu6nNNh
ちなみに、Digammaのプロトタイプは500行ほどのSchemeのプログラムなので、コードの品質はまだそれなりです :p
最後にコンパイルしたmap-1とfor-each-1がcall/cc対応になっているかどうかの確認です。

> (define cont #f)
> (define foo
    (lambda (n)
      (if (= n 222)
          (call/cc (lambda (k) (set! cont k) (- n)))
          (- n))))
> (map-1 foo '(111 222 333))
(-111 -222 -333)
> (cont 'ok?)
(-111 ok? -333)

> (define foo
    (lambda (n)
      (if (= n 222) (call/cc (lambda (k) (set! cont k))))
      (display n)
      (newline)))
> (for-each-1 foo '(111 222 333))
111
222
333
> (cont)
222
333
>

大丈夫なようです ^^b

さて、この記事だけを見ると明日にでもリリースできそうに見えるかと思いますが・・・
実は現在のDigammaはインタープリタをコンパイルしたGCCのバージョンに強く依存しています。この依存を無くしてDigammaを実用化するにはインタープリタの実行コードを自動生成する仕組みが必要だと思っています。ですが、これに関して良いアイディアがまだ出ません orz。まあアセンブラで書いちゃうという最終手段はあるんですけどね :(

ちなみにDigammaの名前はFujitaのFが由来です :D
http://en.wikipedia.org/wiki/Digamma