Brainfuck으로 레이 트레이서를 만들기

AI 요약

C++ 시스템 프로그래밍 대회를 준비하며 CMake를 다시 살펴보던 저자는, 빌드 과정에서 레이 트레이서 같은 도구를 CMake 언어로 작성하는 방식은 권장하지 않는다는 설명을 읽었습니다. 그렇다면 더 단순한 언어로 레이 트레이서를 만들면 어떨까 하는 생각에 Brainfuck을 골랐습니다. 이미 C와 GPU로 레이 트레이서를 구현한 경험이 있었지만, 이번에는 기존 구현을 참고하지 않고 가능한 한 처음부터 설계했습니다. 결과물은 GitHub 저장소 mTvare6/rayfuck에 공개했습니다.

Brainfuck에서 수치 표현하기

Brainfuck에는 여덟 가지 명령과 한쪽으로 무한히 이어지는 셀 테이프만 있습니다. 셀 하나에는 8비트 값이 들어갑니다. 포인터 이동은 <와 >, 입력과 출력은 ,와 ., 셀 값 증감은 -와 +로 처리합니다. [와 ]는 현재 셀 값에 따라 반복을 시작하거나 끝내는 명령입니다. 레지스터나 덧셈·곱셈 명령은 없지만, 반복문을 조합하면 튜링 완전한 프로그램을 만들 수 있습니다.

저자는 장면을 기존 Metal 레이 트레이서 예제와 맞추기로 했습니다. C 코드를 파싱하는 일은 범위가 너무 커서, 코드를 SSA(Static Single Assignment)와 비슷한 중간 표현으로 바꾸는 방법을 택했습니다. 재귀 코드는 반복문으로 바꾸고, 함수마다 변수 이름에 접두사를 붙여 이름 충돌을 피했습니다. 파서와 코드 생성기도 나눴으며, abs, add, div, mul, sqrt, while 같은 연산을 담은 자체 DSL을 중간 표현으로 사용했습니다. LLM은 이 SSA 형태로 코드를 변환하는 작업에만 사용했습니다.

각 값은 셀 여러 개를 묶어 표현합니다. 소수점 위치를 고정한 Q 형식 가운데 Q16.16을 골랐습니다. 값 범위는 [-2^15, 2^15)이고, 해상도는 1/2^16입니다. Q8.8은 해상도가 1/256에 그쳐 장면의 지면을 나타내는 반지름 1000짜리 구를 표현하기에 부족하다고 판단했습니다.

덧셈부터 제곱근까지 직접 구현

값을 옮길 때는 원본 셀을 0으로 만들 때까지 줄이는 동시에 다른 셀을 늘리는 [->+<] 패턴을 씁니다. 복사는 원본을 줄이면서 두 셀을 함께 늘린 뒤, 원본을 다시 복구하는 방식입니다. 각 변수에는 임시 셀도 가까이 배치했습니다. 연산 중간값과 올림값을 저장하고, 포인터 이동을 줄이기 위해서입니다.

곱셈은 반복 덧셈으로 처리합니다. 두 값의 각 셀을 서로 곱한 뒤 결과의 해당 자릿수에 더합니다. Q16.16 값 두 개를 곱하면 소수점 위치가 달라지므로, 결과를 복사할 때 가장 낮은 두 셀을 버립니다. 나눗셈은 긴 나눗셈과 비슷하게 구현했습니다. 피제수의 셀을 높은 자리부터 읽어 나머지를 256배 하고 다음 셀을 더합니다. 나머지에서 제수를 반복해 빼며 몫을 늘리고, 나머지가 음수가 되면 마지막 뺄셈을 되돌립니다. 셀 하나를 처리할 때 뺄셈은 최대 255회 필요합니다. 나눗셈에서 정밀도가 줄어드는 문제는 제수로 나누기 전에 피제수를 2^16배 해 보정합니다.

제곱근은 나눗셈이 필요한 헤론의 방법 대신 긴 나눗셈 방식의 정수 제곱근을 선택했습니다. Q16.16으로 표현한 값 N에서 isqrt(2^16 × N)을 구하면 결과도 Q16.16 형식으로 얻습니다. 결과 정수값이 1 차이 나도 실제 제곱근 값 차이는 1/2^16보다 작습니다. 테일러 근사는 약 0.305보다 작은 영역에서 오차가 커져 채택하지 않았습니다. 난수에는 A = (5 × A + 1) mod 256 형태의 생성기를 사용했습니다. 작성자는 이 방식이 256개 값 전체를 순환하며, 이 사용 사례의 슈퍼샘플링에 적합하다고 설명합니다.

비교 연산은 두 값의 복사본을 함께 감소시키며 차이를 확인합니다. 음수는 최상위 비트로 판별하고, 비교에 앞서 부호 표현을 조정합니다. 불리언은 참을 1, 거짓을 0으로 나타냅니다. 부호 반전은 각 셀을 보수로 바꾸고 1을 더하는 방식으로 구현합니다. 함수 호출은 함수 본문을 호출 지점에 인라인으로 넣습니다. if와 while도 셀을 조건으로 삼는 반복문으로 구성하며, else에는 별도 플래그를 둡니다.

렌더링 속도와 후속 개선

완성된 Brainfuck 프로그램은 약 2,300만 바이트로, 약 0.9MB인 출력 이미지보다 큽니다. 초기 구현은 분당 약 100회 레이 계산을 수행했습니다. 저자는 이를 픽셀 하나당 약 1분으로 계산했고, 400×225 이미지 전체를 그리는 데 최적화 없이 약 62.5일이 걸릴 것으로 추정했습니다. 당시 생성한 1,229개 픽셀 가운데 원본 C 구현과 다른 픽셀은 10개뿐이었으며, 차이는 대부분 값 1 정도였습니다. 글에 실린 이미지는 전체 렌더링 결과가 아니라 C 코드로 만든 근사 이미지입니다.

작성자는 정밀도를 낮춰 처리하는 셀 수를 줄이거나, 무작위 벡터를 정규화하는 단계를 생략하는 최적화를 언급합니다. 다만 정규화를 생략하면 산란 분포가 달라져 원래 재현하려던 계산과 같지 않게 됩니다. Reddit에서 병렬 처리를 제안받은 뒤에는 JIT 인터프리터를 개선했고, 실제 렌더링 결과를 얻었습니다. 출력 이미지는 정밀도 오차 탓으로 추정되는 붓질 같은 모습으로 나타났습니다.

Reddit 반응

• @u/juugcatm — 재미있는 실험입니다. 병렬 처리는 어떨까요? Brainfuck에 fork와 join 의미를 더한다면 어떻게 표현하시겠습니까?
  • @u/lurgi — 누군가 만든다면 brainfork라고 부르면 되겠네요.
  • @u/snake_on_the_case — 이미 있습니다. [Brainfork 링크를 공유했습니다.]
  • @u/lurgi — 제가 졌습니다.
  • @u/epestr — 명시적인 join에 해당하는 기본 기능은 아직 없네요. 저는 그쪽이 더 유용하다고 생각합니다.
  • @u/epestr — 그 말 들으니 특히 만들어 보고 싶어지네요. 살펴보겠습니다.
  • @u/epestr — 그러면 언어가 너무 복잡해집니다 :( 그래도 픽셀마다 계산은 독립적입니다. 셀을 재사용하고 출력도 즉시 하는 현재 방식 대신, 내부 반복을 여러 번 실행하는 부분에서 fork하면 됩니다. 각 작업에 테이프의 독립 영역을 주고 임시값과 결과를 저장한 다음 마지막에 join하면 됩니다.
  • @u/knome — Parallel INTERCAL도 여러 COME FROM 연산자로 같은 명령을 가리켜 스레딩을 구현할 수 있다면, 당신도 해낼 수 있다고 믿습니다.
  • @u/epestr — 일반 Brainfuck만으로도 사실상 비슷하게 할 수 있습니다. 현재 렌더러는 픽셀마다 샘플 100개를 계산하므로, 샘플 하나만 계산하는 프로그램 100개를 만들고 가용한 자원만큼 실행한 다음 결과를 평균 내면 됩니다. 가로와 세로를 절반으로 줄이고 픽셀당 샘플을 하나만 두고 실행했더니 이미지 절반을 이미 렌더링했습니다.
• @u/jt55401 — 행운을 빕니다.
• @u/fabricatedinterest — 제정신이 아닌 실험이네요. 정말 좋습니다.
• @u/Ameisen — MIPS 에뮬레이터 벤치마크에 Brainfuck Mandelbrot 집합과 함께 이것도 추가해야겠네요.
  • @u/epestr — 이미 있는 것 같습니다. [Brainfuck Mandelbrot 구현 링크를 공유했습니다.]
  • @u/Ameisen — 그래서 그 옆에 추가한다고 한 겁니다. 저도 바로 그 구현을 씁니다. 지금 제 Brainfuck 인터프리터에서 돌려 보고 있는데, 언제 끝날지 모르겠고 기다릴 인내심이 있을지도 모르겠습니다. 노트북 예상 시간과 비슷할 것 같습니다. 제 도구 체인에서는 원본 프로그램이 23,811,165바이트였고, 변환된 프로그램은 2,258,318바이트였습니다. 다음 픽셀이 생성되기까지 712초가 걸렸습니다.
  • @u/epestr — 벤치마크로 쓸 만하게 하려면 ray_ssa.c에서 샘플을 픽셀당 1개로 바꾸고 가로와 세로를 각각 4분의 1로 줄이면 됩니다. 작업량이 약 1,600분의 1로 줄어 100일 안팎에서 1일 미만으로 줄어듭니다. 제가 쓴 JIT 인터프리터도 개선해 실제 렌더링을 얻었습니다. 글 마지막 업데이트에 약간 예술적이고 우스운 결과가 있습니다.
  • @u/Ameisen — 제 인터프리터는 Brainfuck의 자주 나오는 패턴을 최적화합니다. JIT보다는 느리겠지만, Brainfuck에는 JIT보다 정적 재컴파일러가 더 적절할 것 같습니다. 인터프리터를 JIT로 바꾸는 것도 가능하지만, 먼저 자주 쓰는 표현을 줄이는 편이 좋습니다. 지금은 프로그램 크기를 10분의 1로 줄입니다. Mandelbrot 구현은 원본 11,452바이트에서 최적화 후 4,791바이트가 됐고, 실행 시간은 49.056초에서 4.623초로 줄었습니다. VeMIPS는 호스트보다 10배 느리고, 해석 모드는 그보다 다시 10배 느립니다. 호스트에서 이만큼 느리면 VeMIPS에서는 아주 오래 걸릴 겁니다. 그리고 JIT 소스는 보이지 않고 ELF 바이너리만 있습니다.
  • @u/epestr — 저도 표현식을 최적화하려고 했습니다. TSoding의 JIT 컴파일러를 바탕으로 구현했고, 다시 포장해 배포하는 대신 라이선스만 추가했습니다.

원문: epestr.com / 번역·요약: Trawling