Vim scriptを処理系レベルから高速化しようとしている話

# TL; DR

Vim scriptをパースしてASTを作り、高速化を図ります。リポジトリはこちら→[wholekeik/vim](https://github.com/wholekeik/vim/tree/feature/vimscript-optimization)

追記: ベンチマーク追加しました

# AST化

Vim script は実行のたびにコマンドをパースしているので非常に遅い言語です。コマンドをパースしておいてASTとし、それを実行すれば高速化が見込めます。しかし、Vim scriptでは引数の解釈が各コマンドによって全く異なるため、共通のパーサーを書くのは不可能です。したがって事前にパースするのではなく実際に実行しながら並行してASTを作っていきます。なおVim scriptの実行はユーザーの入力（コマンドモード）やオートコマンド、関数などがありますが、ASTとなるのは関数内のみです。また、AST化は行単位で行われます。



# 大まかな流れ

1. 関数を定義する
2. 通常通り呼ばれる
3. 呼ばれたExコマンドのうち、ASTにできるものがあれば実行しつつASTを作る
4. 2回目に同じ関数が呼ばれたとき、ASTが作られていればそちらを実行する。なお、一度AST化に失敗した行は二度とAST化されない


# AST化できるコマンド・式

* if
* elseif
* while
* throw
* echo
* echon
* return
* let
* for
* execute
* echomsg
* echoerr
* 及びこれらの引数に現れる式（の一部）

AST化されているか確認するには、`:function 関数の名前`を入力してください。

```vim
" AST化されていない
  function! F()
1 return 1
  endfunction
" 1行目がAST化されている
  function! F()
1            return 1
  endfunction
```

AST化された行が他の行より深くインデントされます。元々は`optimized: return 1`のように表示していたのですが、Vimのテスト（`make test`）でこの`:function`コマンドの出力をパースするため、~~見づらい~~意味を変えない表記にしました。


# 安定性

Vimのソースコードについているテスト（`make test`）は**すべて通ります**。しかし、同じ関数を二度以上実行してみないとAST化がうまくいっているかはわかりませんので、あまり信用はできません。

追記：**[vital.vim](https://github.com/vim-jp/vital.vim)のテストがすべて通るようになりました！！**これでバグはかなり少なくなったと言えそうです。


# ベンチマーク

デバッグ用に有効にしていたいくつかのオプションを削除して`make`し、デバッグシンボルを`strip`で消し去ります。計測には[vital.vim](https://github.com/vim-jp/vital.vim)のテストを利用しました。

```sh
for i in `seq 1 10`; do
    time ./vim-themis/bin/themis
done
```

`src/feature.h`の`#define FEAT_OPTIMIZATION`を有効にしたもの（AST化あり）としていないもの（AST化なし）とで比較します。

||AST化あり|AST化なし|
|--:|--:|--:|
|1|27.36s|29.03s|
|2|27.33s|28.03s|
|3|28.33s|28.08s|
|4|27.33s|28.02s|
|5|27.18s|28.21s|
|6|27.29s|28.13s|
|7|27.35s|27.95s|
|8|27.33s|28.32s|
|9|29.57s|28.01s|
|10|27.24s|28.61s|
|合計|**276.31s**|**282.39s**|

+2.2%高速

速い!......のか？

正直期待したほど速くはないですが、少なくとも遅くはなっていないようで安心しました。~~この二週間が無駄にならなくてよかった。~~

速さをもっと実感できるように、AST化する方が圧倒的有利になるよう仕組んでみます。

* AST化できる
* 何度も繰り返し同じ関数を呼び出す
* 式がやたら複雑（毎回パースすると不利になる）

```vim:test.vim
function! F()
    return 1 + 5 * 4 / 10 - 7 + 9 % 5
endfunction

for i in range(1000)
    for j in range(1000)
        call F()
    endfor
endfor

quit
```

このスクリプトを使って計測します。

```sh
for i in `seq 1 10`; do
    time ./vim -i NONE -u NONE -N -S test.vim
done
```

||AST化あり|AST化なし|
|--:|--:|--:|
|1|5.25s|5.34s|
|2|5.15s|5.35s|
|3|5.18s|5.42s|
|4|5.16s|5.36s|
|5|5.31s|5.48s|
|6|5.19s|5.51s|
|7|5.25s|5.41s|
|8|5.15s|5.51s|
|9|5.21s|5.43s|
|10|5.24s|5.46s|
|合計|**52.09s**|**54.27s**|

+4.1%高速


速い!!

ここまで極端な例は実際には少ないと思うのであまり参考にはならないかもしれませんが、こちらははっきりと差が出ています。AST化できるコマンドの数を増やせればvital.vimの方ももう少し差が出るかもしれません。`:call`がASTにできないのはかなり痛いので、この二つの実装を急ぎたいところです。



# 破壊的変更

一点のみ、互換性を破壊する箇所があります。具体的にいうと次のスクリプトが動きません（ソース元はこちら→[本当にキモい Vim script - . 演算子編](http://thinca.hatenablog.com/entry/20131127/1385487671)）。

```vim
function! s:func(time)
  let time = a:time
  let suffix = 'min'
  return 1000-time.suffix
endfunction

echo s:func(50)
" => 950min

echo s:func({'suffix': 'sec'})
" => 1000 (これまでの動作)
" => エラー (新しい動作)
```

このように、「関数内でドット演算子を使っているとき、ドット演算子の意味が途中で変化する」とエラーになるようになります。


# 課題

以下はAST化できません。

* **call**
* **ラムダ式**
* `|`を含む行
* 関数内関数
* ある条件を満たすドット演算子

AST化できない式を含むコマンドも連鎖的にAST化できなくなります。

ドット演算子の条件について説明します。Vimのドット演算子は左辺の型が決定しないと優先順位すら定まりません。ここで、`x ? a.b : c.d`のような式を考えてみます。`x`が真の時は`a`が評価されるので一つ目のドット演算子が文字列結合か辞書アクセスかが決定します。しかしその時、`c`は評価されませんので、二つ目のドット演算子はどちらの意味なのかがわかりません。そのため`c.d`をASTにできず、連鎖的に`x ? a.b : c.d`全体がASTにできなくなります。`x`が偽の時も同様のことが起こるため、結局この式は絶対にASTにはできません。「右側に空白が一つ以上あればそのドット演算子を文字列結合とみなす」というルールがあればこの問題を（部分的に）解決できるのではないかと思っています（左側だと行継続の関係で辞書のアクセスでもスペースがある可能性があります）。ただ互換性が壊れる危険があるのでこれについては既存のスクリプトを調査する必要があります。


# 試したい方へ

```console
$ git clone https://github.com/wholekeik/vim
$ cd vim
$ git checkout feature/vimscript-optimization
$ ./configure && make && make test # 注: 私は引数なしのconfigure,makeしか試していません
```

大規模な変更でありどのようなバグがあるかわかりませんので、`-u NONE -i NONE`のフラグ付きで起動するか、.vimrc等のバックアップをとった状態で起動してください。**ファイル消失など、何が起こっても責任は負えません**。

* ブランチは`feature/vimscript-optimization`に切り替えてください。

* `FEAT_OPTIMIZATION`を有効にする必要があります。今は`src/feature.h`に`#define FEAT_OPTIMIZATION`が直書きされているので何もする必要はありません（あとでこれはちゃんとfeatureを定義します）。逆に、その行をコメントアウトすれば`FEAT_OPTIMIZATION`が有効になっていない状態でのテストが可能になります。

* 開発中の利便性のため`src/Makefile`が直接変更されており、デバッグ用のフラグがいくつかオンになっています。ベンチマークを取っていただける場合は、それらを切ってコンパイラの最適化オプションを有効にした状態でお願いします。

この量の変更を一人でテストするのは難しいので、バグ報告だけでも非常に助かります。