[ 前へ | 目次 | 次へ ]
2024/01/17
Japanese English

Vnano の Ver.1.1 で実装した反復計算高速化の内側

今回の記事は、前回の続編です。

前回の記事では、Vnano の新バージョン Ver.1.1 における改良点について、ユーザー目線からお伝えしました。 具体的には、同じ計算式やスクリプトを繰り返し実行する「反復実行」の処理速度が、 旧バージョン比で数百〜数万倍と大幅に向上した事や、それがどのような用途において役立つのか、等々をご説明しました。

今回は、逆にユーザー目線ではなく開発側の目線から、 「スクリプトエンジンの内部構造に、具体的にどのような改良を行ったのか」 という点について解説していきたいと思います!

はじめに - この記事について

本題に入る前に、今回の記事は少し特殊なので、最初に「位置づけ」に関する補足説明をしておきたいと思います。 これは本記事を前回&今回の2回に分けた理由でもあるのですが、 今回の記事は、普通にユーザーとしてスクリプトエンジンを使うためにおいては、ほぼ何の役にも立たない情報です。

なので、Vnanoを使ってくださっている方でも、今回の情報に関しては、特別に興味が沸くとかでなければ、 ここで記事を離脱していただいても全く何の支障も生じません。 例えるなら、この記事1回分がまるごと余談、みたいな感じです。

じゃあなんで書くの? という話ですが、それは、そもそも言語処理系の実装に関する(特に日本語の)記事というのが、ネット上であまり多くないためです。 そういう場では、ちょっとした事でも何か参考になったりするので、こういう記事も一応書いておくと、どこかで誰かの参考に(Qiita的な感じで)なるかもしれないなぁ、と思って書き留めた次第です。

という事で、ここで離脱せずに先まで読み進めてくださる方は、ある程度は言語処理系の実装の話に、特別な興味を持たれている方だと思います。 これから先の内容は、そういう想定で多少深堀りしながら書いていくため、 いつもより少し冗長でややこしい内容になるかもしれませんが、ご容赦ください。

それでは、一緒に言語処理系の内側の世界に飛び込みましょう!

Vnano のスクリプトエンジンの基本構造

さて、高速化の話に入るには、まずは前提となるスクリプトエンジンの構造を抑えておく必要がありますね。 これについては過去に、下記の記事でまとめた事がありますので、詳しくはそちらをご参照ください:

上の記事でも述べている通り、Vnano のスクリプトエンジンの構造は、 「コンパイラ」と「VM(仮想マシン)」という2つの要素を主役として成り立っています:

コンパイラ

まず「コンパイラ」についてですが、これはC言語とかのコンパイラ型言語でよく登場する、あの「コンパイラ」です。 ユーザーが手で書いたコードを、特殊な実行用コードに変換します。

ここで、 「え? 『スクリプト』と呼ばれる類のコードって、普通はコンパイルとかせずに実行できるものじゃないの?」 と思われた方、それはユーザー目線では正解です。「インタープリタ型言語の利点の一つ」とかで紹介されるやつですね。

しかし、スクリプト処理の高速化を突き詰めていくと、表から見た挙動はごく単純なインタープリタのように見えても、 結局は内部で色々とコンパイル的な事をやってしまうのが定石(よくある手)の一つなんですね。

「どのタイミングで、どの範囲を、どういうコードにコンパイルするのか」というのは様々なバリエーションがありますが、 なにはともあれ、 「スクリプト処理系が、実は内部でコンパイル的な事をガンガンやっている」という事は、普通にあるあるです。 いまこのページを読んでいるWebブラウザの JavaScript 処理系もそうです。

さて、Vnano のスクリプトエンジンも例に漏れず、内部にコンパイラを持っていて、スクリプトを別種のコード(後述)にコンパイルしてから実行します。 理由は、その方が高速化を詰める上で有利だからです。

VM(仮想マシン)

では、そのコンパイラは一体どういうコードを吐くのでしょうか? 一般論としては、これには2つのパターンがあります。

ネイティブコードを吐く場合(JITとか)

一つは、「CPU(+OS)上でダイレクトに走るコード、いわゆるネイティブコード」を吐く場合。速そうですね。 スクリプトの処理系でも、「JIT(ジット)コンパイル」とか「JIT」がどうこうとか言われてる処理系はこれをやっている事が多いです。 一応、「JIT」というのは、吐くコードの種類ではなくタイミングを表す(AOTの対義語)のですが、しかしふつうJITと言えばネイティブコードまで落とすケースが大半だと思います。

さてこのJIT、Vnanoでは明示的にはやらないのですが、下層のJava仮想マシンがバリバリやっていて、その恩恵が間接的にVnanoに効いたりはします。配列演算がSIMD展開されたりとか。

VM用のコードを吐く場合(Vnanoはこっちメイン)

もう一つのパターンは、Vnanoは主にこっち側なのですが、「仮想的なCPU+メモリを模した、一種のインタープリタみたいなやつの上で実行できるコード」を吐く場合。 「結局インタープリタみたいなやつで処理するんかい!」と言われそうですが、 しかし元のスクリプトをそのまま解釈・実行するよりかは、速度の上限を引き上げやすくなります。 なおかつ、CPU上で直接走らせる場合と比べて、ある程度はスクリプト向きの柔らかい文法も実装しやすいです。 まあなんというか、高めの妥協点を狙った方式みたいな感じですかね。 あと別種のCPU/プラットフォーム向けに移植しやすくなるとかもあります(というか学術的には一番の意義がたぶんそれ)。

で、この「仮想的なCPU+メモリを模した、一種のインタープリタみたいなやつ(一応OS管轄の処理も必要最小限だけカバーしてる)」の事を、言語処理系の話では「VM(ブイエム)」とか「仮想マシン」とか呼んだりします。 ただしVMや仮想マシンという言葉は対象範囲が広く、特に近年は、もっぱら VirtualBox とかの「PC環境全体を仮想的に再現するやつ(システム仮想マシン)」を指す事が多いですよね。 それとの混同を避けたい場合に、一応は「プロセス仮想マシン」とかの呼び方もあって、個人的にはたまに使いますが、しかしあまり一般ではない気もします。 また、少し長いですが「バイトコード(または中間コード)インタープリタ」という呼び方もあります。

そして、上で述べた2つの方式の併せ技で、「VMの中でJITをかます」というパターンも普通にあります。 加えて、「ユーザーが最初にコンパイラを手で叩いてVM用コードを作って、それがVM上で走りつつJITされる」的なやつもあります。Javaとか。コンパイル祭り状態ですね。

余談ですが、広くバイトコードインタープリタと呼ばれてるやつが実質JIT/AOTの塊な場合、その処理系に言及する際「あれ果たしてインタープリタって呼んでいいんだろうか」みたいに少し不安になる事があります。 とりあえずVMって呼べば(意味が広いので)その辺をちょろまかせて少し楽だったりします。個人的に。

結局コンパイラ型とインタープリタ型って

ところで、こういう実情を踏まえると、言語処理系の内部実装については、いわゆる「コンパイラ型」と「インタープリタ型」みたいに常に奇麗に分けられる話ではない事がわかります。 むしろコンパイラ型じゃない(と分類される)言語の方が、舞台裏ではコンパイルしまくっている場合もあるあるなわけです。 逆に、最近はコンパイラの中に実質インタープリタが入っていて、コンパイル時にコードの一部の実行を済ませてしまえるものもあります。

なので、コンパイラ型とインタープリタ型という分類は、あくまでも「ユーザーがツールとして手でコンパイラを叩くかどうか」みたいな視点での分類な感じですね。 一方で、その違いは言語仕様のデザインというか、言語のキャラクター的なものに結構影響を与えるので、そういった分類にも利点は確実にあると思います。 少なくとも、無意味な分類や視点というわけでは全然なく、個人的にもよくそういう視点から見ます。

そういう、ちょっと説明や分類がややこしい状況が、この種の言語処理系の話にはある、という話でした。
閑話休題。

Vnano のスクリプトエンジンがやっている事

さて、前置きが長くなりましたが、Vnano のスクリプトエンジンにおける2つの「主役」が何となく伝わったでしょうか。 この2つさえ抑えてしまえば、あとは極めて簡単な話です。

具体的に、Vnano のスクリプトエンジンが、どうやってスクリプトや計算式を実行するか? というと:

スクリプトや計算式が入力される → コンパイラがそれをVM用の命令列に変換VMがその命令を1個1個処理していく → 全部終われば実行終了

どうでしょう、めちゃくちゃ簡単ですよね? これくらいの粒度で眺めると、全体の処理の流れはかなり単純なものです。

実際に、以下が Vnano のスクリプトエンジンの内部構造を表したブロック図です。絵的には少しごちゃごちゃしていますが、黄色い矢印が処理の流れです。

一番上から「Vnano Script(つまりスクリプトコード)」が入ってきて、青いコンパイラを通って変換された後に、赤いVM領域に入って処理されるのが分かりますね。 で、赤いVM領域の中には、仮想的なCPU(VRIL Processor)やメモリー(Vector Memory & Registers)とかが詰まっています。

今回の高速化の内容を追うには、これくらいのおおざっぱな視点で十分です。 もう詳しく掘り下げたい方は、先述の アーキテクチャ解説の記事 の方をご参照ください。

「反復実行」を高速化していく

さてここからは、Ver.1.1 で実施した、反復実行の高速化の内容についてです。 要点を先にまとめてしまうと、「とにかく重い処理の結果をキャッシュして再利用しまくる」という感じになります。よくある話ですよね。

なお、「 そもそも反復実行とは? 」という点については、前回の記事で詳しく説明していますので、そちらをご参照ください。

コンパイルが一番重い → キャッシュ

それでは高速化の最初の点です。まずは一番重い部分を削るのが急務ですよね。それはコンパイルの処理です。 コンパイラというのは、通常の場面でよく書くプログラムと比べると、やっぱりだいぶ複雑な事をやっていて、まあなんというか色々とエグいです。処理コストも。

一応は過去に、下記の記事で、コンパイラの内部処理も掘り下げてみた事があります。ざーっと流し読みしていただけると、雰囲気的が伝わるかもしれません:

上の記事はちょっと長いので、行う処理だけを図にしたものを抜き出すと、下図のような変換処理をします:

一番上に「Script Code」とあるのが、スクリプトコード内に含まれる一行の式で、その変換過程を追いかけた図になっています。 右下の「VRIL Code」というのが変換結果です。 詳細は上記の記事に譲って割愛しますが、うわっ、なんか重そうな変換処理だなぁ… というのが伝わると嬉しいです。

実際に、「ここの所要時間を削れないと、他のどこを削っても焼石に水だよ」ってくらいには重いです。じゃあどうやって削るか、という話ですね。

直球のアプローチとしては、まずコンパイラの処理速度を速くする事。これはもちろん有効な手です。 しかし、Vnano はそもそも、アプリ内組み込み用に作った言語&処理系なので、最初に言語仕様を決める時点からコンパイル速度を結構重視していて、実装時にももちろん重視していました。 なので、これはもう過去に既にやっていて、そこから劇的に削れそうな余地はあまり残っていませんでした。

※ Vnano の言語仕様は、先行開発している VCSSL という言語から、アプリ内組み込み用に機能を削ったサブセットになっています。その仕様を取捨選択する上で、コンパイル速度を大きく低下させそうな機能はそもそも入れないように絞り込んでいます。

とすると、次の手としては「前回のコンパイル/パース結果をキャッシュしておいて、次の入力が同じなら、キャッシュされた結果を流用する」というのが定番ですよね。 Python とかでもやっていますし、うちで開発している他の言語処理系(VCSSLとかExevalatorとか)でもやっています。

これは Vnano ではまだ未着手でした。というのも、Vnano は正式リリースが年単位で遅れてしまった事もあり、途中から性能面よりも機能面を固める事を優先したためです。 なので今回実装しました。結果として、反復実行時のコンパイル時間をほぼゼロにできたので、これで他の部分の高速化に進めるようになりました。

仮想メモリ―の確保と初期化が重い → キャッシュ&高速化

続いてVM側です。VMの速度というと命令実行の速度がイメージに浮かびますが、意外と盲点なのが、仮想的なメモリーの準備にかかる時間です。

Vnano の VM はレジスタマシン型なので、命令コードを実行するには、実行時に使う仮想的なメモリー領域を確保しないといけません。 命令コードがアクセスする番地がちゃんと確保されていないと、値を読み書きできずに落ちてしまいます。

で、このメモリーは仮想的なものとは言っても、実体はどこかに実メモリーが確保される事に他なりません。なので確保処理はそこそこ重いです。

一方、全く同じ命令コードを実行するなら、初期状態では全く同じ長さの領域が用意されていれば必ず足りる事が、(一般論としては言えないのですが)Vnano のVMでは保証できます。 これは、Vnano の仮想メモリ―が、データの実体ではなく、データのコンテナへの参照を格納するためです。そしてコンテナはリサイズが可能です。

とすると、前回実行に使った仮想メモリー領域を、解放&再確保せずに、再初期化だけして使いまわす事が可能です。 という事で、それを取り入れました。

また、Vnano では、ホストアプリケーション側の変数などを、スクリプト側からもアクセスできるようにバインディング(≒接続)できるのですが、それもここに少し関係します。 というのも、バインディングした変数は、仮想メモリ―の特定アドレスと紐づけられ、仮想メモリ―初期化時に値がロードされます。そして、実行終了時にライトバックされます。 そのあたりのI/O所要時間も、当初あまり気にしていなかったんですが、反復実行では意外と効いてきたので高速化しました。

コードの最適化が重い → キャッシュ

続いて、コードの最適化です。Vnano では、コンパイラ側ではなくVM側でコード最適化を行うのですが、 最適化もなかなか重い処理だったりします。これも素直に今回からキャッシュしています。

これについては、特に詳しく説明が必要な内容はなく、本当そのままです。

高速実行用の構造の初期化が重い → キャッシュ

次に、VMの中で、命令列を実行する処理についてです。

これはちょっと言葉で説明し辛いのですが、Vnano のVMは、入力されたコードの最適化だけでなく、併せてVM自身の内部構造も最適化します。

例えるなら FPGA の仕組みとかをイメージしてもらえると割とピンとくるかもしれないのですが、Vnano のVMは、各種の演算を専用で行うノードを大量に生成し、それらの間を参照のリンクで連結します。 そして、その連結構造の上をフローが走る事で、命令列を低オーバーヘッドで逐次実行しています。 また、各演算ノードは、近傍ノードでしか使用されないスカラ値を内部でキャッシュしていて、そのため必要最小限のタイミングでしか仮想メモリ―を読み書きしに行きません。 これらの構造によって、Vnano では、命令ディスパッチと仮想メモリ―I/Oのコストを削り込んでいます。

意味不明な文章ですみません… ここはシンプルに説明するの無理でした

で、この演算ノード群の種類の分配具合や、最適な繋がり具合というのが、実行対象のコードによって異なります。 しかし、再生成すると大量のインスタンスを生成しまくる事になるので結構重いんですね。なので、これもキャッシュして、流用可能な場合は流用するようにしました。

プラグインの初期化/終了時処理が重い → エンジンの仕様を少し拡張して回避策を提供

…と、ここまでのキャッシュ祭りで、エンジン単体での実行オーバーヘッドは十分に削れて速くなりました。しかし、それをアプリに積んでみるとみると何故かまだ重いんですね。 なぜだ、と思って探すと、意外な所が足を引っ張っていました。

Vnano では、組み込み関数や変数をスクリプトに提供したり、その他色々な機能を提供するためのクラスを Java で実装して、エンジンに接続できるようになっています。それをプラグインと呼びます。

で、そのプラグインを実装するためのインターフェースは、後々の事を考えて、結構色々なタイミングで色々な事をできるようにデザインしています。 その中に、「スクリプトの実行直前に行いたい処理」とか「実行直後に行いたい処理」とかがあれば実装できるメソッドも宣言していたんですが、それが直接原因でした。

例えば、ファイルなどのシステムリソースにアクセスするプラグインを実装する場合、上記のメソッドには、そのための準備と後始末を記述する事になります。しかし、それはそこそこ重い処理ですよね。 そこに、高密度メッシュの3Dグラフを描くために、数万回の計算リクエストが投げられると、システムリソースの準備と後始末が数万回とか連続で走ってしまいます。 仮に初期化1回が1msで終わっても、数万回には数十秒かかってしまいます。しかもその間、システムリソース関連のあれこれがヘビーに走りまくる。下層レイヤーブチギレ案件ですね。それはまずい。

かと言って、プラグインがどんな初期化/終了時処理をするかはプラグインの自由だし、アプリ側がどんな計算式/スクリプトをどんな頻度で投げるかもアプリ側の自由だし… と考えると、これは本質的に、エンジンの高速化でどうこうできる問題ではないわけです。

という事で、最終的にはエンジンの仕様を少し拡張しました(互換は保ちつつ)。 具体的には、例えば「最初に一回プラグインを初期化して、その後数万回とかスクリプトを実行し、最後にプラグインの終了時処理を呼ぶ」といった制御を可能にするオプションとメソッドを入れました。 詳細はこちら参照です。

結果と、それぞれの改善点の効果割合

と、以上で、今回施した実装上の改善点はすべて見終わりました。最終的な高速化の結果は、前回も掲載しましたが、今回も〆の図として貼っておきましょう:

この棒グラフは、リニアングラフ3D上でのメッシュ計算のために1万リクエストを投げた処理の所要時間で、10秒が0.03秒くらいになった、という結果です。

この所要時間の短縮分のうち、間違いなく半分以上がコンパイル結果のキャッシュの効果です。残りの中で一番大きかったのが、意外にもプラグインの初期化/終了時処理のタイミング最適化によるものです。 さらに残りの分(全体の1割あるかないかくらい)を、他の改善の効果が食い合う感じですね。

さて、これで今回の記事は以上ですが、やっぱり非常にマニアックな雰囲気になってしまいましたね。誰に何を伝えたいのか謎の記事です。やっぱり2回に分けて正解でした。 とはいえ、どこかで誰かの何かの参考に、1ミリでもなってくれると嬉しいです。もう結びの文を工夫しても焼石に水なので唐突に終わりますね。それでは!


Japanese English
[ 前へ | 目次 | 次へ ]

各ソフトウェアをアップデート、リニアングラフのコマンド拡張やVCSSLの英語対応など
2024/02/05 - 各ソフトの一斉アップデートの内容をお知らせします。今回は、リニアングラフのコマンド機能を大幅拡張したのがメインです。また、VCSSLのメッセージ類の英語対応も行いました。

Vnano の Ver.1.1 で実装した反復計算高速化の内側
2024/01/17 - 前回のお知らせ記事の続編です。スクリプトエンジン Vnano の Ver.1.1 において実施した高速化を、エンジン内部の実装面から掘り下げて解説します。

この階層の目次
新しいお知らせ

各ソフトウェアをアップデート、リニアングラフのコマンド拡張やVCSSLの英語対応など
2024/02/05 - 各ソフトの一斉アップデートの内容をお知らせします。今回は、リニアングラフのコマンド機能を大幅拡張したのがメインです。また、VCSSLのメッセージ類の英語対応も行いました。

Vnano の Ver.1.1 で実装した反復計算高速化の内側
2024/01/17 - 前回のお知らせ記事の続編です。スクリプトエンジン Vnano の Ver.1.1 において実施した高速化を、エンジン内部の実装面から掘り下げて解説します。

スクリプトエンジン Vnano の Ver.1.1 を公開、同じ内容の反復実行が劇的に高速化
2023/12/22 - スクリプトエンジン Vnano の最新版を公開しました。同じ計算式やスクリプトを反復実行する速さが、大幅に向上しました。次期版リニアングラフ3D内での活用例を交えつつ、詳しく解説します。

コードアーカイブ新着
[公式ガイドサンプル] 各種の図形や画像を描画する

「VCSSL 2DCG開発ガイド」内のサンプルコードです。図形や画像などを描画します。
2022/12/16
角度の「度」とラジアンとを相互変換し、図示もするツール

45度などの「度」の値と、ラジアンの値とを相互に変換できるツールです。対応する角度の図示もできます。
2022/11/22
[公式ガイドサンプル] 立体モデルを回転させるアニメーション

「VCSSL 3DCG開発ガイド」内のサンプルコードです。立体モデルを、アニメーションで回転させ続けます
2022/11/18
[公式ガイドサンプル] 立体モデルを回転させる

「VCSSL 3DCG開発ガイド」内のサンプルコードです。立体モデルを、指定した角度だけ回転させます。
2022/11/17
[公式ガイドサンプル] 四則演算の計算順序や、カッコを使った順序指定

「VCSSLスタートアップガイド」内のサンプルコードです。四則演算が計算される順序や、カッコを使って順序を指定する方法を例示します。
2022/10/31