Ruccola VM Crystal版の速度改善 (2022-08)

github.com

fastvm/rclvm.cr の高速化の自分用メモ。


  • オペコードを String のまま取り回す実装だった → これをシンボルや enum にするとどうなるか
  def execute : Int32 | Nil
    insn = @mem.main[@pc]

    opcode = insn[0]
    case opcode
    when "exit"     then return insn[1].as(Int32)
    when "cp"       then cp()       ; @pc += 1
    when "lea"      then lea()      ; @pc += 1
    when "add_ab"   then add_ab()   ; @pc += 1
    # ...

修正前はこうなっていて、文字列比較してるとこで遅くなってそう。


  • 使っている Crystal のバージョンが 1.0.0 のままだった → これを最新の 1.5.0 に上げるとどうなるか

計測

変更前
real    1m34.613s / user    1m44.672s / sys     0m2.679s
real    1m34.598s / user    1m44.409s / sys     0m2.869s
real    1m34.340s / user    1m44.597s / sys     0m2.555s

opcode をシンボルに変更しただけ
real    1m29.133s / user    1m36.528s / sys     0m2.152s
real    1m28.814s / user    1m36.282s / sys     0m2.106s
real    1m29.255s / user    1m36.347s / sys     0m2.400s

opcode を enum に変更しただけ
real    1m28.696s / user    1m35.704s / sys     0m2.447s
real    1m29.589s / user    1m36.684s / sys     0m2.367s
real    1m28.533s / user    1m35.828s / sys     0m2.244s

Crystal のバージョン変更だけ(1.0.0 => 1.5.0)
real    1m13.030s / user    1m21.938s / sys     0m2.984s
real    1m12.881s / user    1m21.927s / sys     0m2.772s
real    1m12.474s / user    1m21.444s / sys     0m2.840s

Crystal 1.5.0 + enum
real    1m8.694s / user    1m16.653s / sys     0m2.906s
real    1m8.094s / user    1m15.968s / sys     0m2.952s
real    1m8.741s / user    1m16.860s / sys     0m2.683s

メモ

  • v1.5.0 に上げただけでけっこう速くなる
    • 処理時間は 23% 減、速度は 1.30倍
  • バージョンアップの寄与の方が大きいが、シンボル化・enum化でも多少速くなる
  • 速度向上の優先度
    • そんなに高くない。あまりがんばらずに速くできるならやってしまおうか、くらいの温度感。
    • 可読性・保守性を損なわない方を優先

Crystal では String#to_sym は使えないが、 オペコードの種類は限られているので自前で変換してやれば String からシンボルへの変換は可能。

      opcode =
        case opcode_str
        when "exit"     then :exit
        when "cp"       then :cp
        when "lea"      then :lea
        when "add_ab"   then :add_ab
        # ... snip ...
        else
          raise # 不正なオペコード
        end

……という方法を思いついてないせいでシンボル化できないと思っていたか、 面倒そうなので後回しにしていたか(忘れたけどたぶん前者)。

シンボル (Symbol) - Crystal
https://ja.crystal-lang.org/reference/syntax_and_semantics/literals/symbol.html

シンボルはコンパイル時に解釈されるもので、動的に生成することはできません。シンボルを生成する唯一の方法はシンボルリテラルを使うことです。


  • シンボルと enum どちらを使うか
    • せっかく Crystal を使っているので、この場合は enum でいいんじゃないかなと
    • 煩雑さはシンボルを使う場合でもあまり変わらない (String#to_sym が使えないので)

列挙型 (Enum) - Crystal
https://ja.crystal-lang.org/reference/syntax_and_semantics/enum.html


最終的に Crystal 1.5.0 + enum 化によって

  • 処理時間は 27.5% 減
  • 速度は 1.38倍

になった。


コミット:

vm2gol v2 (63) sub_sp 命令を廃止 / panic



sub_sp 命令を廃止

VM命令 sub_sp を廃止しました。 オペランドを負の値にすれば add_sp で代用できるので。 これで VM のコードが5行減って、実装の量の面でも、仕様の面でも、またちょっとコンパクトになりました。

VM命令がいっぱいあると、入門者視点では「えー、こんなにいっぱい覚えないといけないの……」となりそうなので、少ない数で済ませられるならその方がいいかなと。

ちなみに sub_sp を使っているのは変数宣言のときだけ。

--- a/vgcodegen.rb
+++ b/vgcodegen.rb
@@ -290,7 +290,7 @@ def gen_stmts(fn_arg_names, lvar_names, stmts)
 end
 
 def gen_var(fn_arg_names, lvar_names, stmt)
-  puts "  sub_sp 1"
+  puts "  add_sp -1"
 
   if stmt.size == 3
     _, dest, expr = stmt

panic

たとえばコンパイラが完成するまでのこういう状態だったら、

# 例: vgcodegen.rb: _gen_expr_binary

  case operator
  when "+"  then _gen_expr_add()
  else
    raise not_yet_impl("operator", operator)
  end

"not yet implemented" というメッセージも間違いではありませんでした。 まだ + 演算子しか実装していないが、これから *== などの場合の処理も実装していく予定である、という表明になっています(そのつもり)。

しかし、今は完成してだいぶ落ち着いている状況であり、 新たな演算子を追加する予定は今のところありません。

  case operator
  when "+"  then _gen_expr_add()
  when "*"  then _gen_expr_mult()
  when "==" then _gen_expr_eq()
  when "!=" then _gen_expr_neq()
  else
    raise not_yet_impl("operator", operator)
  end

こうなってくると、 "not yet implemented" というメッセージと実装者(私)の意図とのずれが気になってきます。

というわけで、 not_yet_impl を使っていた箇所は一律で panic に置き換えました。

あわせて、パーサで使っていた ParseError クラスをなくしました。

その他


sub_sp をなくしたのでサイズはちょっと減りました。

$ wc -l vg*.rb common.rb
   66 vgasm.rb
  375 vgcodegen.rb
   57 vglexer.rb
  368 vgparser.rb
  442 vgvm.rb
   52 common.rb
 1360 合計

  # コメントを除いたサイズ:
$ cat vg*.rb common.rb | grep -v '^ *#' | wc -l
1324