Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

Announcing Lv5 new RegisterVM

C++ ECMAScript JavaScript

lv5がRegisterVMになりました. これを持ってversion 0.0.2とします.
次の目標は, さらなるtuning, RegExp JIT, 部分的なES.next対応の開始です.

benchmark

RegisterVM

============================================
RESULTS (means and 95% confidence intervals)
--------------------------------------------
Total:             11453.9ms +/- 0.7%
--------------------------------------------

  v8:              11453.9ms +/- 0.7%
    crypto:         1085.9ms +/- 5.5%
    regexp:         1085.0ms +/- 0.5%
    earley-boyer:   1357.7ms +/- 0.8%
    splay:          1216.8ms +/- 3.6%
    deltablue:      2215.0ms +/- 0.6%
    raytrace:       1071.4ms +/- 1.8%
    richards:       3422.0ms +/- 0.5%

============================================
RESULTS (means and 95% confidence intervals)
--------------------------------------------
Total:                 1576.6ms +/- 0.7%
--------------------------------------------

  3d:                   154.2ms +/- 0.9%
    raytrace:            50.2ms +/- 0.7%
    cube:                45.1ms +/- 2.4%
    morph:               58.9ms +/- 0.7%

  date:                 265.7ms +/- 1.2%
    format-xparb:       136.3ms +/- 1.8%
    format-tofte:       129.4ms +/- 0.7%

  access:               216.7ms +/- 0.9%
    nbody:               53.0ms +/- 1.4%
    fannkuch:            66.4ms +/- 0.9%
    nsieve:              54.7ms +/- 1.2%
    binary-trees:        42.5ms +/- 1.0%

  regexp:                89.8ms +/- 1.1%
    dna:                 89.8ms +/- 1.1%

  controlflow:           15.7ms +/- 0.9%
    recursive:           15.7ms +/- 0.9%

  string:               527.2ms +/- 1.6%
    fasta:              157.9ms +/- 2.2%
    base64:              59.9ms +/- 2.7%
    unpack-code:        128.9ms +/- 3.8%
    tagcloud:            98.0ms +/- 0.6%
    validate-input:      82.6ms +/- 1.7%

  crypto:                67.7ms +/- 0.7%
    sha1:                16.5ms +/- 1.4%
    md5:                 16.0ms +/- 1.2%
    aes:                 35.2ms +/- 0.9%

  math:                 104.6ms +/- 0.7%
    cordic:              46.4ms +/- 0.9%
    partial-sums:        38.5ms +/- 0.8%
    spectral-norm:       19.8ms +/- 0.9%

  bitops:               134.9ms +/- 0.8%
    bits-in-byte:        24.9ms +/- 1.5%
    3bit-bits-in-byte:   14.5ms +/- 5.1%
    nsieve-bits:         24.3ms +/- 0.9%
    bitwise-and:         71.3ms +/- 0.6%

StackVM

============================================
RESULTS (means and 95% confidence intervals)
--------------------------------------------
Total:             11760.1ms +/- 0.8%
--------------------------------------------

  v8:              11760.1ms +/- 0.8%
    splay:          1158.8ms +/- 0.9%
    regexp:         1098.0ms +/- 1.4%
    raytrace:       1118.1ms +/- 0.6%
    richards:       3475.2ms +/- 0.6%
    crypto:         1387.5ms +/- 6.6%
    deltablue:      2148.9ms +/- 1.4%
    earley-boyer:   1373.7ms +/- 0.6%

============================================
RESULTS (means and 95% confidence intervals)
--------------------------------------------
Total:                 1641.6ms +/- 0.6%
--------------------------------------------

  access:               251.5ms +/- 1.3%
    nbody:               60.5ms +/- 0.9%
    fannkuch:            87.6ms +/- 2.8%
    nsieve:              62.2ms +/- 1.9%
    binary-trees:        41.1ms +/- 0.6%

  math:                 113.7ms +/- 2.0%
    cordic:              52.4ms +/- 4.0%
    partial-sums:        40.3ms +/- 1.1%
    spectral-norm:       20.9ms +/- 5.0%

  date:                 255.9ms +/- 0.7%
    format-xparb:       136.4ms +/- 1.1%
    format-tofte:       119.6ms +/- 0.7%

  regexp:                88.6ms +/- 0.4%
    dna:                 88.6ms +/- 0.4%

  bitops:               143.5ms +/- 0.8%
    bits-in-byte:        29.1ms +/- 1.7%
    3bit-bits-in-byte:   15.9ms +/- 4.4%
    nsieve-bits:         28.3ms +/- 0.8%
    bitwise-and:         70.2ms +/- 0.6%

  controlflow:           13.4ms +/- 1.4%
    recursive:           13.4ms +/- 1.4%

  string:               530.6ms +/- 1.5%
    fasta:              159.4ms +/- 3.5%
    base64:              60.3ms +/- 1.4%
    unpack-code:        127.2ms +/- 2.0%
    tagcloud:           100.1ms +/- 1.0%
    validate-input:      83.6ms +/- 1.1%

  3d:                   170.6ms +/- 0.7%
    raytrace:            55.2ms +/- 1.2%
    cube:                55.4ms +/- 1.9%
    morph:               60.0ms +/- 0.8%

  crypto:                73.8ms +/- 1.0%
    sha1:                17.7ms +/- 1.3%
    md5:                 16.4ms +/- 2.0%
    aes:                 39.7ms +/- 1.3%

高速化しました!

intro

StackVMがあったとして, そのbytecodeは通るpathごとにstackの深さが違うということがあり得るでしょうか? つまり,

if (cond) {
  ...何らかのpath
}
v = 1 + 2;  // ここでpushしてpushしてbinary addするstackの深さ

で1 + 2の部分でstackにpushしてーってやる場所がthen pathを通っているかいないかによって変わるかという話です. 通常考えればそんなことはありえません. ということは, 現在のframeから見て, 1 + 2は結局常に同じstackのoffsetに向かってpushしているはずなのです.

つまり,

v = 1 + 2;
1はstack[0]にpush. 完了後 sp = 1
2はstack[1]にpush. 完了後 sp = 2
stack[0]に1 + 2. 完了後 sp = 1

というのは常に同じなのであれば, そもそもstack pointerをincrementしたりdecrementしたりせずに

loadI r0, 1
loadI r1, 2
add r0, r0, r1

って書いてるのと同じです. ということで, stackの深さをそのままregisterに割り当てることで, RegisterVM bytecodeを作ることができます. registerは無限長です.

optimization

しかし, 上のbytecodeでは無駄があります. ここであるlocal変数(stack上に存在)iを考えるとき,

v = i + 20;

はstack VMでは,

pushLocal i  // local変数iがstackにpush
pushI 20
binaryAdd
...

となりますが, これをそのままRegister VM bytecodeに置き直すと, (iがr0に入っているとして)

move r1, r0  // push_localの処理を愚直にr1へのcopyとして
loadI r2, 20
add r3, r1, r2

となります. ここで, moveは明らかに無駄です. 本来的には

loadI r1, 20
add r2, r0, r1

となってしかるべきです. という訳で, 対象の変数がregister上に構築されているとき, そのままregisterを使う事ができ, copy costが削減されます.

RHS

しかし, 上のoptimizationについては気をつける必要があります. というのも, StackVMの場合はstack上に値をcopy, いわば評価していたわけですが, RegisterVMは評価していないからです. このままでは以下のような場合, (iはr0にあるとして)

i = 10;
v = i + (i = 20);
loadI r0, 10  // i = 10
              // ここでStackVMはcopyすることで評価しているが, 省いてしまっている.
loadI r0, 20  // i = 20の代入処理が...
add r1, r0, r0  // あれ?

というわけで, 10 + 20のはずが, 20 + 20になってしまいます.

これの解決法は, ある評価結果を使うまでの間に別のexprを評価する場合, そのexprが代入を含んでいればmoveしておけばいいです.

loadI r0, 10  // i = 10
move r1, r0   // RHSに代入があるので
loadI r0, 20
add r2, r1, r0

という訳で安心です. 最適化passなしで何とかしようとしたらこんな形でしょうか. 別にpass通せば, tmpのままのを後で置き換えできるのですが, なんとか1 passだとこのような形...? (from 『コンパイラ』 p396)

未評価

この間ゆるゆり2期に敬意を表してハーゲンダッツのラムレーズンを買いに行ったところ, ふと頭に浮かんだやり方があって,

上記のr0を, 「未評価だけど後で使うlist」に入れておいて, 書きこみ処理を行う命令をemitした時にそのlistを検索, dst対象と同じ物があれば, 退避させればいいのではないかと考えました. つまり,

loadI r0, 10  // i = 10
              // ここでStackVMはcopyすることで評価しているが, 省いてしまっている.
              // r0は未評価だけど後で使うlistに入っている.

              // で, loadI r0, 20をemitしようとする. この時r0はlistに入っている
move r1, r0   // すかさずmoveを挿入. listからr0をremoveしつつ, 使う値をr1に変更
loadI r0, 20
add r2, r1, r0  // 安心

という方法を考えたのですが, 大丈夫なのでしょうか? 問題がなさそうなら, この実装に変えようかなと考えています.

補足

なにぶん稚拙なので, より良いやり方がある場合は教えていただければありがたいです...