mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの?② (完結編, mrubyとLuaの文字列連結の違い)
これはカーネル/VM Advent Calendar 2013の記事です。
最近本業(大学生)の方が忙しくなかなかコードが書けない@domitryです。
当初はmrubyとLuaを比較してみて似ている点や違う点を挙げて記事にしようと思っていたのですが、時間と知識が足りず断念しました。
前回の記事(http://domitry.hatenablog.jp/entry/2013/12/08/002426)の続きになります。
続き物の記事の2つ目をAdvent Calendarのネタにしてしまいましたが、前回の内容とほとんど関連のない記事ですのでご容赦ください。
前置き
疑問点: mrubyやLuaのVMにある文字列連結専用のオペコードは何故存在するのか？
mrubyにはOP_STRCAT, LuaにはOP_CONCATという文字列連結用のオペコードが存在します。
しかしJavaやCIL, Python VMなど他のVMにはこのようなバイトコードは存在しません。
これを解決するため、今回はmrubyとLuaの文字列連結処理を比較してみます。
参考URL
1.動的文字列&正規表現 - ひとり勉強会
http://d.hatena.ne.jp/hzkr/touch/20061215/p15
2. mruby命令セット - きむしゅノウハウ帳
http://kimushu.thyme.jp/knowhow/ruby:mruby:instructions
3. Luaのコード生成 - Safx
https://sites.google.com/site/safxdev/lua_codegen
4. [ruby] 文字列の連結 - ぞえの戯れ言
http://d.hatena.ne.jp/t-tkzw/20060709/p3
5. mruby/mruby - GitHub
https://github.com/mruby/mruby/
6. LuaDist/lua - GitHub
https://github.com/LuaDist/lua
Rite VM (mruby)
最初にmrubyの文字列連結がどのように行われているのか調べてみる。
mrubyでは実行時に--verbose オプションをつけることで構文木とバイトコードを出力させることができる。
以下のようなサンプルコードのバイトコードを出力させる。
str = "hoge" 10.times do str += "hoge" end print str
すると以下のようになる。
NODE_SCOPE:
local variables:
str
NODE_BEGIN:
NODE_ASGN:
lhs:
NODE_LVAR str
rhs:
NODE_STR "hoge" len 4
NODE_CALL:
NODE_INT 10 base 10
method='times' (262)
args:
block:
NODE_BLOCK:
body:
NODE_BEGIN:
NODE_OP_ASGN:
lhs:
NODE_LVAR str
op='+' (109)
NODE_STR "hoge" len 4
NODE_CALL:
NODE_SELF
method='print' (264)
args:
NODE_LVAR str
irep 240 nregs=4 nlocals=2 pools=1 syms=2
000 OP_STRING R1 "hoge"
001 OP_LOADI R2 10
002 OP_LAMBDA R3 I(+1) 2
003 OP_SENDB R2 :times 0
004 OP_LOADSELF R2
005 OP_MOVE R3 R1
006 OP_SEND R2 :print 1
007 OP_STOP
irep 241 nregs=3 nlocals=1 pools=1 syms=1
000 OP_GETUPVAR R1 1 0
001 OP_STRING R2 "hoge"
002 OP_ADD R1 :+ 1
003 OP_SETUPVAR R1 1 0
004 OP_RETURN R1
hogehogehogehogehogehogehogehogehogehogehogeこのようにOP_STRCATではなくOP_ADDが埋め込まれている。
この後試行錯誤してみる(<<演算子や数値の結合)がOP_STRCATにお目にかかれない。
このままではどのような場合にOP_STRCATが埋め込まれるのかわからないので、mrubyのコード生成部分を読む。
(mruby/src/codegen.cから抜粋)
case NODE_DSTR:
if (val) {
node *n = tree;
codegen(s, n->car, VAL);
n = n->cdr;
while (n) {
codegen(s, n->car, VAL);
pop(); pop();
genop_peep(s, MKOP_AB(OP_STRCAT, cursp(), cursp()+1), VAL);
push();
n = n->cdr;
}
}NODE_DSTRの処理の中でOP_STRCATが埋め込まれている。
調べてみるとNODE_DSTRは式展開が必要な文字列リテラルを扱うときに生成されるノードのようだ。
これを踏まえて以下のようなサンプルコードを書いて、同じようにmrubyに通してみる。
a = "ruby"
b = "java"
p "I love #{a}, not #{b}"そうすると以下のように出力される。
NODE_SCOPE:
local variables:
a, b
NODE_BEGIN:
NODE_ASGN:
lhs:
NODE_LVAR a
rhs:
NODE_STR "ruby" len 4
NODE_ASGN:
lhs:
NODE_LVAR b
rhs:
NODE_STR "java" len 4
NODE_CALL:
NODE_SELF
method='p' (266)
args:
NODE_DSTR
NODE_STR "I love " len 7
NODE_BEGIN:
NODE_LVAR a
NODE_STR ", not " len 6
NODE_BEGIN:
NODE_LVAR b
NODE_STR "" len 0
irep 240 nregs=6 nlocals=3 pools=5 syms=1
000 OP_STRING R1 "ruby"
001 OP_STRING R2 "java"
002 OP_LOADSELF R3
003 OP_STRING R4 "I love "
004 OP_MOVE R5 R1
005 OP_STRCAT R4 R5
006 OP_STRING R5 ", not "
007 OP_STRCAT R4 R5
008 OP_MOVE R5 R2
009 OP_STRCAT R4 R5
010 OP_SEND R3 :p 1
011 OP_STOP
"I love ruby, not java"0,1行目で"ruby", "java"のstringが生成されそれぞれR1,R2レジスタに代入される。
その後"I love", ", not"のstringもそれぞれ生成され、順にOP_STRCATで結合されていく。
調べてみるとYARV(CRuby)でも同じ構文木が生成されるということがわかった。
こちらでも式展開で生成された文字列がconcatstrings命令で連結されるようなバイトコードが出力されるようだ。
(参考URL1: http://d.hatena.ne.jp/hzkr/touch/20061215/p15)
Luaにはこのような式展開を伴う構文は存在しない。
つまりこのオペコードはLua由来ではなく、CRubyから引き継がれてきたものだった！
Lua
ではLuaのVMでは文字列連結をどのように行っているのか見てみる。
luacに-lオプションを付けることでどのようなバイトコードが出力されるか見ることができる。
以下のようなサンプルコードを-lオプションを付けてコンパイルしてみる。
a = "Hello"
for i=1,10 do
a = a .. "fuee"
end
print(a)すると以下のようなコードが出力される。
$ ./luac.exe -l test1.lua
main <test1.lua:0,0> (14 instructions at 0x80048e60)
0+ params, 6 slots, 1 upvalue, 4 locals, 6 constants, 0 functions
1 [1] SETTABUP 0 -1 -2 ; _ENV "a" "Hello"
2 [2] LOADK 0 -3 ; 1
3 [2] LOADK 1 -4 ; 10
4 [2] LOADK 2 -3 ; 1
5 [2] FORPREP 0 4 ; to 10
6 [3] GETTABUP 4 0 -1 ; _ENV "a"
7 [3] LOADK 5 -5 ; "fuee"
8 [3] CONCAT 4 4 5
9 [3] SETTABUP 0 -1 4 ; _ENV "a"
10 [2] FORLOOP 0 -5 ; to 6
11 [5] GETTABUP 0 0 -6 ; _ENV "print"
12 [5] GETTABUP 1 0 -1 ; _ENV "a"
13 [5] CALL 0 2 1
14 [5] RETURN 0 1こちらでは演算子を用いた文字列連結にOP_CONCATが使われているようだ。
LuaのOP_CONCATは第2オペランドに指定されたレジスタから第3オペランドに指定されたレジスタまでの文字列を結合し、第1オペランドに指定されたレジスタに格納する命令である。(参考url3: https://sites.google.com/site/safxdev/lua_codegen)
この場合、8行目でレジスタ4から5までの文字列を結合し、レジスタ4に格納している。
このようにmrubyとは異なる命令が出力される。
結論
新しく生まれた疑問
一つ目
詳しくは調べていないものの、参考URL1(http://d.hatena.ne.jp/hzkr/touch/20061215/p15)を参照するとYARVではconcatstringが一度しか呼ばれないようにコードが生成されている。
式展開で生成された文字列は順番にスタックに積まれ、一度のconcatstring命令で結合されるようになっている。
それに対してRiteVMのOP_STRCATは2つのオペランドにそれぞれ指定したオブジェクトを結合する命令のため、一度に2つずつしか結合できない。
よって上のようにOP_STRCATが複数回呼ばれるようなコードが生成される。
これはYARVがスタックマシン、mrubyがレジスタマシンであるからと考えられるがLua VMと同じで内部的にはスタックをレジスタのように使っているだけなのだから、Luaと同様に一度に複数のオブジェクトを結合して文字列にするようにはできないのかと思った。
(が、式展開が含まれる文字列リテラルという限られた状況でそんなに高速化を求める必要もないのかな…? 100回の式展開が必要な文字列リテラルとか見たことない)
終わりに
文字列連結についての記事はこれで完結になります。新しくわかったことがあればこの記事に追記します。
文字列連結がかなり奥深い世界で驚きました。
またmrubyとLua両者の実装をしばらく読んでみて、API周りが比較的似ている(mrb_stateとLua_state等)のに対して、オブジェクト周りやVMは全く別物のように感じました。
実装を読んでいるとますますRubyが書きたくなるけど書く機会があまりなくてつらい…
追記
link: mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの?② (完結編, mrubyとLuaの文字列連結の違い) - どみにっき - なぜOP_STRCATが２引数かというと、深い理由はない。多分スタック節約のため？
http://t.co/418XWVorYI
— Yukihiro Matsumoto (@yukihiro_matz) 2013, 12月 23まつもとゆきひろさんからレスポンスがありました！
