読者です 読者をやめる 読者になる 読者になる

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とは異なる命令が出力される。

結論

  1. Luaとmrubyのオペコードはそれぞれ全く別の由来だった。
  2. mruby(というよりRuby)がこのようなオペコードを導入しているのはおそらく言語使用に式展開が必要な文字列リテラルが存在するため。
  3. LuaがなぜOP_ADDでなくOP_CONCATを使っているのかは不明。おそらくは大量結合時のパフォーマンス向上のため?
  4. Javaバイトコードにこのようなオペコードが見当たらないのはmrubyのようにOP_ADDに相当するバイトコードを使用している、または前回の記事にあったようにStringBuilderを使った処理に自動的に置き換えられるから。

新しく生まれた疑問

一つ目

詳しくは調べていないものの、参考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回の式展開が必要な文字列リテラルとか見たことない)

二つ目

JavaのStringBuilder的な最適化が一切ないことが気になった。例えば

hoge += "fuga"

このような場合は << 演算子で代替できる(参考URL4参照)ものの、

s = "hoge" + 4.to_s + "fuga" 

このような場合には最適化が効かないなあと思った。
JavaのStringBuilderが実際どう実装されているのかもわかりませんが…

終わりに

文字列連結についての記事はこれで完結になります。新しくわかったことがあればこの記事に追記します。
文字列連結がかなり奥深い世界で驚きました。

またmrubyとLua両者の実装をしばらく読んでみて、API周りが比較的似ている(mrb_stateとLua_state等)のに対して、オブジェクト周りやVMは全く別物のように感じました。
実装を読んでいるとますますRubyが書きたくなるけど書く機会があまりなくてつらい…

追記

まつもとゆきひろさんからレスポンスがありました!