mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの? ① (あるいはJavaの文字連結最適化について)

前置き

最近色々ありましてmrubyやKopiLua(C#によるLua実装)のソースコードを読んだりしております。
ちょうどVM部分を読んでいたら、面白い部分を見つけました。

これまでx86アセンブラしか読んだことがなかったので特殊かどうかよくわからない…
そこでふとLL言語でない, 例えばJavaのVMはどうなってるんだろうなーと思い調べてみました。

とそこで

というわけでこの論文を読んでみたのでメモも兼ねてまとめてみます。

読んだもの :

Y. H. Tian. String concatenation optimization on Java bytecode. In Proceedings of the Conference on Programming Languages and Compilers, pages 945--951. CSREA Press, 2006.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.5641&rep=rep1&type=pdf

1. 問題提起

Javaの文字列連結に関してはこれまで様々な最適化の手法がとられてきた。
例えば以下のようなコードがあったとする。

String s = x + "abc" + someInt + someArray[index];

本来ならば3つの+演算子それぞれがstringを返す処理となる。
この3つのオブジェクトはこの一度しか使われずにGCによって回収される。この分のコストはかなり大きなものである。
最近のJavaではStringBufferを使い, よく最適化されたコードを出力してくれる。
例えば先ほどのコードは以下のコードと等価なバイトコードに変換される。

StringBuffer temp = new StringBuffer( );
temp.init();
temp.append(String.valueOf( x ));
temp.append(String.valueOf("abc"));
temp.append(String.valueOf(someInt));
temp.append(String.valueOf(someArray[index]);
String s = temp.toString( );

ここではStringBufferを一度だけ生成し, これを使いまわして文字を連結している。 また, StringBufferとStringはバッファを共有するため, 両者の変換にはほとんどコストがかからない。
この, StringBufferを生成してからtoStringを行うまでのブロックをstring concatenation block(SCB)と呼ぶ。
しかし文字列連結のコストの問題がこれですべて解決されるわけではない。例えば以下のようなコードを考えてみる。

String x = "hello";
for (int i=0; i<1500; i++) {
x += "world";
}

このコードは以下のような疑似コードと等価なバイトコードに変換される。

r1 = "hello";
i1 = 0;
label0:
if i1 >= 1500 goto label1;
StringBuffer temp = new StringBuffer( );
temp.init();
temp.append(String.valueOf( x ));
temp.append(String.valueOf( "world" ));
String x = temp.toString( );
i1 = i1 + 1;
goto label0;
label1:
:

ここでは1500回のループそれぞれについてStringBufferオブジェクトが生成され, それらはすべて後からGCに回収される。
しかしこの場合, StringBufferは一度生成したものを使いまわせるはずである。この論文ではこの最適化を実現する方法について論じている。

2. The reaching definitions relation analysis algorithm

2.1 Reaching Definitions Relation Graphについて

この論文ではReaching Definitions Relation Analysis (以下RDRA)による最適化アルゴリズムが説明されている。
この手法ではまず最初にメソッドの解析を行い, Reaching Definitions Relation Graph (RDRG)を生成する。まずはこのグラフについて説明する。
・各ノードはSCBを表す。
・各エッジはSCBで生成されるStringのReaching Definitions Relation (定義の依存関係?)を表す。

例えば以下のコードを見てみる。

String x = "hello";
x = x + "world";
if (true) {x = x + "abc";}
else {x = x + "efg";}
x = x + "xyz";

このコードからは次のようなグラフが生成される。

f:id:domitry_h:20131207192948p:plain

このグラフは制御フローグラフによく似ている。 プログラムはまずSCB1を実行し, SCB2かSCB3のいずれかに分岐する。その後両者はSCB4で合流する。
SCB1の最後で生成されたstringはSCB2またはSCB3で使われ, それらのブロックの最後で生成されたstringはSCB4で使われる。

2.2 RDRAについて

このグラフを見て私たちが知りたいのは以下の2点である。
・ どのような場合, StringBufferを新しく生成しないですむのか?
・ どのStringBufferを使いまわすことができるのか?
この2つは各ノードに入ってくるエッジを調べることで確認できる。
各ブロックに対して最適化をかけることができるケースとできないケースがある。それらはノードとエッジの関係を調べることで下のいくつかに分類できる。

1. 入力エッジが1本かつ入力元のノードが自分自身、 または直接支配ノードでない場合
ループケース。 ループの直前で生成したStringBufferを使いまわすことができる。

f:id:domitry_h:20131207214848p:plain

2. 入力エッジが0本の場合
下図のSCB1。 StringBufferは新しく生成しないといけない。

3. 入力エッジが1本かつ入力元のノードが直接支配ノードの場合
下図のSCB2, SCB3。 直接支配ノードで生成されたStringBufferを使いまわすことができる。

4. 入力エッジが2本以上かつ入力元のノードに共通の直接支配ノードが存在する場合
下図のSCB4。 入力元ノードに共通の直接支配ノードで生成されたStringBufferを使いまわすことができる。

f:id:domitry_h:20131207214857p:plain

5. 入力エッジが2本以上かつ入力元のノードに共通の直接支配ノードが存在しない場合
下図のSCB5。StringBufferは新しく生成しないといけない。
f:id:domitry_h:20131207214912p:plain

2.3 実例

以下のようなコードを考える。

String x = "hello";
i = 22;
x = x + "world";
for (int j = 0; j < 3; j++) {
    if (i > 15) {
       x = x + "abc";
    }
    else if (i < 8) {
         x = x + "efg";
    }
    for (int k = 0; k < 2; k++) {
        x = x + "xyz"
    }
}

これを解析することで以下のRDRGが生成される。

f:id:domitry_h:20131207214939p:plain

Analizerの動作は次のようになる。
1. SCB1から開始
入力エッジは0本なので新しくStringBufferを生成する。

2. SCB2に移る
入力エッジが2本以上あるので入力元のノードを確認する。 SCB2の入力元ノードはSCB1, SCB2, SCB3, SCB4なので, これらすべてについて調べる。
これらのノードは全て共通の直接支配ノードSCB1を持つ。(SCB1はSCB1自身によって支配されていると考える)
よってSCB2ではSCB1で生成されたStringBufferを使いまわすことができる。

3. SCB3, SCB4を調べる
この2つについても入力元のノードが共通の直接支配ノードSCB1を持つことが確認できるため, それぞれSCB1で生成されたStringBufferを使いまわすことができると確認される。

3. Liveness analysis with RDRA

上のRDRAのみによる解析では問題点が生じる。例えば以下のようなコードを考えてみる。

S1: String x = "hello";
S2: x = x + "world";
S3: x = x + "123";
S4: String y = x + "abc";
S5: x = x + "efg";
S6: y = y + "xyz";

このコードからは以下のようなReaching Definitions Relation Graphを描くことができる。

f:id:domitry_h:20131207193650p:plain

この中でSCB3に注目してみる。
SCB3に入っているエッジは1本だけなので, 一見するとSCB3でSCB2のStringBufferを使いまわすことができるように見える。
しかしそれを行ってしまうと, SCB4でもSCB2のStringBufferが使いまわされるため, xが期待された値にならなくなってしまう。
つまり, x="helloworld123efg"であることが期待されるが, SCB3でStringBufferを使いまわすことで x="helloworld123abcefg" になってしまう。
これはRDRAだけでは, このブロックの処理が終わった後xが再び必要であるかどうかが判断できないからである。

この論文ではこの問題を, RDRAと共にLiveness analysisを行うことで解決している。
例えばS4を見てみる。 S4以降のコードの中, xが再定義されるまでにS5で再び値が参照されている。そこでS4ではまだxは生きている(alive)であると判断する。
S4でRDRAを適応するとき, xはまだ生きているので, yを新しく定義するときxのStringBufferを使いまわすことはできないと判断することができる。
この場合は最適化を行わず, SCB3で新たなStringBufferを生成する処理を残す。

5. 実例

String x = "hello";
for (int i=0; i<1500; i++) {
x += "world";
}

このコードはJimpleに変換すると以下のようになる。

r1 = "hello";
i6 = 0;
L1: if i6 >= 1500 goto label1;
$r3 = new java.lang.StringBuffer;
specialinvoke $r3.<..StringBuffer: void <init>()>();
$r4 = virtualinvoke $r3.<..append(..String)>(r1);
$r5 = virtualinvoke $r4.<..append(..String)>("world");
r1 = virtualinvoke $r5.<..toString()>();
i1 = i1 + 1;
goto L1;

これは上で上げたループケースである。
解説した手法を使えば以下のように変換できる。

r1 = "hello";
i6 = 0;
$r3 = new java.lang.StringBuffer;
specialinvoke $r3.<..StringBuffer: void <init>()>();
$r4 = virtualinvoke $r3.<..append(..String)>(r1);
L1: if i6 >= 1500 goto label1;
$r5 = virtualinvoke $r4.<..append(..String)>("world");
r1 = virtualinvoke $r5.<..toString()>();
$r4 = $r5;
i1 = i1 + 1;
goto Ll;

最終的にStringBufferの生成は一度で済み, 処理速度の向上が見込まれる。


今回はmrubyにもLuaにも全く触れませんでしたが次回に続きます。おそらく…