Optz Michelson オプティマイザをリリースしました

Optz は Tezos ブロックチェーンのスマートコントラクトで使われている Michelson プログラムの最適化器です。 Optz は Michelson プログラムを入力として受け取り、(可能ならば)最適化を行って同じ動作をするより小さい、効率的な Michelson プログラムを出力します。

Michelson オプコード列の最適化

Optz の最適化は、ルールベースのプログラム書き換えと A* アルゴリズムによる最適スタック命令列検索の二つを行っています。

ルールベースのプログラム書き換え
次のような書き換えルールを使い、合致した命令列をより良いものに置き換えます:
PAIR; CDR  =>  DROP
   
DIP n { a }; DIP n { b }  =>  DIP n { a; b }
   
SWAP; op  =>  op  # when op is a commutative binary operator
   
NOT; IF { a } { b }  =>  IF { b } { a }
最適スタック命令列検索
A* アルゴリズムを使い、DROP, SWAP, DIG, DUG, DIP, DUP, と push のみを行う PUSHEMPTY_SET といったスタック操作命令列に対して、同じ動作をする最小命令列を検索します。例えば、
DIG 1; DUP 1; DUG 2; PUSH c0; DIG 2; PUSH c1; DIG 4

は次のより短いコードに置き換え可能です:

PUSH c0; DIG 1; PUSH c1; DUP 4

最適化対象命令列の長さとそこに出現する定数の数が増えると、この検索スペースは指数関数的に増加します。最適化検索を実用的な時間で終了させるために、対象命令列の長さには制限を加えています。

Drop-only 命令列に対する最適スタック命令作成
高レベル言語から Michelson スタックマシーンへのコンパイラでは、よく関数や変数のスコープ脱出の際にスコープから外れる変数をスタックから消し去る動作が入ります。一部のコンパイラではこのスタックの掃除に対して非常に冗長で効率の悪いコードを生成していることがわかりました。このコードはあまりに長いため、上記の最適スタック命令列検索では現実的な時間での最適化を行うことができません。

Optz では、このスタック掃除コードの最適化のため、スタックから一部の要素を取り除くだけで、新しい要素を付け加えたり、順番を入れ替えることをしない、「drop-only」操作列に対する特別な最適化を導入しています。Drop-only 操作に対する最適な命令列は A* を使わずとも簡単に生成できるため、対象命令列に長さ制限を設ける必要がありません。例えば、

DROP 2; DIG 1; DROP 1; DIG 1; DROP 1; DIG 3; DROP 1; DIG 3; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1

というコードはこの最適化により、次の非常に短い効率の良いコードに書き換えることができます:

DROP 2; DUG 2; DROP 2; DIG 3; DIG 4; DROP 2; DIP 4 { DROP 6 }

Tezos Mainnet のコントラクトに対する最適化

2021-02-18 から 2022-02-17 の一年間にTezos Mainnet にデプロイされた 1711 個の異なるスマートコントラクトを Optz を使って最適化を行いました。 ラップトップ(Mac Book Pro 13-inch 2017)上で、すべてのコントラクトコードは1秒以内に Optz による最適化が完了。平均して元のサイズの 94% のコントラクトに書き換えられました。30%以上のサイズ削減率になったコードもありました。

Try Optz now

ダイラムダでは Optz のソースコード、 Docker イメージ、ブラウザ上で最適化を行えるウェブアプリ を公開しています。 詳しくは Optz プロジェクトのページ をご覧ください。