Gauche:VMの最適化:JIT:予備実験

Gauche:VMの最適化:JIT:予備実験

2008/09/18 08:04:01 PDT: Google v8が速い とかいう 話もあるし、時代はJITなのかなあと思って、果たしてGaucheでどのくらいJITが効くのか、 もしくはJITを効かせるために必要な変更があるとしたら何かを調べてみた。 現時点でのソースはexperiment_jitブランチにcommitしてある。

注意:

ベンチマーク

環境: Core2 Quad 2.4GHz / 4GB DDR2 memory / Ubuntu 8.04 (Linux scherzo 2.6.24-19-generic #1 SMP)

fib(39) を計算。

ケース 時間(s)
Gauche rev6383 JITなし 13.51
Gauche rev6383 JITあり 6.22
Gauche rev6383 JITあり w/leaf-env 6.09
Google v8 rev153 3.42

(leaf-envというのは、JITされる手続きが(1)内部でクロージャを作らない (2)内部で環境を積まない、という条件の時に可能になる最適化を有効にしたもの。 本来、jitルーチンでそういう手続きを判別して最適化を切り替えるべきだが、 今は外部からパラメータで切り替えている)

Schemeのソース 

(define (fib n) (if (< n 2) 1 (+ (fib (- n 2)) (fib (- n 1)))))

JITなし版の実行 

gosh> (time (fib 39))

JITあり版の実行 

gosh> (use gauche.vm.jit)
#<undef>
gosh> (define (fib n) (if (< n 2) 1 (+ (fib (- n 2)) (fib (- n 1)))))
fib
gosh> fib
#<closure fib>
gosh> (define fib (jit fib))    ;; jit compile
...
gosh> fib                       ;; subrになる
#<subr (jit-compiled fib)>
gosh> (time (fib 39))
...

JITあり版(leaf-env)の実行 

gosh> (use gauche.vm.jit)
gosh> (define (fib n) (if (< n 2) 1 (+ (fib (- n 2)) (fib (- n 1)))))
gosh> (args-regs 1)             ;; jit実行前にパラメータ設定
gosh> (leaf-env? #t)            ;; ditto
gosh> (define fib (jit fib))
gosh> (time (fib 39))

JavaScript版 

function fib(n) { if (n<2) return 1; else return fib(n-2)+fib(n-1); }
function timefib(n) {var start=new Date(); var r =fib(n); var end=new Date(); print (end-start); return r;}

Scheme版、VM instruction 

gosh> (disasm fib)
main_code (name=fib, code=0xa63dc0, size=19, const=2, stack=11):
args: #f
     0 CONSTI(2) 
     1 LREF-VAL0-BNLT(0,0) 5    ; (< n 2)
     3 CONSTI(1) 
     4 RET 
     5 PRE-CALL(1) 11
     7 LREF0                    ; n
     8 NUMADDI(-2)              ; (- n 2)
     9 PUSH-GREF-CALL(1) #<gloc user##fib>; (fib (- n 2))
    11 PUSH-PRE-CALL(1) 17
    13 LREF0                    ; n
    14 NUMADDI(-1)              ; (- n 1)
    15 PUSH-GREF-CALL(1) #<gloc user##fib>; (fib (- n 1))
    17 NUMADD2                  ; (+ (fib (- n 2)) (fib (- n 1)))
    18 RET

Scheme版、JIT出力。callをトランポリンで行うので、 手続きはVMインストラクションの0-10, 11-16,17-18の3つに分断される。 label_** がVMインストラクションのアドレスに相当。 

>>>
  (push %rbp)
  (push %r10)
  (movq %rdi %rax)
  (movq (%rsi) %rbp)
  (movq (464 %rbp) %r10)
  (push %r15)
  (movq (8 %rsi) %r15)
  label_17
  (movq %rax %rsi)
  (movq (-8 %r10) %rdi)
  (andq 3 %rax)
  (subq 8 %r10)
  (cmpq 1 %rax)
  (jne G67)
  (movq %rdi %rax)
  (andq 3 %rax)
  (cmpq 1 %rax)
  (jne G67)
  (subq 1 %rsi)
  (addq %rsi %rdi)
  (movq %rdi %rax)
  (jno G68)
  (rcr 1 %rdi)
  (sar 1 %rdi)
  (movq 140468411950080 %rax)
  (call %rax)
  (jmp G68)
  G67
  (movq 140468411966160 %rax)
  (call %rax)
  G68
  label_18
  (pop %r15)
  (pop %r10)
  (pop %rbp)
  (ret)
code = 0x78fc40
>>>
  (push %rbp)
  (push %r10)
  (movq %rdi %rax)
  (movq (%rsi) %rbp)
  (movq (464 %rbp) %r10)
  (push %r15)
  (movq (8 %rsi) %r15)
  label_11
  (movq %rax (%r10))
  (addq 8 %r10)
  (movq (264 %rbp) %rdi)
  (movq 7928896 %rax)
  (movq 0 (8 %r10))
  (movq %rdi (%r10))
  (movq (240 %rbp) %rdi)
  (movq 0 (16 %r10))
  (movq 2 (24 %r10))
  (movq %rdi (40 %r10))
  (movq %rax (32 %r10))
  (movq %rbp (48 %r10))
  (movq %r15 (56 %r10))
  (movq %r10 (264 %rbp))
  (addq 64 %r10)
  (movq %r10 (464 %rbp))
  (movq %r10 (272 %rbp))
  label_13
  (movq %r15 %rax)
  label_14
  (movq %rax %rdi)
  (andq 3 %rax)
  (cmpq 1 %rax)
  (jne G69)
  (addq -4 %rdi)
  (movq %rdi %rax)
  (jno G70)
  (rcr 1 %rdi)
  (sar 1 %rdi)
  (movq 140468411950080 %rax)
  (call %rax)
  (jmp G70)
  G69
  (movq -3 %rsi)
  (movq 140468411966160 %rax)
  (call %rax)
  G70
  label_15
  (movq %rax (%r10))
  (addq 8 %r10)
  (movq 10057408 %rcx)
  (movq (24 %rcx) %rax)
  (cmpq 86 %rax)
  (jne G72)
  (movq G73 %rdi)
  (movq (8 %rcx) %rsi)
  (movq 140468411761264 %rax)
  (call %rax)
  (jmp G72)
  G73
  (datas unbound variable: %S)
  G72
  (movq %rax %rcx)
  (andq 3 %rcx)
  (jnz G71)
  (movq (%rax) %r8)
  (movq 140468414776515 %r9)
  (cmpq %r8 %r9)
  (jne G71)
  (movzbq (17 %rax) %r8)
  (shr 3 %r8)
  (andq 7 %r8)
  (jnz G71)
  (movzwq (16 %rax) %r8)
  (andq 1023 %r8)
  (cmpq 1 %r8)
  (jne G71)
  (movq (56 %rax) %rdx)
  (movq 1 %rsi)
  (addq -8 %r10)
  (movq %r10 %rdi)
  (movq %r10 (464 %rbp))
  (pop %r15)
  (pop %r10)
  (pop %rbp)
  (jmp (48 %rax))
  G71
  (addq -8 %r10)
  (movq %rax %rdi)
  (movq (%r10) %rsi)
  (movq %r10 (464 %rbp))
  (movq 140468411676240 %rax)
  (pop %r15)
  (pop %r10)
  (pop %rbp)
  (jmp %rax)
code = 0x955a80
>>>
  (push %rbp)
  (push %r10)
  (push %r15)
  (movq %rdx %rbp)
  (movq (464 %rbp) %r10)
  (movq (%rdi) %r15)
  label_0
  (movq 9 %rax)
  label_1
  (movq %rax %r8)
  (movq %r15 %rax)
  (movq %rax %r9)
  (andq 3 %rax)
  (jz G63)
  (cmpq 1 %rax)
  (jne G64)
  (movq %r8 %rax)
  (andq 3 %rax)
  (cmpq 1 %rax)
  (jne G64)
  (cmpq %r8 %r9)
  (movq 6 %rax)
  (jnl label_5)
  (jmp G65)
  G63
  (movq (%r9) %rcx)
  (movq 140468414778179 %rdx)
  (cmpq %rdx %rcx)
  (jne G64)
  (movq %r8 %rax)
  (andq 3 %rax)
  (jnz G64)
  (movq (%r8) %rcx)
  (cmpq %rdx %rcx)
  (jne G64)
  G64
  (movq %r9 %rdi)
  (movq %r8 %rsi)
  (movq 140468411959664 %rax)
  (call %rax)
  (cmpq 0 %rax)
  (movq 6 %rax)
  (jge label_5)
  G65
  (movq 22 %rax)
  label_3
  (movq 5 %rax)
  label_4
  (pop %r15)
  (pop %r10)
  (pop %rbp)
  (ret)
  label_5
  (movq (264 %rbp) %rdi)
  (movq 9788032 %rax)
  (movq 0 (8 %r10))
  (movq %rdi (%r10))
  (movq (240 %rbp) %rdi)
  (movq 0 (16 %r10))
  (movq 2 (24 %r10))
  (movq %rdi (40 %r10))
  (movq %rax (32 %r10))
  (movq %rbp (48 %r10))
  (movq %r15 (56 %r10))
  (movq %r10 (264 %rbp))
  (addq 64 %r10)
  (movq %r10 (464 %rbp))
  (movq %r10 (272 %rbp))
  label_7
  (movq %r15 %rax)
  label_8
  (movq %rax %rdi)
  (andq 3 %rax)
  (cmpq 1 %rax)
  (jne G74)
  (addq -8 %rdi)
  (movq %rdi %rax)
  (jno G75)
  (rcr 1 %rdi)
  (sar 1 %rdi)
  (movq 140468411950080 %rax)
  (call %rax)
  (jmp G75)
  G74
  (movq -7 %rsi)
  (movq 140468411966160 %rax)
  (call %rax)
  G75
  label_9
  (movq %rax (%r10))
  (addq 8 %r10)
  (movq 10057408 %rcx)
  (movq (24 %rcx) %rax)
  (cmpq 86 %rax)
  (jne G77)
  (movq G78 %rdi)
  (movq (8 %rcx) %rsi)
  (movq 140468411761264 %rax)
  (call %rax)
  (jmp G77)
  G78
  (datas unbound variable: %S)
  G77
  (movq %rax %rcx)
  (andq 3 %rcx)
  (jnz G76)
  (movq (%rax) %r8)
  (movq 140468414776515 %r9)
  (cmpq %r8 %r9)
  (jne G76)
  (movzbq (17 %rax) %r8)
  (shr 3 %r8)
  (andq 7 %r8)
  (jnz G76)
  (movzwq (16 %rax) %r8)
  (andq 1023 %r8)
  (cmpq 1 %r8)
  (jne G76)
  (movq (56 %rax) %rdx)
  (movq 1 %rsi)
  (addq -8 %r10)
  (movq %r10 %rdi)
  (movq %r10 (464 %rbp))
  (pop %r15)
  (pop %r10)
  (pop %rbp)
  (jmp (48 %rax))
  G76
  (addq -8 %r10)
  (movq %rax %rdi)
  (movq (%r10) %rsi)
  (movq %r10 (464 %rbp))
  (movq 140468411676240 %rax)
  (pop %r15)
  (pop %r10)
  (pop %rbp)
  (jmp %rax)
code = 0xa07c00

検討

最初は

という感じで実装してみたんだけど、ベンチマークを取ったら JIT無しよりも遅かった。 つまり現時点のVMで、 インストラクションを実行時に見てディスパッチしている部分というのは オーバヘッドになってないってことだ。

そのあとごちゃごちゃいじってとりあえず倍くらいの速さまで到達。 やったこと：

v8はi386インストラクションを出してるハンデがあることを考えると、 対抗するにはここからさらに倍以上速くしないとだめだなあ。

今はjit版は単なるSUBRになって、non-jitなコードと共存できるように なってるけど、VMの状態をコンパチに保つオーバヘッドがある (vm->spなどの管理)。 多分今のVMを持ったままにする限り、劇的な速度向上はない。 で、倍の速度にしかならないっていうのは、開発やメンテの手間と天秤にかけると 割が合わない。

本格的にjitに移行するなら現在のScmVMは忘れて、CPUレジスタやスタックに べったりの構造にしないとだめだろう。JIT無しに対して5倍-10倍になるなら 考えても良いかもしれない。

もっとも、fibはGCもランタイムCルーチンの呼び出しもほとんど発生しない というマイクロベンチマークであって、そこで10倍の差がついたとしても 現実のプログラムではおそらくせいぜい2-3倍ってとこだと思う。

ちくちくプロファイリングしてみたんだが、一番足を引っ張ってるのは、 VM stackでcontinuationを実現するために、C functionはすべて トランポリンで呼び出す必要があるところ (Scm_VMPushCC, jit-pre-call)。 というのはトランポリンで呼び出されるC continuationは間接callに なるため、分岐予測が効きにくいのだ。oprofileでみるとC continuation の冒頭でひっかかってるのがわかる。

ChickenみたいにCPUスタックにcontinuation frameを積んで、 間にC frameが挟まってpop出来ないやつはstack overflow handlerで 回収するとかそっちの方向にいかないとだめかも。

今はほとんどアセンブリセグメントをつなげてるだけだけど、 もう少し大きな目で見ればレジスタの使い方とかスケジューリング の工夫で多少の改善は見込める。パイプラインストールが集中して 発生してるのが、GREFでgloc->valueを読み出してunboundか どうかをチェックしてるところなんだが、gloc->valueの読み出しを 速めに持ってくることでレイテンシを隠蔽できる可能性はある。

とりあえずの結論：

って感じかなあ。

コメントとか

Post a comment

Name:

Last modified : 2012/02/02 12:01:24 UTC