Brainfuck'ta ray tracer: 23MB'lık program dakikada bir piksel çiziyor

epestr.com blogunun yazarı, CMake kılavuzundaki bir satırı meydan okuma olarak kabul etti: ray tracer'lar CMake Language ile bile yazılmış, ancak bu önerilen bir yöntem değil. Daha önce bir ray tracer yazmış ve onu GPU için yeniden yazmıştı; bu yüzden bildiği en basit dil dediği Brainfuck'a yöneldi ve Ray Tracing in One Weekend dizisinin Metal bölümündeki görüntüyü yeniden üretmeyi hedefledi. Kod GitHub'da mTvare6/rayfuck adıyla yayımlandı.

Sekiz komut, tek bir şerit

Brainfuck sekiz işlem ve tek bir veri yapısı sunar: her hücresinde işaretsiz bir bayt tutan sonsuz bir şerit. Tek hücreden geniş kayıt yoktur, hiçbir komut aynı anda iki hücreye dokunmaz, toplama ve çarpma komut değildir. Bu yüzden gerçek sayılar elle kodlandı: her değer işaretli Q16.16 sabit noktalı biçimde dört hücre kaplar, 16 bit tam kısım ve 16 bit kesir, yani 1/2^16 çözünürlük ve yaklaşık [-2^15, 2^15) aralığı. Daha ucuz Q8.8 fazla dar bulundu, çünkü zemin olarak kullanılan kürenin düz görünmesi için yarıçapı 1000 olmalıydı.

Aritmetiği sıfırdan kurmak

23 megabaytlık Brainfuck elle yazılmadı: program SSA benzeri bir biçime dönüştürülüyor, ardından copy, mul, sqrt, if ve while gibi otuz kadar işlem içeren küçük bir ara DSL'e ayrıştırılıyor. İşin çoğunu iki temel işlem yapıyor: move ([->+<]) bir hücrenin değerini komşusuna taşır, copy ([->+>+<<]) ise değeri iki hücrede bırakır. Çarpma dört hücre boyunca tekrarlı toplamadır, bölme ise 256 tabanında okul usulü uzun bölmeyle yapılır: bölen hücre başına en fazla 255 kez çıkarılır.

Matematik kütüphanesi de aynı yapı taşlarından kuruldu. Rastgele sayılar küçük bir üreteçten geliyor: A = (5*A + 1) % 256; 256 değerlik tam periyodu sahnedeki süperörnekleme için yeterli. Karekök için Heron yöntemi bölme yüzünden, Taylor serisi ise 0,305 altında kötü uyum verdiği için elendi; yazar uzun bölmeye dayalı karekök kullandı.

Dakikada bir piksel

Bitmiş program 23MB, yani çizdiği görüntüden büyük (görüntü yaklaşık 0,9MB); yazar bu yüzden Brainfuck'ın kötü bir sıkıştırma yöntemi olduğunu belirtiyor. Hız dakikada yaklaşık 100 ışın hesabı, yani dakikada bir piksel, dolayısıyla 400×225 görüntü dizüstü bilgisayarında tahminen 62,5 gün sürerdi. Yazının yazıldığı sırada yaklaşık 90.000 pikselin 1229'u üretilmişti ve bunlardan yalnızca 10'u C referansından farklıydı, çoğunlukla bir birim.

Reddit başlığındaki bir yorum fork/join temel işlemlerini önerince yazar bunun yerine JIT yorumlayıcısını iyileştirdi ve büyük bir hız artışı bildirdi; gerçek render, ona göre, muhtemelen hassasiyet hataları yüzünden biraz Van Gogh tablosuna benziyor.