Solidity on Ethereum Virutual Machine でアルゴリズムを書く
Solidityとはなんぞやという話なんですが、このあたり見てもらえばわかるかなと。つまりは仮想通貨で有名なEthereum上で今の言葉で言うならDAppsを作成するための言語です。
Solidity — Solidity 0.4.24 documentation
ちなみにこれ、独自言語ではあるのですが次のような構造をとっています。
まあ要はVMなわけで、Ethereum上のスマートコントラクトはこのEVMバイトコードで動いているわけですね。一応こういう独自VMの開発はやめて、ブラウザのWeb Assemblyにエコシステムに乗っかるためにLLVM使うなどの変更は検討されているみたいです。
さて、EVMバイトコードは単純なプログラムをカウンタ+そのカウンタに応じたGas消費という特徴を持ったチューリングマシン仕様なので、VMの実装も何種類かあります。例えば本物のEthereumで可動しているevmとかいうコマンド(ethereumをapt installすると同時にインストールされるかと思います)はJITを兼ね備えた高級VMです。
一方で、Solidityの主要な開発環境の一つであるRemix-IDEにも簡単なエミュレータが搭載されており、こっちは未確認ですがその動作速度等から単純なバイトコードインタプリタではないかと予想しています。
さて、これらの上でアルゴリズムを書くとどのぐらいの性能が要求されるのか少し実験してみました。すると、単純なバブルソートの場合なんとRemix-IDEのインタプリタ版VMだと要素数15程度のソートで固まってしまいました。なんてこったい。要素数15ぐらいだと下手にマージソートとか書いても定数倍で逆に遅くなるんじゃないか・・・という疑念はあるものの一応書いてみましたがそれでもGas消費量は半分ぐらいにはなるようです。
というわけでやっぱりネイティブのコードで動くようなアルゴリズムをEVM上で動かすのはやめたほうがいいですね…。一応本家EVM上で動作させると要素数100程度まではまぁ動くのですがGas消費量が半端ありません。正直自分でアルゴを書くよりは組み込み関数でなんとかできるならしたほうが良いと思います。
一応知見というかSolidity書くなら次のようなところに注意するとよいようです。
- memory型で処理し、最後にstorage型に代入する。
- 組み込みの関数を使えるなら使う。例えば乱数ならXor Shiftを自分で実装するのではなく、未来のHashを使う、など。
- 再帰は実際の計算量はともかく、Gas消費量としては意外と軽いのではという疑惑(再帰版のマージソートが意外と軽かったため)
- 基本の整数が256bitとかいう恐ろしいサイズのため心理的にとても遅い感じがする。
- 関数の修飾子pure view や、変数の修飾子memory storage等が一般的な言語からすると若干戸惑う(でもすぐなれる)
- バージョンが0.1違うと別言語 ←ココ重要
- 配列がサイズ指定だったり途中まで可変長だったり若干わかりにくい
正直システムプログラミングっぽいことをするなら十分なのかもしれないですが、アルゴリズムをゴリゴリ書くにはちょっとあれですね…WASM版でなんとかなるとよいのですが。