LuneScript のトランスコンパイル高速化 (トランスコンパイル時間を 2273 パーセント改善)

今回の時間短縮は以下の通りです。

この表は、セルフホスティングしているソースのトランスコンパイル時間の計測結果を 示しています。 lua VM で動作させた lnsc と、go でビルドした lnsc で計測しています。

改善前の 6e5661a9 は、2021/5/6 のバージョンです。 今回の 改善後3 の 8898c475 は、2021/6/29 のバージョンです。

この表の通り、 改善前の Lua と、 今回の改善後3 go のトランスコンパイル時間を比べると (/ 25.69 1.13) 22.734513274336287 == 2273% 改善しています。

あと少しで 1 秒を切れるところまで改善しました。

なおこの時間は、 lns コマンドの処理時間を time コマンドで計測した結果です。 一方で、トランスコンパイラ内部で計測すると、 その処理時間は 約 0.94 秒 となっていて 1 秒を切っています。 つまり、トランスコンパイラの起動・終了処理に 約 0.2 秒程度かかっているようです。

次の図は、セルフホストのトランスコンパイル実行時の flamegraph です。

これを見ると、左端の Go runtime にかなり多くの時間がかかっていることが分かります。 ただ、この時間がパフォーマンスにどの程度影響しているかは分かっていません。

この Go のランタイム処理は、基本的には GC の制御だと思います。

GC 制御にこれだけ時間がかかっているということは、 それだけオブジェクトをヒープに生成しているということでもあります。 つまり、ヒープへのオブジェクト生成を抑制できれば、 GC 制御も軽くなることが考えられます。

現状の LuneScript は、 全てのクラスのオブジェクトをポインタで管理 します。

以下の記事によると、 ポインタで管理するオブジェクトは、 ほとんど全てのケースでヒープに生成される ということです。

<https://hnakamur.github.io/blog/2018/01/30/go-heap-allocations/>

つまり、 LuneScript のクラスオブジェクトは、 ほとんど全てがヒープに生成される ことになります。

これでは Go のランタイム処理が重くなるのも当然 でしょう。

ならば、出来るだけポインタを使用せずにクラスオブジェクトを管理できれば、 ヒープのオブジェクト数が減り、Go のランタイム処理は軽くなるはずです。

ただしここで疑問なのは、 GC 処理が重いのは間違いないとしても、 スタック割り当てにした時に、本当に軽くなるのか？ というところ。

また、LuneScript のデータ構造で、 オブジェクトをスタック割り当てにすることが可能かどうか？ というところです。

スタック割り当てにして本当に高速化できるのかを確認するため、 簡単な検証用コードを作成しました。

このコードは、 sub1 〜 sub4 をそれぞれ一定回数実行し、 それぞれの実行時間を出力します。

コメントの // escape は、 $ go build -gcflags -m コマンドで escapes to heap と出力された箇所を示します。

package main

import "fmt"
import "time"
import "runtime"

type Test struct {
    val int
}

var list1 = make( [] Test, 1 )
var list2 = make( [] interface{}, 1 )

func sub1( test Test ) {
    list1[ 0 ] = test
}
func sub2( test *Test ) {
    list2[ 0 ] = test
}    
func sub3( test Test ) {
    list2[ 0 ] = test // escape
}
func sub4( test *Test ) {
    list1[ 0 ] = *test
}

func profile( name string, callback func() ) {
    runtime.GC()
    prev := time.Now()

    callback()
    
    fmt.Printf( "%s: time = %v\n", name, time.Now().Sub( prev ).Milliseconds() )
}

func main() {
    maxCount := 100000 * 50000
    profile( "sub1", func() {
        test := Test{}
        for count := 0; count < maxCount; count++ {
            sub1( test )
        }
    })
    profile( "sub2", func() {
        test := &Test{} // escape
        for count := 0; count < maxCount; count++ {
            sub2( test )
        }
    })
    profile( "sub3", func() {
        test := Test{}
        for count := 0; count < maxCount; count++ {
            sub3( test ) // escape
        }
    })
    profile( "sub4", func() {
        test := &Test{}
        for count := 0; count < maxCount; count++ {
            sub4( test )
        }
    })
}

この処理は、 Test 構造体のオブジェクトを生成し、 スライスの list1 あるいは list2 に格納します。 オブジェクトの生成から格納するまでの間、 値渡しで処理するか、ポインタ渡しで処理するかによって、 実行時間にどのような違いが出るかを計測します。

各関数はそれぞれ以下を実行しています。

• sub1

  • 値渡しのまま処理する。

• sub2

  • ポインタ渡しのまま処理し、interface{} に変換する。

• sub3

  • 値渡しのデータを、 interface{} に変換して処理する。

• sub4

  • ポインタが示すアドレスから、値をコピーして処理する。

上記プログラムの実行結果は次の通りです。

sub1: time = 1765
sub2: time = 3724
sub3: time = 11300
sub4: time = 3713

これを見ると、以下が分かります。

• 値渡しをしている sub1 が一番高速に動作している。
• ポインタ渡しをしている sub2 は、sub1 の倍以上の時間かかっている。
• 値渡しのデータを interface{} に変換している sub3 は、 最初からポインタでデータを保持している sub2 の 3 倍時間がかかっている。
• ポインタ渡しのデータから値をコピーするだけなら escape されない。 しかし、コピーに時間がかかってしまい、 最初から最後までポインタで持っている sub2 と変わらない。

これにより、 値渡しがポインタ渡しよりも高速に動作する ことが確認できました。

一方で、 sub3 のケースのように 値をスタック割り当てで処理する場合でも、 途中で interface{} に変換すると逆に遅くなる ケースがある。 ということも分かりました。

特に、 sub1 と sub2 の比率と、 sub2 と sub3 の比率を比べると、明らかに後者の方が大きいです。

つまり、 中途半端なスタック割り当ては逆効果になる ということです。 sub1 のつもりでスタック割り当て対応したら、結果は sub3 になってしまう。 そんなことが起きる可能性があります。

これを考えると、 下手にスタック割り当てすると今よりさらに遅くなる 可能性があるということで、 スタック割り当て対応は慎重に 行なわなければなりません。

LuneScript でスタック割り当てを実現する場合、以下を検討する必要があります。

• lua にトランスコンパイルした時の動作の定義
• スタック割り当てと、ヒープ割り当ての syntax 上の表現

class Test {
  let mut val:int {pub,pub};
}
fn foo( test:&Test ) {
   print( test.$val );
}
fn bar( test:Test ) {
   test.set_val( 10 );
}
let mut test = new Test(1);
foo( test ); // 1
bar( test );
foo( test ); // 10

class Test {
  let mut val:int {pub,pub};
}
fn foo( test:&Test ) {
   print( test.$val );
}
fn bar( test:Test ) {
   test.set_val( 10 );
}
let test;
{
   let mut work = new Test(1);
   foo( work );
   bar( work );
   test = work;
}
foo( test );