Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

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

サイボウズ・ラボユースの最終成果報告会にて発表しました

Dialy

3/26に発表してきました. 資料は以下にあります.

iv / lv5, ECMA262 Engine

内容は主に, ECMA262 5.1th Engine, lv5の独自性である仕様準拠性, Register VM概説, またrailgun::Compilerの独自のRegisterの割り当て方による効率的なRegister Allocation(個人的には, ゆるゆりメソッドと呼んでいます), Stack VM / Register VMの論争点の一つであるcode sizeについての考察などです.

時間があれば, JavaScriptの変数の解析, 及び参照の解析などについても話したかったのですが, それをやるとスライド数が爆発するのでやめています...(direct call to eval, with, argumentsがあるとどうなるかとか, immutable bindingとの兼ね合いだとか, strict mode下でできる最適化だとか, argumentsという変数が隠された場合にはargumentsを作る必要がなくなることが静的解析可能な場合があるとか...)

参加して

サイボウズ・ラボユースに1年間参加させていただきました.

書籍, LuaPython, JSCやRubyなど様々なsource codeを読んでVMの仕組みなどを勉強したり, 論文を読んだり, 非常に有意義な時間を過ごすことが出来ました.

それにより, Engineも当初のECMA262のInterpretation Algorithmを実行するAST Interpreterから, Stack VM, そしてRegister VMを構築するなど, VMの基礎的なことや, VM levelでの最適化のやり方, Bytecode Compilerについての知識など, 非常に勉強になりました.
また, JavaScript Engineには必ず必要になってきつつある, Polymorphic Inline Cacheの実装などの知識を得ることが出来ました.

また, 新屋さん, 林さんら, 同期の方々のすごさに圧倒され, 非常に刺激的でした!

サイボウズ・ラボのみなさまには, 非常に多くのアドバイスを頂き, とても感謝しております.
asmなどについて非常に基礎的な知識も持っていなかったのですが, x86/x64についてや, Xbyakについてメモリ自動伸長optionをつけていただくなど, 様々な点でアドバイスを頂き, とてもためになりました.
また, ECMA262についても, 様々なことを教えていただきました.

謝辞

この1年間, 参加して非常に有意義な時間を過ごすことが出来ました. 本当にありがとうございました!

サイボウズ・ラボユース 最終成果報告会

Blog

が, 3/26にあります.
サイボウズ・ラボユース学生支援制度: 3/26(月)第1期サイボウズ・ラボユース最終成果報告会&第2期募集説明会を開催します

自分は主にRegisterVMの話をしていると思います.
特に, 副作用を含んだexpressionにおける適切なRegisterの割り当て方について話しているかと...
ので, ご興味ある方は是非お越しくださいー.

■ 第1期サイボウズ・ラボユース 最終成果報告会

 開催日時:2012年 3/26(月) 13:00〜17:00
 開催場所:秋葉原ダイビル5階(カンファレンスフロア)
 参加人数:70名
 事前申込:必要(無料)申し込みフォーム→ http://bit.ly/ArZrGm

【タイムテーブル】

 13:00 開場(受付)
 13:15 サイボウズ・ラボユース第1期生5名による成果発表
  (1) 桐井祐樹「Ruby・Raccを使用した言語処理系の日本語プログラミング化」
  (2) 新屋良磨「世界最速の正規表現JITエンジンの実装」@sinya8282
  (3) 林 拓人「型システムの拡張と型推論
  (4) 鈴木勇介「世界で一番仕様に忠実なJavaScript処理系の作成」
  (5) 粟本真一「現役高校生の考えるクラウドOSの設計と実装」
 15:30 ライトニングトーク大会
 16:00 サイボウズ・ラボユース第2期生の募集について
 16:30 卒業式
 16:50 自由解散
 17:00 懇親会(希望者のみ別の会場に移動して開催予定)
 19:30 解散

iv / js ES.next, update for February 27, 2012 Draft

ECMAScript JavaScript

iv / js ES.next parser (my original ES.next parser, see this entry) is updated to follow February 27, 2012 Draft

ArrayComprehension

ArrayComprehension is supported.

[ v * v for (v of [1, 2, 3])];

to

[
  {
    "type": "ExpressionStatement",
    "expr": {
      "type": "ArrayComprehension",
      "expression": {
        "type": "BinaryExpression",
        "op": "*",
        "left": {
          "type": "Identifier",
          "value": "v"
        },
        "right": {
          "type": "Identifier",
          "value": "v"
        }
      },
      "comprehensions": [
        {
          "type": "ComprehensionBlock",
          "left": {
            "type": "ExpressionStatement",
            "expr": {
              "type": "Identifier",
              "value": "v"
            }
          },
          "right": {
            "type": "Array",
            "sealed": false,
            "items": [
              {
                "type": "Number",
                "value": "1"
              },
              {
                "type": "Number",
                "value": "2"
              },
              {
                "type": "Number",
                "value": "3"
              }
            ]
          }
        }
      ],
      "filter": null
    }
  }
]

and

[ v * v for (v of []) if (true)];

to

[
  {
    "type": "ExpressionStatement",
    "expr": {
      "type": "ArrayComprehension",
      "expression": {
        "type": "BinaryExpression",
        "op": "*",
        "left": {
          "type": "Identifier",
          "value": "v"
        },
        "right": {
          "type": "Identifier",
          "value": "v"
        }
      },
      "comprehensions": [
        {
          "type": "ComprehensionBlock",
          "left": {
            "type": "ExpressionStatement",
            "expr": {
              "type": "Identifier",
              "value": "v"
            }
          },
          "right": {
            "type": "Array",
            "sealed": false,
            "items": []
          }
        }
      ],
      "filter": {
        "type": "True"
      }
    }
  }
]

for-of Statement

for-of Statement is supported.

for (var i of []) print(i);

to

[
  {
    "type": "ForOfStatement",
    "init": {
      "type": "VariableStatement",
      "body": [
        {
          "type": "Declaration",
          "key": {
            "type": "Identifier",
            "value": "i"
          }
        }
      ]
    },
    "enumerable": {
      "type": "Array",
      "sealed": false,
      "items": []
    },
    "body": {
      "type": "ExpressionStatement",
      "expr": {
        "type": "FuncCall",
        "target": {
          "type": "Identifier",
          "value": "print"
        },
        "args": [
          {
            "type": "Identifier",
            "value": "i"
          }
        ]
      }
    }
  }
]

GeneratorComprehension

GeneratorComprehension is supported

(print(v) for (v of [1, 2, 3]));

to

[
  {
    "type": "ExpressionStatement",
    "expr": {
      "type": "GeneratorComprehension",
      "expression": {
        "type": "FuncCall",
        "target": {
          "type": "Identifier",
          "value": "print"
        },
        "args": [
          {
            "type": "Identifier",
            "value": "v"
          }
        ]
      },
      "comprehensions": [
        {
          "type": "ComprehensionBlock",
          "left": {
            "type": "ExpressionStatement",
            "expr": {
              "type": "Identifier",
              "value": "v"
            }
          },
          "right": {
            "type": "Array",
            "sealed": false,
            "items": [
              {
                "type": "Number",
                "value": "1"
              },
              {
                "type": "Number",
                "value": "2"
              },
              {
                "type": "Number",
                "value": "3"
              }
            ]
          }
        }
      ],
      "filter": null
    }
  }
]

let or const declaration in for statement

let or const declaration in for statement is supported.

for (let i of [1, 2, 3]);

to

[
  {
    "type": "ForOfStatement",
    "init": {
      "type": "LetDeclaration",
      "body": [
        {
          "type": "Declaration",
          "key": {
            "type": "Identifier",
            "value": "i"
          }
        }
      ]
    },
    "enumerable": {
      "type": "Array",
      "sealed": false,
      "items": [
        {
          "type": "Number",
          "value": "1"
        },
        {
          "type": "Number",
          "value": "2"
        },
        {
          "type": "Number",
          "value": "3"
        }
      ]
    },
    "body": {
      "type": "EmptyStatement"
    }
  }
]

GeneratorExpression

GeneratorExpression is supported.

(function* generator() { });

to

[
  {
    "type": "ExpressionStatement",
    "expr": {
      "type": "GeneratorExpression",
      "kind": "EXP",
      "params": [],
      "body": [],
      "name": "generator"
    }
  }
]

GeneratorExpression direct property

GeneratorExpression direct property is supported.

({
  *generator() { }
});

to

[
  {
    "type": "ExpressionStatement",
    "expr": {
      "type": "Object",
      "sealed": false,
      "values": [
        {
          "key": "generator",
          "val": {
            "type": "GeneratorExpression",
            "kind": "EXP",
            "params": [],
            "body": []
          }
        }
      ],
      "accessors": []
    }
  }
]

NOTE

  • GeneratorDeclaration is not supported because of no BNF entry
  • YieldDeclaration is not supported because of no BNF entry
  • Only for-of style ComprehensionFor is allowed (reject for-in style) because of BNF

というわけで

どうでしょう, ES.next engine書いてもいいんですよ, id:teramako さん!!

ECMAScript code generator: escodegen

JavaScript ECMAScript

Keeping Esprima core simple

Esprimaのcoreをparser levelに保つということで, code generatorが単一のmoduleになりました.

escodegen

Install

npm install escodegen

example

simple example: (from http://ariya.ofilabs.com/2012/02/primavera-updates-of-esprima.html )

escodegen.generate({
    type: 'BinaryExpression',
    operator: '+',
    left: { type: 'Literal', value: 40 },
    right: { type: 'Literal', value: 2 }
});

and gets following string

40 + 2

See API page for more information.

Future plans

  • adding minify option
  • adding SourceMap option

How to write JS code generator

JavaScript

f:id:Constellation:20120202003445p:image

esprimaに入りました. 次のversionからesprima.generateで利用可能です. Issue 89 - esprima - Code generator: convert AST to source code - ECMAScript parsing infrastructure for multipurpose analysis - Google Project Hosting


JSのpretty printerを作りました. ECMAScriptのparserとしてesprimaを使っていて, 自作のcode generatorがASTから綺麗なJSをprintします.
で, 現在はesprima code baseに持って行こうとしています. 将来的にesprimaで使えるようになる予定なので, 使いたい!! という方はお待ちください.

operator precedence

ASTではparenthesisの情報が落ちています. もちろん, 全て括弧で囲めば評価順序は問題ないわけですから,

((((((1 + 1) + 1) + 1) + 1) + 1) + 1)

とprintすれば, 別段問題はないわけです. しかし, これはprettyですか? いやいやご冗談を...

つまり, 端的には

(1 + 2) * 3

はこのまま残すけれども,

1 + (2 * 3)

1 + 2 * 3

としたいわけです. はたしてどうするのか?

前提, precedence

parserではこのような優先順位の異なる結合をうまく扱う方法として, operator precedence parserが存在します.

では, code generatorはこれの逆をやればいいわけです.
precedenceは結合優先度が高ければ高いexprほど高くなります. つまり, LogicalOR < LogicalAND < ... < Additive < Multiplicative < Unary < ... < Primaryという風にです.
いま, 現在のgeneratorのprecedenceというものを設定します. これは現在generatorがどのprecedenceを最低レベルとしているかというもので, generatorはこれより低いprecedenceを持つoperatorのexprを出力するには括弧で囲む必要があります.

実例1
1 + (2 * 3)

という形のASTが与えられたとします. これからpretty-printを行いましょう.
すると, まずは最低のprecedence, Sequential(コンマ区切りのもの. expr, expr, expr)をgeneratorに設定してgenerateします. このexprはAdditiveなので, Sequentialよりも高いprecedenceです. よってこのexpr全体には括弧がいりません.

次にlhsの1です. AdditiveExpressionは

AdditiveExpression + MultiplicativeExpression

ですから, こちらはAdditiveのprecedenceでgenerateします. すると1はPrimaryExpression(というかNumericLiteral)です. これは最高precendenceなので気にすることなく1を出力します(括弧なし)

rhsの(2 * 3)です. 上のBNFより, Multiplicativeのprecedenceでgenerateします. すると対象は*でMultiplicativeですから, MultiplicativeとMultiplicativeなのでより低いということはありません. よって括弧なしでgenerateします.

この結果,

1 + 2 * 3

を得ることができます.

実例2
1 * (2 + 3)

次にという形のASTが与えられたとします.
すると, まずは最低のprecedence, Sequentialをgeneratorに設定してgenerateします. このexprはMultiplicativeなので, Sequentialよりも高いprecedenceです. よってこのexpr全体には括弧がいりません.

次にlhsの1です. MultiplicativeExpressionは

MultiplicativeExpression * UnaryExpression

ですから, こちらはMultiplicativeのprecedenceでgenerateします. するとPrimaryなので, 括弧なしで1を取り出します.

問題はrhsの(2 + 3)です. 上のBNFより, Unaryのprecedenceでgenerateします. すると対象は+でAdditiveですから, Unaryよりも低いprecedenceなわけです. そこでgeneratorはすかさず括弧でこのexprを囲みます!!! (2 + 3)

この結果,

1 * (2 + 3)

を得ることができます. よかった!!

blockとelse-ifの連結

非常に簡単なことに, 基本的にはstatementをとるstatementではひとつindentを下げるというそれだけの規則でうまく行きます.

if (cond)
    print("HELLO");

のようにです. ただし, ここでたった2つだけ例外を考慮することで, 綺麗なcodeを出力できます.

blockは全体のstatementにくっつく

blockは前のstatementにくっつきます. つまり,

if (cond)
    {
        print("HELLO");
    }

という風にblock自体がstatementとしてindentが下がるのではなく, if (cond)にくっついて,

if (cond) {
    print("HELLO");
}

となります. FunctionExpressionやらdo-whileやら, blcokらしきものを所持する可能性があるstatement, expressionでこのcheckを行うことで, 綺麗なcodeを出力できます.

else-ifはくっつく

今のままでは

if (cond) {
    print("HELLO");
} else
    if (cond2) {
    }

となってしまいます. else-ifでセットになっているのではなく, あれは単にelse statementのstatementにif文を突っ込んでいるだけであるためです. このため, elseが存在するとき, そのstatementがif文であったときにはelseに吸い付くようにします. すると,

if (cond) {
    print("HELLO");
} else if (cond2) {
}

となります. 綺麗!

まとめ

pretty-printerは思いの外simpleな規則で綺麗に実装できました.

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  // 安心

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

補足

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