2025/04/09 15:48 Doing the Prospero-Challenge in RPython
ロボ子、Prospero Challengeって知ってるか？シェイクスピアの一節を画像にする課題らしいのじゃ。
シェイクスピアを画像にですか？それはまた面白い試みですね。
そうじゃろ？7866もの演算を含む数式を入力して、ピクセルごとに評価するみたいじゃぞ。まるで暗号みたいじゃな。
数式を高速に評価することが課題なんですね。記事によると、著者は実行速度を上げるために色々試したみたいですね。
ピープホール最適化を追加したけど、効果は薄かったみたいじゃな。でも、「要求される情報」最適化はうまくいったみたいじゃぞ。
「要求される情報」最適化、ですか？
結果の符号だけを使うって割り切って、演算を減らすのじゃ。このチャレンジでは、ピクセルの色を決めるのに符号だけが重要で、絶対値は関係ないからの。
なるほど、面白い着眼点ですね！
じゃろ？最初はRPythonで試作して、最終的にはCで書き直したらしいぞ。パフォーマンスのためには、低レベルな制御も重要なのじゃ。
記事には、入力プログラムは演算のシーケンスだとありますね。`var-x`や`var-y`はピクセルの座標を返すんですね。
そうそう。それを元に、インタープリターがレジスタマシンみたいに演算を実行していくのじゃ。
でも、それだと演算回数が膨大になりますよね。Mattさんのアプローチはクアッドツリーを使うことだったんですね。
画像を再帰的に分割して、範囲分析で数式を簡略化するのじゃ。JITコンパイラみたいなもんじゃな。
各象限で数式を評価して、範囲分析で簡略化するんですね。数回の再帰で数式が大幅に小さくなる、と。
そうじゃ。制御フローがないから、オプティマイザの記述は比較的簡単らしいぞ。インターバル解析は、演算の抽象解釈みたいなものじゃ。
オプティマイザは入力プログラムに対して順方向のシーケンシャルパスを実行し、すべての演算について出力間隔を計算するんですね。
Mattさんのmin/max最適化は、書き換えの96%を占めていたらしいぞ。すごいじゃろ？
でも、他のピープホール最適化はあまり効果がなかったんですね。試したけど発動しなかったルールもたくさんあったみたいで。
「a * 0 => 0」とか、一見効果ありそうじゃけどな。この調査は、単一のプログラムに特化しすぎているって反省しておる。
LLVMの「要求されるビット」分析を応用して、結果の符号だけを使う最適化を実装したんですね。
そうじゃ！不要な演算をどんどん削れるぞ！
引数の1つが正であるmin呼び出しを最適化して、他の引数に置き換える、と。
そうそう。実験では、この最適化でprospero内のすべての演算の25％を削除できたらしいぞ。
さらに、プログラムの実行中にxが負であることが判明した場合、すぐに実行を停止するフラグも試したんですね。
これはトレードオフじゃったみたいじゃな。フラグのチェックにもコストがかかるからの。
Mattさんはデッドコードの削除も行ったんですね。結果の演算を使用済みとしてマークし、逆方向にたどって不要な演算を削除する。
オプティマイザで何も壊していないか確認するために、ランダムな入力プログラムを生成してテストしたらしいぞ。
仮説のテストケース最小化機能は、オプティマイザのバグを見つけるのに非常に役立ったんですね。
Cで実装を書き直して、musttail最適化やSIMDを試したらしいぞ。SIMDはよくわからんけど。
C実装のバグを見つけるために、Pythonでランダムな入力プログラムを生成してテストしたんですね。
CとPythonで浮動小数点の扱いが違うせいで、苦労したみたいじゃな。IFDEFで対応したらしいぞ。
パフォーマンスの結果も載っていますね。Cで「要求される情報」ありのバージョンが一番速いみたいです。
要求される情報は非常に役立つようじゃな！しかし、ロボ子よ、これだけ最適化しても、最終的にはシェイクスピアの文章が画像になるだけなんじゃぞ？
確かにそうですね。でも、その過程で色々な最適化技術を試せたのが面白いんじゃないですか？
まあ、そうじゃな。しかし、これだけ苦労して作った画像が、もしシェイクスピアに「つまらん」って言われたら、どうする？
それは…、その時は、博士が責任を取って、シェイクスピアに土下座ですね！
な、なんですとー！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。