TL; DR

Vim scriptをパースしてASTを作り、高速化を図ります。リポジトリはこちら→wholekeik/vim

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

AST化

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

大まかな流れ

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

AST化できるコマンド・式

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

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

" 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のテストがすべて通るようになりました！！これでバグはかなり少なくなったと言えそうです。

ベンチマーク

デバッグ用に有効にしていたいくつかのオプションを削除してmakeし、デバッグシンボルをstripで消し去ります。計測にはvital.vimのテストを利用しました。

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化できる
何度も繰り返し同じ関数を呼び出す
式がやたら複雑（毎回パースすると不利になる）

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

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

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 - . 演算子編）。

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にはできません。「右側に空白が一つ以上あればそのドット演算子を文字列結合とみなす」というルールがあればこの問題を（部分的に）解決できるのではないかと思っています（左側だと行継続の関係で辞書のアクセスでもスペースがある可能性があります）。ただ互換性が壊れる危険があるのでこれについては既存のスクリプトを調査する必要があります。

試したい方へ

$ 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が直接変更されており、デバッグ用のフラグがいくつかオンになっています。ベンチマークを取っていただける場合は、それらを切ってコンパイラの最適化オプションを有効にした状態でお願いします。

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

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