Ray tracer на Brainfuck: 23 МБ коду і один піксель за хвилину

Автор блогу epestr.com сприйняв рядок із посібника CMake як виклик: ray tracer-и навіть писали мовою CMake Language, щоправда, це не рекомендована практика. Він уже писав ray tracer і переписував його під GPU, тож обрав Brainfuck, який називає найпростішою мовою, яку знає, і взявся відтворити зображення з розділу Metal підручника Ray Tracing in One Weekend. Код опубліковано на GitHub як mTvare6/rayfuck.

Вісім команд і одна стрічка

У Brainfuck є вісім операцій і єдина структура даних: нескінченна в один бік стрічка комірок, кожна з яких зберігає один беззнаковий байт. Жоден регістр не ширший за комірку, жодна інструкція не діє на дві комірки одразу, а додавання й множення інструкціями не є. Тому дійсні числа довелося кодувати вручну: кожне значення займає чотири комірки у форматі зі знаком Q16.16, 16 бітів на цілу частину і 16 на дробову, що дає роздільність 1/2^16 і діапазон приблизно [-2^15, 2^15). Дешевший Q8.8 виявився завузьким, бо сфера, що править за землю, має радіус 1000, аби здаватися пласкою.

Арифметика з нуля

23 мегабайти Brainfuck ніхто не писав руками: програму перетворюють на SSA-подібну форму, а потім розбирають у невелику проміжну DSL із тридцятьма операціями на кшталт copy, mul, sqrt, if і while. Основну роботу виконують два примітиви: move ([->+<]) переносить значення комірки в сусідню, copy ([->+>+<<]) залишає його у двох. Множення це повторюване додавання в межах чотирьох комірок, а ділення відбувається як шкільне ділення стовпчиком за основою 256: дільник віднімається щонайбільше 255 разів на комірку.

Математичну бібліотеку зібрали з тих самих блоків. Випадкові числа дає крихітний генератор A = (5*A + 1) % 256, чий повний період у 256 значень достатній для згладжування методом супердискретизації. Для квадратного кореня метод Герона відкинули через ділення, а ряд Тейлора погано працював нижче 0,305, тож автор узяв корінь через ділення стовпчиком.

23 МБ, один піксель за хвилину

Готова програма важить 23 МБ, тобто більше за зображення, яке малює (близько 0,9 МБ), і автор зауважує, що для стиснення Brainfuck не годиться. Швидкість становить близько 100 обчислень променів за хвилину, тобто один піксель за хвилину, тож зображення 400×225 на його ноутбуці тривало б приблизно 62,5 дня. На момент написання з приблизно 90 000 пікселів було готово 1229, і лише 10 з них відрізнялися від еталона на C, здебільшого на одиницю.

Після коментаря в гілці на Reddit про fork/join автор натомість поліпшив JIT-інтерпретатор і отримав значне прискорення; справжній рендер, за його словами, тепер скидається на картину Ван Гога, ймовірно через похибки точності.