하드 모드 러스트

---

URL: https://matklad.github.io/2022/10/06/hard-mode-rust.html

title: 하드 모드 러스트

date: 2022-10-06

---

Oct 6, 2022

이 글은 (예: 동적 메모리 할당 금지처럼) 최소한의, 인위적으로 제약된 API만을 사용해 Rust 애플리케이션을 작성해 보는 사례 연구다. 언어에 대한 상당한 친숙함을 전제로 한다.

Hard Mode Rust

배경은 “하드코어 C 프로그래머”들이 Rust와 C++에 대해 제기하는 특정한 비판이다. 이 비판의 표적은 RAII — C++을 정의하는 핵심 기능이며 Rust에도 그대로(전면적으로) 들어온 개념 — 이다. RAII는 정리가 필요한 각종 리소스(파일 디스크립터, 메모리, 락)를 쓰기 쉽게 만든다. 프로그램 어디서든 리소스를 만들 수 있고, 필요할 때 정리 코드가 자동으로 호출된다. 그리고 바로 여기 문제가 있다. 리소스 할당이 쉬워지기 때문에, RAII는 리소스를 대충 다루는 태도를 부추기고, 프로그램 곳곳에서 리소스가 생성되고 파괴된다. 특히 이는 다음을 초래한다:

• 신뢰성 저하. 리소스는 원칙적으로 제한되어 있지만, 실제로 리소스 고갈은 드물게 일어난다. 프로그램 전반에 걸쳐 리소스가 할당되면, 사실상 테스트되지 않는 코드 경로가 많이 생긴다.
• 예측 가능성 부족. 프로그램이 얼마나 많은 리소스를 소비할지 사전에 예측하기가 보통 불가능하다. 대신 리소스 소비는 경험적으로 관찰된다.
• 성능 저하. 보통은 리소스를 묶어서(batch) 할당하고 해제하는 편이 훨씬 효율적이다. 개별 리소스의 정리 코드가 코드베이스 전체에 흩어져 있어 코드 부풀림(code bloat)도 커진다.
• 스파게티 아키텍처. 리소스 할당은 아키텍처적으로 중요한 일이다. 모든 리소스 관리를 한 곳에 중앙집중화하면, 리소스의 생명주기를 이해하기가 크게 쉬워진다.

나는 이 비판이 타당하다고 생각한다. 사실, 이건 C++/Rust 프로그래머들이 GC 언어를 향해 하는 비판과 같은 종류라고도 생각한다. 이것은 스펙트럼이다:

GC object graph
                 v v
                  v
        Tree of values with RAII
                 v v
                  v
Static allocation of resources at startup

Rust 프로그래머들은 보통 이 피라미드의 최하층을 경험할 일이 없다. 하지만 관련된 경험을 얻기 위한 비교적 간결한 연습이 있다: 좋아하는 Rust 프로그램을 하드 모드로 다시 구현해 보라.

**하드 모드(Hard Mode)**란 프로그램을 std 바이너리와 #![no_std]의 no-alloc 라이브러리로 나누는 것이다. OS에 직접 리소스를 요청할 수 있는 것은 작은 바이너리뿐이다. 라이브러리는 모든 리소스를 주입(inject)받아야 한다. 특히 메모리 할당을 하려면, 라이브러리는 고정 크기의 바이트 슬라이스를 전달받고, 그 슬라이스만을 모든 저장소에 사용해야 한다. 대략 이런 느낌이다:

rust
// app/src/main.rs
fn main() {
  let mem_limit = 64 * 1024;
  let memory = vec![0u8; mem_limit];
  app::run(&mut memory)
}

// app/src/lib.rs
#![no_std] // <- 연습의 핵심

pub fn run(memory: &mut [u8]) {
  ...
}

레이 트레이싱

이 글은 내가 장난감 수준의 하드 모드 레이 트레이서를 구현한 경험에 대한 이야기다. 코드는 GitHub에서 볼 수 있다: http://github.com/matklad/crt.

레이 트레이서의 임무는 아래 같은 3D 씬(scene) 설명을:

background #000000

camera {
    pos 0,10,-50
    look_at 0,0,0
    up 0,-1,0
    focus 50
    dim 80x60
}

light {
    pos -20,10,0
    color #aa1111
}

plane {
    pos 0,-10,0
    normal 0,1,0
    material {
        color #5566FF
        diffuse 3
    }
}

mesh {
    material {
        color #BB5566
        diffuse 3
    }

    data {
        v 5.92,4.12,0.00
        v 5.83,4.49,0.00
        v 5.94,4.61,0.00
        v 6.17,4.49,0.00
        v 6.42,4.12,0.00
        v 5.38,4.12,2.74
        ...

        vn -0.96,-0.25,0.00
        vn -0.96,0.25,0.00
        vn -0.09,0.99,0.00
        vn 0.68,0.73,0.00
        vn 0.87,0.49,0.00
        vn -0.89,-0.25,-0.36
        ...

        f 1/1 2/2 3/3
        f 4/4 5/5 6/6
        ...
    }

}

이런 렌더링 이미지로 변환하는 것이다:

개념적으로는 꽤 직관적으로 동작한다. 먼저, 위의 씬을 상상해 보자. 무한히 큰 선홍색(fuchsia) 평면과 그 위에 떠 있는 빨간색 유타 티포트(주전자)가 있다. 그리고 0,10,-50(직교좌표) 위치에 서서 원점을 바라보는 카메라를 상상하자. 이제 카메라의 시선 방향으로, 초점 거리 50에 해당하는 위치에 80x60의 직사각형 스크린을 가상으로 놓는다. 2D 이미지를 얻기 위해, 스크린의 각 “픽셀”을 통과하도록 카메라에서 광선(ray)을 쏘고, 씬의 어떤 물체를 맞췄는지(평면/티포트/배경)를 기록한 뒤 픽셀을 그에 맞게 칠한다. 더 깊게 빠져들고 싶다면 PBRT Book을 보라(경고: 매우 깊다). (글 전반에서 내가 사용하는 “작은 사각 픽셀” 단순화에 대해서는 사과한다 :-) ).

여기서는 구체적 알고리즘(사실 crt는 매우 순진한 트레이서다)에 집중하기보다는, 하드 모드 Rust에 특화된 고민들을 강조할 것이다.

픽셀 버퍼

결국 레이 트레이서의 출력은 8비트 RGB 픽셀로 이루어진 2D 버퍼다. 보통은 이렇게 표현한다:

rust
pub struct Color { r: u8, g: u8, b: u8 }

pub struct Buf {
  dim: [u32; 2]
  // invariant: data.len() == dim.0 * dim.1
  data: Box<[Color]>,
}

하지만 우리는 누군가(메인)가 색상 박스를 대신 할당해 주길 원한다. 그래서 대신 이렇게 한다:

rust
pub struct Buf<'m> {
  dim: [u32; 2],
  buf: &'m mut [Color],
}

impl<'m> Buf<'m> {
  pub fn new(dim: Idx, buf: &'m mut [Color]) -> Buf<'m> {
    assert!(dim.0 * dim.1 == buf.len() as u32);
    Buf { dim, buf }
  }
}

여기서 'm 라이프타임은 다른 곳에서 관리되는 추상 메모리를 의미한다. 구조체에 라이프타임이 하나 더 늘어난 점에 주목하라! 이는 RAII에 의존해 리소스 정리를 맡기지 않기 위해 지불해야 하는 추가 비용이다:

rust
// Easy Mode
fn paint(buf: &mut Buf) { ... }

struct PaintCtx<'a> {
  buf: &'a mut Buf
}

// Hard Mode
fn paint(buf: &mut Buf<'_>) { ... }

struct PaintCtx<'a, 'm> {
  buf: &'a mut Buf<'m>
}

특히 Ctx 구조체가 이제 두 개의 라이프타임을 포함해야 한다는 점을 보라. 이건 불필요해 보인다: 'a는 'm보다 짧다. 어떻게든 이를 추상화할 수 있으면 좋겠다:

rust
struct PaintCtx<'a> {
  buf: &'a mut Buf<'_> // &'a mut exists<'m>: Buf<'m>
}

나는 그게 실제로 가능하다고 생각하지 않는다(관련 이전 글). 특히 다음은 분산(variance) 문제에 걸린다:

rust
struct PaintCtx<'a> {
  buf: &'a mut Buf<'a>
}

결국 귀찮긴 하지만, 치명적이진 않다.

이 rgb::Buf<'_>로 프로그램을 개략적으로 그리면 이렇게 된다:

rust
// hard mode library
#![no_std]
pub fn render<'a>(
  crt: &'a str,   // 씬의 텍스트 표현
  mem: &mut [u8], // 사용할 수 있는 모든 메모리
  buf: &mut rgb::Buf, // 여기에 이미지를 쓴다
) -> Result<(), Error<'a>> {
  ...
}

// main
#[derive(argh::FromArgs)]
struct Args {
  #[argh(option, default = "64")]  mem: usize,
  #[argh(option, default = "800")] width: u32,
  #[argh(option, default = "600")] height: u32,
}

fn main() -> anyhow::Result<()> {
  let args: Args = argh::from_env();

  let mut crt = String::new();
  io::stdin()
    .read_to_string(&mut crt)
    .context("reading input")?;

  // 메모리를 전부 할당한다.
  let mut mem = vec![0; args.mem * 1024];

  // 이미지를 할당한다.
  let mut buf = vec![
    rgb::Color::default();
    (args.width * args.height) as usize
  ];
  let mut buf =
    rgb::Buf::new([args.width, args.height], &mut buf);

  render::render(
    &crt,
    &mut mem,
    &mut buf,
  )
  .map_err(|err| anyhow::format_err!("{err}"))?;

  // 결과를 PPM 이미지 포맷으로 출력한다.
  write_ppm(&buf, &mut io::stdout().lock())
    .context("writing output")?;
  Ok(())
}

fn write_ppm(
  buf: &rgb::Buf,
  w: &mut dyn io::Write,
) -> io::Result<()> {
  ...
}

하드 모드 Rayon

레이 트레이싱은 병렬화가 아주 쉬운 작업이다 — 출력 픽셀 각각의 색은 독립적으로 계산할 수 있다. 보통은 훌륭한 rayon 라이브러리를 써서 병렬성을 활용하지만, 이번 레이 트레이서에서는 다코어를 활용하기 위한 훨씬 단순한 API 설계를 보여주고 싶다. 이 설계는 Ruby용 타입 체커인 Sorbet에서 본 적이 있다.

병렬성을 지원하는 render 함수는 이렇게 생겼다:

rust
type ThreadPool<'t> = dyn Fn(&(dyn Fn() + Sync)) + 't;

pub fn render<'a>(
  crt: &'a str,
  mem: &mut [u8],
  in_parallel: &ThreadPool<'_>,
  buf: &mut rgb::Buf<'_>,
) -> Result<(), Error<'a>> {

여기서 인터페이스는 in_parallel 함수다. 이는 다른 함수를 인자로 받아, 사용 가능한 모든 스레드에서 그 함수를 병렬로 실행한다. 보통은 이렇게 사용한다:

rust
let work: ConcurrentQueue<Work> = ConcurrentQueue::new();
work.extend(available_work);
in_parallel(&|| {
  while let Some(item) = work.pop() {
    process(item);
  }
})

이는 전형적인 스레드풀과 비슷하지만 다르다. 스레드풀처럼 여러 스레드(보통 코어당 하나)가 임의의 작업(job)을 실행하는 점은 같다. 첫 번째 차이점은, 전형적인 스레드풀이 한 작업을 단일 스레드로 보내는 반면, 이 설계에서는 같은 작업이 모든 스레드에 브로드캐스트된다는 점이다. 작업 타입은 FnOnce + Send가 아니라 Fn + Sync다. 두 번째 차이점은, 모든 스레드에서 작업이 끝날 때까지 _블록_하므로 스택에서 데이터를 빌려올 수 있다는 점이다.

구체적인 작업 아이템을 분배하기 위해서는 호출자가 명시적으로 동시 큐를 구현해야 한다. 내 구현에서는 이미지를 행(row) 단위로 나눈다.

rust
type ThreadPool<'t> = dyn Fn(&(dyn Fn() + Sync)) + 't;

pub fn render<'a>(
  crt: &'a str,
  mem: &mut [u8],
  in_parallel: &ThreadPool<'_>,
  buf: &mut rgb::Buf<'_>,
) -> Result<(), Error<'a>> {
  ...
  // 주의: 이건 mut이 아니다. 동시(concurrent) 이터레이터다.
  let rows = buf.partition();
  in_parallel(&|| {
    // next_row는 atomic을 증가시키고
    // row 인덱스를 이용해 해당 행의 픽셀에 대한 `&mut`을 제공한다.
    while let Some(row) = rows.next_row() {
      let y: u32 = row.y;
      let buf: &mut [rgb::Color] = row.buf;
      for x in 0..dim[0] {
        let color = render::render_pixel(&scene, [x, y]);
        buf[x as usize] = to_rgb(&color);
      }
    }
  });
  ...
}

main에서는 코어당 하나의 스레드를 스폰(spawn)하여 구체적인 ThreadPool을 구현한다:

rust
fn main() -> anyhow::Result<()> {
  ...
  let threads = match args.jobs {
    Some(it) => Threads::new(it),
    None => Threads::with_max_threads()?,
  };
  render::render(
    &crt,
    &mut mem,
    &|f| threads.in_parallel(f),
    &mut buf,
  )
  .map_err(|err| anyhow::format_err!("{err}"))?;
}

할당기

우리가 렌더링할 씬은 본질적으로 동적 크기다. 임의의 개수의 오브젝트를 담을 수 있다. 따라서 모든 메모리를 정적으로 사전에 할당할 수 없다. 대신 CLI 인자로 레이 트레이서가 사용할 수 있는 메모리 양을 정하고, 그 안에서 해결하거나 에러를 반환해야 한다. 즉, 직접 할당기를 작성해야 한다. 하지만 실제로 필요한 만큼만 메모리를 할당하려고 최대한 노력할 것이고, 메모리 해제는 전혀 구현하지 않아도 되게 만들 것이다. 그러니 단순한 범프(bump) 할당기면 충분하다:

rust
pub struct Mem<'m> {
  raw: &'m mut [u8],
}

#[derive(Debug)]
pub struct Oom;

impl<'m> Mem<'m> {
  pub fn new(raw: &'m mut [u8]) -> Mem<'m> {
    Mem { raw }
  }

  pub fn alloc<T>(&mut self, t: T) -> Result<&'m mut T, Oom> { ... }

  pub fn alloc_array<T>(
    &mut self,
    n: usize,
    mut element: impl FnMut(usize) -> T,
  ) -> Result<&'m mut [T], Oom> { ... }

  pub fn alloc_array_default<T: Default>(
    &mut self,
    n: usize,
  ) -> Result<&'m mut [T], Oom> {
    self.alloc_array(n, |_| T::default())
  }
}

바이트 슬라이스로부터 할당기를 만들고, 값이나 배열을 할당해 달라고 요청할 수 있다. 개략적으로 alloc은 이런 느낌이다:

rust
// PSEUDOCODE, 정렬(alignment)을 처리하지 않으며 깨져 있다.
pub fn alloc<'a, T>(
  &'a mut self,
  val: T,
) -> Result<&'m mut T, Oom> {
  let size = mem::size_of::<T>();
  if self.raw.len() < size {
    // 메모리가 부족하면 에러를 반환한다.
    return Err(Oom);
  }

  // 시작 부분에서 size_of::<T> 바이트를 떼어낸다.
  // borrow checker를 달래기 위해 `mem::take` 트릭을 쓴다.
  let res: &'m mut [u8] = {
    let raw = mem::take(&mut self.raw);
    let (res, raw) = raw.split_at_mut(size);
    self.raw = raw;
    res
  };

  // 값을 초기화한다.
  let res = res as *mut [u8] as *mut u8 as *mut T;
  unsafe {
    ptr::write(res, val);
    Ok(&mut *res)
  }
}

이를 완전히 올바르게 만들려면 정렬(alignment)도 처리해야 하지만, 간결함을 위해 그 부분은 뺐다.

배열 할당의 경우, “전부 0인 비트 패턴”이 타입의 유효한 기본값이라면 원소별 초기화를 생략할 수 있어서 유용하다. 하지만 이런 조건은 현재 Rust에서 쉽게 표현할 수 없으므로, 우리는 배열의 모든 원소를 초기화하도록 요구한다.

할당 결과는 &'m T다 — 이것이 하드 모드에서 Box<T>를 표기하는 방식이다.

파싱

씬에는 구(sphere)나 평면(plane) 같은 다양한 오브젝트가 있다:

rust
pub struct Sphere {
  pub center: v64, // v64는 [f64; 3]
  pub radius: f64,
}

pub struct Plane {
  pub origin: v64,
  pub normal: v64,
}

보통이라면 씬을 이렇게 표현한다:

rust
pub struct Scene {
  pub camera: Camera,
  pub spheres: Vec<Sphere>,
  pub planes: Vec<Plane>,
}

하드 모드에서도 크기 조절 가능한 배열(Vec)을 구현할 수는 있다. 하지만 그렇게 하면 메모리를 누수시키거나, 할당기에 제대로 된 해제 로직을 구현하고, 이를 안정적으로 트리거하기 위해 디스트럭터도 추가해야 한다. 그런데 디스트럭터는 바로 이 연습에서 피하려는 대상이다. 그래서 씬은 이렇게 생길 수밖에 없다:

rust
pub struct Scene<'m> {
  pub camera: Camera,
  pub spheres: &'m mut [Sphere],
  pub planes: &'m mut [Plane],
}

즉, 필요한 오브젝트 수를 미리 알아야 한다. 이를 해결하는 방법은 2패스 파싱이다. 첫 패스에서 개수를 세고, 그만큼 할당한 다음, 두 번째 패스에서 할당된 공간에 실제로 파싱 결과를 채워 넣는다.

rust
pub(crate) fn parse<'m, 'i>(
  mem: &mut Mem<'m>,
  input: &'i str,
) -> Result<Scene<'m>, Error<'i>> {
  // 필요한 할당 크기를 계산한다.
  let mut n_spheres = 0;
  let mut n_planes = 0;
  for word in input.split_ascii_whitespace() {
    match word {
      "sphere" => n_spheres += 1,
      "plane" => n_planes += 1,
      _ => (),
    }
  }

  // 할당한다.
  let mut res = Scene {
    camera: Default::default(),
    spheres: mem.alloc_array_default(n_spheres)?,
    planes: mem.alloc_array_default(n_planes)?,
  };

  // 할당된 씬에 "집어넣으며" 파싱한다.
  let mut p = Parser::new(mem, input);
  scene(&mut p, &mut res)?;
  Ok(res)
}

파싱 중 에러를 만나면, 도움이 되는 에러 메시지를 만들고 싶다. 메시지가 완전히 동적이면 'm에 _할당_해야 하지만, 입력의 일부를 에러 메시지로 재사용하는 편이 더 단순해 보인다. 그래서 Error<'i>는 메모리 라이프타임 'm이 아니라 입력 라이프타임 'i에 묶인다.

중첩 오브젝트

씬에서 흥미로운 오브젝트 유형 중 하나는 삼각형 메쉬(mesh)다(예: 티포트는 그냥 삼각형들의 집합이다). 삼각형 묶음을 표현하는 순진한 방법은 벡터를 쓰는 것이다:

rust
pub struct Triangle {
  pub a: v64,
  pub b: v64,
  pub c: v64,
}

type Mesh = Vec<Triangle>;

하지만 이는 낭비가 크다. 메쉬에서는 각 변(edge)이 두 삼각형에 의해 공유된다. 즉, 하나의 정점(vertex)은 여러 삼각형에 속한다. 삼각형 벡터로 저장하면 정점 데이터를 불필요하게 중복 저장하게 된다. 더 압축된 표현은 유일한 정점들을 한 번만 저장하고, 공유를 위해 인덱스를 사용하는 것이다:

rust
pub struct Mesh {
  pub vertexes: Vec<v64>,
  pub faces: Vec<MeshFace>,
}
// 인덱스는 vertexes 벡터를 가리킨다.
pub struct MeshFace { a: u32, b: u32, c: u32 }

다시, 하드 모드에서는 이렇게 된다:

rust
pub struct Mesh<'m> {
  pub vertexes: &'m mut [v64],
  pub faces: &'m mut [MeshFace],
}

그리고 씬에는 여러 메쉬가 들어간다:

rust
pub struct Scene<'m> {
  pub camera: Camera,
  pub spheres: &'m mut [Sphere],
  pub planes: &'m mut [Plane],
  pub meshes: &'m mut [Mesh<'m>],
}

구조가 재귀적이라면 &'m mut T<'m> 형태의 “소유 포인터”가 생긴다는 점에 주목하라. 처음에는 이것이 분산(variance) 문제를 일으킬까 걱정했지만, 소유권 관점에서는 잘 동작하는 듯하다. 다만 처리(processing) 중에는 여전히 &'a mut T<'m>가 필요하다.

그리고 그 때문에 파싱 함수들은 불편할 정도로 많은 라이프타임을 갖는다:

rust
fn mesh<'m, 'i>(
  p: &mut Parser<'m, 'i, '_>,
  res: &mut Mesh<'m>,
) -> Result<(), Error<'i>> { ... }

파서 p는 &'i str 입력과 &'a mut Mem<'m> 메모리를 들고 있다. 그리고 &'b mut Mesh<'m>에 입력을 파싱해서 써 넣는다.

바운딩 볼륨 계층(BVH)

Scene<'m>을 완전히 파싱했으니, 이제 마침내 이미지를 렌더링할 수 있다. 순진한 방법은 각 픽셀마다 광선을 쏘고, 모든 도형을 중첩 반복으로 훑으며 가장 가까운 교차(intersection)를 찾는 것이다. 하지만 이는 매우 느리다! 티포트 모델에는 약 1k 삼각형이 있고, 픽셀은 640*480개이므로, 광선-삼각형 교차 테스트가 307_200_000번 발생한다. 멀티스레딩을 해도 꽤 느리다.

따라서 속도를 올리자. 아이디어는 단순하다 — 각 삼각형마다 광선을 교차시키지 말자. 삼각형 묶음을 빠르게 걸러낼 수 있다. 삼각형 묶음이 있다면 전처리 단계로 그들을 감싸는 3D 박스(상자)를 그릴 수 있다. 이제 광선이 바운딩 박스와 교차하지 않으면, 어떤 삼각형과도 교차할 수 없다는 걸 알 수 있다. 즉 많은 삼각형 테스트 대신 바운딩 박스 테스트 한 번으로 대체할 수 있다.

물론 이는 단방향이다 — 광선이 박스와 교차하더라도 삼각형을 모두 빗나갈 수 있다. 하지만 바운딩 박스를 똑똑하게(인접한 삼각형을 많이 포함하는 작은 박스들) 배치하면 많은 작업을 건너뛸 수 있기를 기대할 수 있다.

아주 똑똑한 방법까지 가는 대신, 단순한 분할 정복을 사용하자. 구체적으로, 전체 삼각형을 감싸는 큰 박스를 만든다. 그 박스의 X/Y/Z 중 가장 긴 축을 찾는다. 예를 들어 박스가 매우 높다면, 수평으로 반 갈라 각 절반이 절반의 삼각형을 포함하도록 한다. 그런 다음 두 절반을 재귀적으로 분할한다.

결국, 각 노드가 바운딩 박스와 두 자식을 가진 이진 트리가 된다. 자식의 바운딩 박스는 부모 바운딩 박스 안에 포함된다. 리프(leaf)는 삼각형을 담는다. 이 구성은 바운딩 볼륨 계층(bounding volume hierarchy, BVH)이라 부른다.

광선을 BVH와 교차시키기 위해 재귀 절차를 사용한다. 루트 노드에서 시작해, 광선이 교차하는 바운딩 박스를 가진 자식으로 내려간다. 때로는 두 자식 모두로 내려가야 하지만, 충분히 자주 최소 한 자식의 바운딩 박스는 광선에 닿지 않아 서브트리 전체를 건너뛸 수 있다.

Easy mode Rust에서는 이렇게 코딩할 수 있다:

rust
struct BoundingBox {
  // 박스의 서로 마주보는 두 꼭짓점
  lo: v64, hi: v64,
}

struct Bvh {
  root: BvhNode
}

enum BvhNode {
  Split {
    bb: BoundingBox,
    children: [Box<BvhNode>; 2],
    /// X,Y,Z 차원 중 어느 축을 사용해
    // bb를 두 조각으로 잘랐는지.
    axis: u8,
  }
  Leaf {
    bb: BoundingBox,
    /// 메쉬에서 삼각형의 인덱스.
    triangle: u32,
  }
}

하드 모드에서는 그런 개별 박스들을 그다지 좋아하지 않는다. 우리는 배열을 좋아한다! 그래서 우리가 원하는 형태는 이렇다:

rust
pub struct Bvh<'m> {
  splits: &'m mut [BvhSplit],
  leaves: &'m mut [BvhLeaf],
}

struct BvhSplit {
  /// splits 또는 leaves 중 하나에 대한 인덱스.
  /// `tag`는 최상위 비트에 있다.
  children: [u32; 2],
  bb: BoundingBox,
  axis: u8,
}

struct BvhLeaf {
  face: u32,
  bb: BoundingBox,
}

그래서 메쉬에 대해 BVH를 재귀적으로 구성하는 다음 함수를 쓰고 싶다:

rust
pub fn build(
  mem: &mut Mem<'m>,
  mesh: &Mesh<'m>,
) -> Result<Bvh<'m>, Oom> { ... }

문제는, 파서와 달리 전체 트리를 실제로 빌드하지 않고는 리프와 분기(split) 노드 개수를 싸게 알아낼 수 없다는 것이다.

스크래치 공간

그래서 여기서는 포인터 트리 구조를 어떤 스크래치 공간에 할당하고, 그걸 &'m mut 배열로 복사할 것이다. 스크래치 공간은 어떻게 찾을까? 우리의 메모리는 &'m [u8]다. 우리는 영역의 앞쪽부터 할당한다. 그러므로 끝쪽에서 스크래치 공간을 떼어낼 수 있다:

&'m mut [u8] -> (&'m mut [u8], &'s mut [u8])

첫 번째 절반에 할당되는 것들은 “영구(permanent)” 할당이다. 두 번째 절반에 할당되는 것들은 “임시(temporary)” 할당이다. 임시 버퍼를 드롭하면 그 공간 전부를 회수할 수 있다.

이건… 아마 이 전체 시도에서 가장 수상한 부분일 것이다. unsafe이고, 라이프타임 꼼수가 필요하며, 실제로 miri를 통과시키지 못한다. 하지만 괜찮겠지…?

그래서 나는 다음 같은 API를 만들었다:

rust
impl Mem<'m> {
  pub fn with_scratch<T>(
    &mut self,
    size: usize,
    f: impl FnOnce(&mut Mem<'m>, &mut Mem<'_>) -> T,
  ) -> T { ... }
}

이렇게 사용할 수 있다:

rust
#[test]
fn test_scratch() {
  let mut buf = [0u8; 4];
  let mut mem = Mem::new(&mut buf);

  let x = mem.alloc(0u8).unwrap();
  let y = mem.with_scratch(2, |mem, scratch| {
    // 여기서는 `mem`에서 영구 할당을,
    // `scratch`에서 임시 할당을 할 수 있다.
    // 밖으로 나갈 수 있는 건 영구 할당뿐이다.

    let y = mem.alloc(1u8).unwrap();
    let z = scratch.alloc(2u8).unwrap();
    assert_eq!((*x, *y, *z), (0, 1, 2));

    // 남은 메모리는 스크래치가 차지하고 있다.
    assert!(mem.alloc(0u8).is_err());

    y // 여기서 z를 반환하면 실패한다.
  });

  // 스크래치 메모리는 이제 회수되었다.
  let z = mem.alloc(3u8).unwrap();
  assert_eq!((*x, *y, *z), (0, 1, 3));
  assert_eq!(buf, [0, 1, 3, 0]);
  // 컴파일이 실패한다.
  // assert_eq!(*x, 0);
}

그리고 with_scratch 구현은 다음과 같다:

rust
pub fn with_scratch<T>(
  &mut self,
  size: usize,
  f: impl FnOnce(&mut Mem<'m>, &mut Mem<'_>) -> T,
) -> T {
  let raw = mem::take(&mut self.raw);

  // 스크래치 공간을 떼어낸다.
  let mid = raw.len() - size;
  let (mem, scratch) = raw.split_at_mut(mid);

  self.raw = mem;
  let res = f(self, &mut Mem::new(scratch));

  let data = self.raw.as_mut_ptr();
  // 스크래치 공간을 다시 붙인다.
  let len = self.raw.len() + size;
  // 이게 miri를 불평하게 만든다. 누가 조언 좀? :(
  self.raw = unsafe { slice::from_raw_parts_mut(data, len) };
  res
}

이 인프라가 준비되면, 마침내 BVH 구성을 구현할 수 있다! 3단계로 한다:

1. 메모리의 절반을 스크래치 공간으로 떼어낸다.
2. 그 공간에 동적으로 크기가 변하는 트리를 빌드하면서 리프와 내부 노드 수를 센다.
3. 영구 공간에 정확한 크기의 배열을 할당하고 데이터를 한 번만 복사한다.

rust
pub struct Bvh<'m> {
  splits: &'m mut [BvhSplit],
  leaves: &'m mut [BvhLeaf],
}

struct BvhSplit {
  children: [u32; 2],
  bb: BoundingBox,
  axis: u8,
}

struct BvhLeaf {
  face: u32,
  bb: BoundingBox,
}

// 스크래치 공간에 저장하는 임시 트리.
enum Node<'s> {
  Split {
    children: [&'s mut Node<'s>; 2],
    bb: BoundingBox,
    axis: u8
  },
  Leaf { face: u32, bb: BoundingBox },
}

pub fn build(
  mem: &mut Mem<'m>,
  mesh: &Mesh<'m>,
) -> Result<Bvh<'m>, Oom> {
  let free_mem = mem.free();
  mem.with_scratch(free_mem / 2, |mem, scratch| {
    let (node, n_splits, n_leaves) =
      build_scratch(scratch, mesh);

    let mut res = Bvh {
      splits: mem.alloc_array_default(n_splits as usize)?,
      leaves: mem.alloc_array_default(n_leaves as usize)?,
    };
    copy(&mut res, &node);

    Ok(res)
  })
}

fn build_scratch<'s>(
  mem: &mut Mem<'s>,
  mesh: &Mesh<'_>,
) -> Result<(&'s mut Node<'s>, usize, usize), Oom> {
  ...
}

fn copy<'m, 's>(res: &mut Bvh<'m>, node: &Node<'s>) {
  ...
}

그리고 끝! miri의 불평에도 불구하고 실제로 동작한다!

결론

솔직히 나는 감명받았다. 나는 이게 실제로 성립하지 않을 거라고 확신했고, 내가 원하는 런타임 동작을 얻기 위해 엄청난 양의 unsafe를 써야 할 거라고 생각했다. 특히 &'m mut T<'m>의 분산 문제 때문에 'm, 'mm, 'mmm 같은 라이프타임을 계속 추가하게 될 거라고 믿었는데, 그런 일은 일어나지 않았다. “소유” 포인터에 대해서는 &'m mut T<'m>가 꽤 잘 동작했다! 추가 라이프타임이 필요한 건 처리 단계뿐이다. Parser<'m, 'i, 'a>는 내가 편안하게 느끼는 것보다 최소 두 개의 라이프타임이 더 있지만, 뭐… 감수할 수 있을 것 같다.

이 스타일의 프로그래밍을 어디까지 밀어붙일 수 있을지 궁금하다. 미적으로는, 프로그램이 정확히 얼마나 많은 메모리를 사용하는지 정밀하게 알 수 있다는 점이 꽤 마음에 든다!

이 글의 코드: http://github.com/matklad/crt.

/r/rust에서의 토론.