Brainfuckでレイトレーサーを書いた
I wrote a ray tracer in Brainfuck (epestr.com)
要約
著者は、CMake言語でレイトレーサーが書けるという主張に触発され、極めてシンプルなプログラミング言語であるBrainfuckでレイトレーサーを実装する挑戦をしました。この記事では、Brainfuckの基本的な8つの命令と無限のテープという制約の中で、Qフォーマット数値表現、乱数生成、平方根計算といったレイトレーシングに必要な要素をどのように実装したか、その過程と工夫が詳細に解説されています。
全文翻訳
Writing a ray tracer in Brainfuck
C++でのシステムプログラミングコンペティションの準備をしていた頃、CMakeを再学習し始めました。その過程で、チュートリアルの中に興味深い主張を見つけました。
多くの場合、正しいアプローチは、ビルドプロセスの一部としてそのツールを呼び出す方法をCMakeに教えるために、汎用プログラミング言語でツールを書くことです。コード生成、暗号署名ユーティリティ、さらにはレイトレーサーさえもCMake言語で書かれていますが、これは推奨される実践ではありません。
以前にレイトレーサーを書き、それをGPU向けに書き直した経験があったため、この記述は私の目に留まり、さらに優れたレイトレーサー実装言語は何かと考えさせられました。
前回の書き直しでは、第一原理に基づいたアプローチがほとんどなく、比較的高度なAPIセットに大きく依存するコードを書きました。そのため、私が知っている中で最もシンプルな言語であるBFを選びました。なぜなら、シンプルな言語は明らかに非常にシンプルなコードベースにつながるからです。実際、BFのコードベースは通常、数行しかありません。さらに、READMEにあるMullerのコメント[^1]が、反例を示したいという私の欲求を掻き立てました。
コードはmTvare6/rayfuck[^2]で入手できます。
Primer
BFは、わずか8つの操作と1つの「データ構造」(各u8を格納できる片側無限のテープ)からなる、明らかにシンプルな言語です。
>という文字を見ると、テープ上のセルを指すデータポインタが右に移動し、<では逆に左に移動します。
I/Oは,と.で管理されます。前者はデータポインタが指すセルにバイトを入力として格納し、後者はそれを表示します。
I/O以外の値を変更できる唯一のプリミティブは、データポインタでのインクリメントとデクリメントであり、それぞれ+と-で行います。
その限界は明白でしょう。他のマシンが持つような$n>1$レジスタはなく、複数のセルを操作する命令もなく、加算や乗算のための命令もありません。
BFをチューリング完全にするための最後の要素は、[と]で書かれるループです。[トークンに遭遇すると、ランタイムはデータポインタが指すセルをチェックします。ゼロであれば、対応する]の後に実行をジャンプさせますが、そうでなければループに入ります。]では、セルがゼロでない場合は対応する[に戻り、そうでなければループを終了します。
簡単な演習としてcatプログラムを書いてみましょう。5文字だけで書いてみて、その環境について直感を得てください。
Premeditation
これを始める前に、以前に読んだことを元に、結果や実装の詳細を一切調べずに、可能な限り第一原理から書き下すことにしました。スコープを最小限に抑え、プログラムを明らかにレイトレーサーにするために、RIW[^3]のMetalセクションでレンダリングされたものと全く同じ画像をレンダリングすることにしました。
Cコードはそれでも少し複雑すぎたため、Cパーサーを書くことは明らかにスコープ外でした。メンテナンスされていないCパーサーを書くことは、AnthropicのCコンパイラ[^4]で処理する方が良いでしょう。
すべてのdoubleは、ビットの一部を小数部、残りを整数部として組み合わせたセルで表現することにしました。これにより、固定小数点がセル間に配置されます。[^1] このアプローチは、doubleだけでなく、boolなどの他のデータ型にも適用できます。後にこれがQフォーマットと呼ばれることを知りました。より安価な符号付きQ8.8を使用すると、$1/256$の解像度と約${-128,128)$の範囲が得られます。しかし、明らかにそれは十分ではありません。シーンの地面に使用された球体が平坦に見えるためには$r=1000$が必要だったため、より高価な符号付きQ16.16フォーマットを採用しました。これは$1/2^{16}$の解像度と${-2^{15},2^{15})$の範囲を持ち、十分です。
コードをSSAライクな形式に変換することにしました。ここでは、再帰的なコードを反復的にし、関数で定義された変数は、名前のアドレスルックアップ中の名前の衝突を避けるために、ハンガリアン記法でプレフィックスを付けます。[^2] この変換のみをLLMの仕事とし、残りはプロジェクトに設定した第一原理の制約に従うことにしました。
同様に、パーシングとコード生成を分離することが必要だと判断し、複雑さを2つのコード領域に分割し、中間的な「DSL」をIRとして使用しました。このDSLには、abs、add、and、call、copy、div、else、end、eq、func、ge、gt、if、int、le、lt、mul、neg、not、or、print2、print3、set、sqrt、sub、text、var、whileのような単純な操作が含まれていました。
次にトリッキーな部分となったのは、いくつかのライブラリコールです。使用したのはsqrt、rand、absです。当初は以下のような2状態ソリューションの使用を計画していました。
$$ \begin{aligned} A &\gets (A-B) \bmod 256,\ B &\gets (B+1) \bmod 256, \end{aligned} $$
または、$p$を素数として$B\gets(B+A+p)\bmod256$ですが、これらのバリアントのほとんどは周期が短いです。このユースケースでは十分な周期を持つ、よりシンプルな
$$ A\gets(5A+1)\bmod256, $$
を採用することにしました。これは、完全な256値のシーケンスまで繰り返されないことが保証されているため、このユースケースでは悪くありません。[^5] ここでのユースケースはスーパーサンプリングアンチエイリアシングであり、暗号学的に強力なランダム性よりも、わずかに異なるサンプル位置のストリームを必要とします。
sqrtには、ヘロンの公式[^3]という明白な候補があります。前述のCMakeチュートリアルでヘロンの公式を思い出しました。しかし、除算を含むため、性能が悪いことは明らかでした。繰り返し減算は、生成されるコードは小さくなりますが、それでも実行するには比較的コストがかかります。[^4] 生成されるコードが小さい方が望ましいのは、インタープリタが移動するコードが少なくなるためです。他の候補としては、テイラー級数と「School Method」(筆算を伴う)がありました。
$$ \begin{aligned} \sqrt{1+x} &\approx 1+\frac{x}{2}-\frac{x^2}{8},\ y &= 2^{16}x,\ \frac{\sqrt{2^{16}+y}}{2^8} &\approx 1+\frac{y}{2^{17}}-\frac{y^2}{2^{35}},\ \frac{\sqrt y}{2^8} &\approx 1+\frac{y-2^{16}}{2^{17}}-\frac{(y-2^{16})^2}{2^{35}}. \end{aligned} $$
Desmosでこれをプロットしたところ、エンコードされた値が20k未満(つまり、約0.305未満)ではフィットが悪く、これは非常に重要な領域でした。そのため、筆算による方法が残りましたが、これは非常にシンプルでした。実数値がxの場合、表現される値は次のようになります。
$$ N=x,2^{16}. $$
$\sqrt{x}$を表現するには、次のようになります。
$$ \begin{aligned} N_0 &= \sqrt{x},2^{16},\ \operatorname{isqrt}(N) &= \sqrt{x},2^8,\ \operatorname{isqrt}(2^{16}N) &= \sqrt{x},2^{16}=N_0. \end{aligned} $$
ここでisqrtが正当化されるのは、エンコードされた結果の1の違いが、デコードされた平方根を$1/2^{16}$、つまり約$0.00001526$未満変化させるためです。
そして最後に、変数マップ全体と対応するBFアドレスは辞書で管理されます。
Implementation
理論的な部分が設定されたので、あとは明らかにシンプルな実装の詳細だけが残りました。重要なプリミティブはmoveとcopyでした。
[a, 0]
Moveは、値を継続的に減らしていき、初期データポインタのセルがゼロになるまで、他のセルを毎回等しくインクリメントします。
[ # start loop
- # decrement
>+ # move right and increment
< # come back, this cell is used to control the loop
]
ワンライナーとして
[->+<]
そしてコピーは以下のように動作します。この配列から開始します。
[a, 0, 0]
コードを使用します。
[->+>+<<]
これを以下のように変換します。
[0, a, a]
そして今、必要であれば、末尾のaを内側に移動できます。
加算、そして後の除算は一時値の繰り返し使用を伴うため、データポインタの移動をあまり避けるために値が近くにある必要があります。そのため、map内の各値には、一時変数スロットも近くにあります。これらは、コピーをまとめた状態に保つためのキャリーセルやその他のスクラッチスペースも提供します。
乗算も同様に単純で、各セルを乗算し、結果を格納してから後で合計します。乗算ステップは、繰り返し加算によって処理されます。2つのセルを乗算するために、一方を一時的な場所にコピーして外側のループとして使用し、もう一方を各イテレーションで内側のループとしてコピーします。内側のループの各イテレーションは、結果を1回インクリメントします。
[a, b, a->0, b->0, a + ... + a]
ここでaは毎回なくなり、aがゼロになったときにbがデクリメントされ、b個のaのコピーが生成されます。
4セル値の場合、一方の各セルともう一方の各セルがペアになります。セルiとjの乗算は、8セル結果のi+jに追加されます。
[a0, a1, a2, a3] * [b0, b1, b2, b3]
result[i+j] += a_i*b_j
両方の入力はすでに表現に$2^{16}$を含んでいたため、結果をコピーバックする際に下位2セルは破棄されます。
$$ \begin{aligned} N_1 &= x_1,2^{16},\ N_2 &= x_2,2^{16},\ \frac{N_1N_2}{2^{16}} &= N=(x_1x_2)2^{16}. \end{aligned} $$
除算はやや直接的ではありませんでしたが、手動の筆算と同じ方法で実行できました。被除数は最上位セルから読み取られ、各ステップで古い剰余が次のセルに繰り越されます。
R = R * 10 + A[next] # school
R = R * 256 + A[next] # here
次に、この剰余から除数を繰り返し減算し、結果セルに1を加えます。剰余が負になったら、ステップを元に戻し、次のセルに進みます。
while R >= D:
R -= D
result += 1
これはセルごとに最大255回の減算を必要とし、セル間で除算し、後でそれらを結合します。
表現が乗算中に右にシフトして拡大するのと同じように、除算は左へのシフトによって情報が失われるため、除算前に表現のシフトが必要になります。
$$ \begin{aligned} N_1 &= x_1,2^{16},\ N_2 &= x_2,2^{16},\ \frac{N_1}{N_2},2^{16} &= \frac{x_1}{x_2},2^{16} && \text{bits already lost},\ \frac{N_1,2^{16}}{N_2} &= \frac{x_1}{x_2},2^{16}. \end{aligned} $$
これらの操作全体を通して、まず符号が削除され、入力が1つだけ負の場合に結果が負になります。
比較は同じ小さな操作を共有します。2つのセルは、少なくとも1つがゼロになるまで一緒にデクリメントされ、差が生じるか一時的なコピーが完全にゼロになるまで続きます。最上位セルに$2^7$を加えるというマイナーな処理がありましたが、そうでなければ負の数はバイトとしてそのまま見た場合に値が高くなるためです。
00 ... 7f -> positive half
80 ... ff -> negative half
128を加えてラップオーバーした後
80 ... ff -> positive half
00 ... 7f -> negative half
ブールチェックはセルを読み取り、Cの真偽値の傾向を考慮して、いずれかのセルがゼロでない場合に結果を1に設定することを含みます。構築された表現では、最下位ビットが真で、すべてのビットが偽の場合はゼロになります。and、or、notのようなブール演算は、そのビット表現を使用して機能しました。
否定は$-x=\mathord{\sim}x+1$のトリックを使用します。各セル$x$は補完され、次に最下位セルに1が追加され、繰り越されます。[^6] 各セルは1バイトなので、セルの補完は$255-x$の計算と同等です。absは最後のセルの最上位ビットのみをチェックし、設定されている場合はこの否定を実行します。
関数ごとの変数名のスコープ設定とSSAスタイルのコードの使用という以前の決定により、関数は非常に簡単になりました。コード生成は関数本体をその名前の下に記録し、call funcが見られたときにインラインで発行します。
ループが与えられた場合、ifは簡単でした。
[- body ]
elseの場合、別のフラグが1で開始され、最初のボディによってクリアされます。
whileも同様です。
condition
[
body
move to condition and calculate
]
Artifact
[画像: C version's output]
プログラムは最終的に23MBになり、圧縮技術としてはかなり貧弱な選択肢となりました。[^7] 意図されていた画像は約0.9MBでした。
粗い計算によると、毎分100回のレイ計算、つまり1分あたり1ピクセルを行いました。画像は400x225ピクセルなので、私の最初の見積もりでは、最適化なしでラップトップで約62.5日かかるはずでしたが、空しか見えていないことに気づき、球体の周りのバウンスがETAを大幅に遅らせるだろうと思いました。したがって、上の画像は、Cコードを使用してレンダリングされたものの近似です。執筆時点で生成された1229ピクセルのうち、[^8] 完全な400x225レンダリングには90,000ピクセルが含まれます。10ピクセルのみが異なり、ほとんどが値1の違いです。
いくつかの最適化が可能です。地面をより悪く近似できる場合、セル数を減らすために精度を失うのが最初の選択肢です。ランダムベクトルの正規化ステップもスキップできますが、これは散乱分布を変更するため、ここで再現しようとしたコードの正確なビットを実行しなくなります。
Update
私のRedditスレッド[^5]へのコメントで、フォーク/ジョインプリミティブでどのように改善できるかという質問がありました。この挑戦は興味深く、JITインタープリタを改善することに神経を奪われ、そのパフォーマンスが劇的に向上しました。[^9] JITコンパイラに関する以前の実験とそこから学んだことが、この作業に役立ちました。実際のレンダリングは、おそらく精度エラーのため、ゴッホの絵画のように見えます。
[画像: BF version's output]