[Перевод] Rust в режиме «жесть»
В этом посте будет разобрано, как написать приложение на Rust с применением самого минимального API, возможности которого искусственно ограничены (например, не применяется динамическое выделение памяти). Предполагается, что читатель немного знаком с языком Rust.
Жёсткий Rust
Идея этого проекта возникла как ответ на специфическую критику, которой подвергают Rust и C++ ортодоксальные C-программисты. Эта критика направлена на RAII — формообразующую фичу C++, которая была полностью и без исключений импортирована и в Rust. При работе с RAII используются различные ресурсы (дескрипторы файлов, память, блокировки), после употребления которых требуется очищать последствия работы. В любой точке программы, где может быть создан ресурс, также может быть вызван код очистки — при необходимости это произойдёт автоматически. В этом и заключается проблема. Поскольку выделение ресурсов настолько упрощается, RAII потворствует небрежному обращению с ресурсами, когда они выделяются и убираются повсюду в пределах программы. Вот к чему, среди прочего, это приводит:
Снижение надёжности. Ресурсы в принципе обычно ограничены, но такое, чтобы некоторый ресурс был полностью исчерпан, происходит редко. Если ресурсы выделяются в программе повсюду, то возникает множество практически непротестированных путей выполнения кода.
Непредсказуемость при работе. Как правило, невозможно заранее спрогнозировать, сколько ресурсов израсходует программа. Напротив, потребление ресурсов обычно оценивается эмпирически.
Низкая производительность. Обычно работа идёт гораздо эффективнее, если ресурсы и выделяются, и высвобождаются партиями. Если приходится отдельно очищать каждое небольшое включение ресурсов, и такие включения рассеяны по базе кода, то код пухнет.
Спагетти-архитектура. С архитектурной точки зрения выделение ресурсов — это характерная проблема. Если всё управление ресурсами централизовано в одной точке, то становится гораздо проще понимать жизненный цикл ресурсов.
Думаю, вся эта критика обоснована. Более того, я думаю, ровно такую же критику специалисты по C++ и Rust предъявляют языкам со сборкой мусора. Здесь просматривается спектр:
Граф объектов, попадающих под сборку мусора
v v
v
Дерево значений при работе с RAII
v v
v
Статическое выделение ресурсов при запуске программыКак правило, Rust-программисты избавлены от работы с самым нижним уровнем этой пирамиды. Но есть относительно компактное упражнение, на котором можно получить релевантный опыт. Попробуйте заново реализовать ваши любимые Rust-программы в жёстком режиме.
Под жёстким режимом здесь понимается, что мы разбиваем программу на двоичный файл std и невыделяемая библиотека #![no_std]. Лишь небольшому бинарнику разрешено напрямую запрашивать ресурсы у операционной системы. Что касается библиотеки, все её ресурсы должны внедряться. Например, для выделения памяти библиотека получает байтовый фрагмент фиксированного размера, и нам должно хватить его на хранение всей информации. Примерно в таком духе:
// 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-сцены, подобное нижеприведённому:
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
...
}
}Примерно в такую отображённую картинку:
Концептуально тут всё понятно без объяснения. Первым делом представьте вышеприведённую сцену, в которой имеется бесконечная плоскость цвета фуксия, а над ней парит красный чайник в стилистике племени юта. Далее представьте себе камеру, расположенную в (декартовых) координатах 0,10,-50, нацеленную в начало координат. Теперь начертим воображаемый прямоугольный экран размером 80×60 sна фокусном расстоянии 50 от камеры, расположенный на линии обзора. Чтобы получить картинку в 2D, пропускаем по лучу от камеры через каждый из пикселов на экране, отмечаем, какие из объектов на экране при этом затрагиваются (план, чайник, фон) и соответствующим образом закрашиваем пиксель. Если у вас возникает ощущение, будто вы падаете в кроличью нору — см. PBRT Book (внимание: нора очень глубока). Извините, что в этом посте я говорю о пикселях в упрощённом виде, как о «маленьких квадратиках».
Не буду сосредотачиваться на конкретных алгоритмах, при помощи которых выполняется реализация (в самом деле, crt — это простейший трассировщик), а сосредоточусь на конкретных проблемах, которые возникают с Rust в таком жёстком режиме.
Буфер пикселей
В конечном счёте, мы получаем на выход от трассировщика лучей 2D-буфер, заполненный 8-битными RGB-пикселями. Обычно его представляют следующим образом:
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]>,
}Мы же хотим, чтобы кто-то ещё (в данном случае — главная функция) выделил для нас это пространство цветов, поэтому мы, напротив, поступим так:
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, который должен был бы очищать за нас ресурсы:
// Простой режим
fn paint(buf: &mut Buf) { ... }
struct PaintCtx<'a> {
buf: &'a mut Buf
}
// Жёсткий режим
fn paint(buf: &mut Buf<'_>) { ... }
struct PaintCtx<'a, 'm> {
buf: &'a mut Buf<'m>
}В частности, обратите внимание вот на что: теперь в структуру Ctx требуется включить два времени жизни. Кажется, что в этом нет необходимости, ведь 'a короче 'm. Хотелось бы как-то абстрагировать эту деталь:
struct PaintCtx<'a> {
buf: &'a mut Buf<'_> // &'a mut exists<'m>: Buf<'m>
}На самом деле, не думаю, что это осуществимо (раньше писал об этом). В частности, следующий код обеспечит нам проблемы из-за изменчивости:
struct PaintCtx<'a> {
buf: &'a mut Buf<'a>
}В конечном итоге, это раздражает, но погоды не делает.
Вооружившись rgb::Buf<'_>, можем в общих чертах набросать программу:
// библиотека для работы в жёстком режиме
#![no_std]
pub fn render<'a>(
crt: &'a str, // текстовое описание сцены
mem: &mut [u8], // вся память, которая есть у нас в распоряжении
buf: &mut rgb::Buf, // здесь записываем изображение
) -> Result<(), Error<'a>> {
...
}
// главная функция
#[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, который будет при работе опираться на ресурсы многоядерного процессора. Такой дизайн я видел в Sorbet — инструменте проверки типов, используемом в Ruby.
Вот как выглядит функция render с поддержкой параллелизма:
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, принимающая в виде аргумента другую функцию и распараллеливающая её для выполнения во всех доступных потоках. Обычно работа с ней строится так:
let work: ConcurrentQueue = ConcurrentQueue::new();
work.extend(available_work);
in_parallel(&|| {
while let Some(item) = work.pop() {
process(item);
}
}) Пусть эта реализация и похожа на типичный пул потоков, она от него отличается. Как и при работе с пулом, здесь у нас в распоряжении есть некоторое количество потоков (обычно по одному на ядро), которые сами разбирают себе задания для выполнения. Разница с пулом потоков здесь двоякая. Во-первых, типичный пул потоков отправляет задание отдельно взятому потоку, а при проектируемом нами решении одно и то же задание широковещательно раздаётся всем потокам. Задание претерпевает Fn + Sync, а не FnOnce + Send. Во-вторых, мы блокируемся до тех пор, пока задание не будет выполнено силами всех потоков, это позволит нам заимствовать данные из стека.
На вызывающей стороне мы явно реализуем конкурентную очередь для распределённой обработки конкретных элементов. В моей реализации картинка нарезается построчно.
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, поскольку здесь у нас
// конкуретный итератор.
let rows = buf.partition();
in_parallel(&|| {
// next_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 реализуем конкретный ThreadPool, порождая по одному потоку на ядро:
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-аллокатор:
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(&mut self, t: T) -> Result<&'m mut T, Oom> { ... }
pub fn alloc_array(
&mut self,
n: usize,
mut element: impl FnMut(usize) -> T,
) -> Result<&'m mut [T], Oom> { ... }
pub fn alloc_array_default(
&mut self,
n: usize,
) -> Result<&'m mut [T], Oom> {
self.alloc_array(n, |_| T::default())
}
} Можно создать аллокатор из сегмента байт, а затем приказать ему выделять значения и массивы. Схематически alloc выглядит так:
// ПСЕВДОКОД, не занимается выравниванием и неисправен.
pub fn alloc<'a, T>(
&'a mut self,
val: T,
) -> Result<&'m mut T, Oom> {
let size = mem::size_of::();
if self.raw.len() < size {
// Возвращает ошибку, если памяти недостаточно
return Err(Oom);
}
// Отсекает size_of:: байт в самом начале,
// и немного возться с `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)
}
} Чтобы было совсем грамотно, также нужно предусмотреть, как будет обрабатываться выравнивание, но этот фрагмент я уберу для краткости.
При выделении массивов будет полезно, если для каждого валидного экземпляра типа по умолчанию будет действовать паттерн заполнения всех разрядов нулями — так мы сможем обойтись без поэлементной инициализации. Но в современном Rust это условие не так легко выразить, так что нам потребуется отдельно инициализировать каждый из членов массива.
В результате выделения получаем &'m T — именно так в жёстком режиме записывается Box.
Синтаксический разбор
В сцене содержатся различные объекты, например, сферы и плоскости:
pub struct Sphere {
pub center: v64, // v64 это [f64; 3]
pub radius: f64,
}
pub struct Plane {
pub origin: v64,
pub normal: v64,
}Обычно мы представляем сцену как
pub struct Scene {
pub camera: Camera,
pub spheres: Vec,
pub planes: Vec,
} Можно было бы реализовать массив, размер которого поддаётся динамическому изменению (Vec), но тем самым мы либо спровоцируем утечки памяти, либо будем вынуждены реализовать в нашем аллокаторе полноценную логику деаллокации, а также добавить деструкторы, которые обеспечивали бы её корректное срабатывание.
Но именно без деструкторов мы пытаемся обойтись в этом упражнении, так что наша сцена должна будет принять следующий вид:
pub struct Scene<'m> {
pub camera: Camera,
pub spheres: &'m mut [Sphere],
pub planes: &'m mut [Plane],
}И это означает, что нам требуется заранее знать, сколько объектов нам потребуется. Эту задачу мы решаем, реализуя двухходовой синтаксический разбор. При первом проходе мы просто считаем элементы, затем выделяем их, а уже после этого подвергаем их синтаксическому разбору в пространстве, выделенном аллокатором.
pub(crate) fn parse<'m, 'i>(
mem: &mut Mem<'m>,
input: &'i str,
) -> Result, 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> привязано к времени жизни ввода 'i, а не ко времени жизни памяти 'm.
Вложенные объекты
В этой сцене есть один объект интересного типа, а именно сетка треугольников (например, чайник в нашем примере представлен как совокупность треугольников). Чтобы представить совокупность треугольников, проще всего задействовать вектор:
pub struct Triangle {
pub a: v64,
pub b: v64,
pub c: v64,
}
type Mesh = Vec; Но при этом чрезмерно тратятся ресурсы: фактически же, в сетке каждая сторона является общей для двух треугольников. Если хранить вектор треугольников, то придётся зря дублировать данные вершин. Можно сделать более компактное представление: все уникальные вершины сохранить по одному разу, а затем организовать их совместное использование, обращаясь к ним по индексам:
pub struct Mesh {
pub vertexes: Vec,
pub faces: Vec,
}
// Индексы указывают в вектор с вершинами
pub struct MeshFace { a: u32, b: u32, c: u32 } Опять же, в жёстком режиме имеем
pub struct Mesh<'m> {
pub vertexes: &'m mut [v64],
pub faces: &'m mut [MeshFace],
}А сцена содержит набор сеток:
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>. Исходно я опасался, что это приведёт к проблемам из-за изменчивости, но, по-видимому, всё работает нормально, особенно применительно к владению. Но в процессе обработки нам всё равно понадобится
&'a mut T<'m>.Именно поэтому в функциях для синтаксического разбора содержится так много неудобных времён жизни:
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>.
Иерархия ограничивающих объёмов
Когда синтаксический разбор Scene<'m> доведён до завершения, можно, наконец, переходить к отображению картинки. Проще всего это делается прямым перебором всех пикселей, простреливаемых лучами. После этого каждая фигура подвергается вложенным итерациям, так ищется ближайшее пересечение. Получится медленно! В модели чайника около 1k треугольников, а также у нас здесь 640×480 пикселей. Таким образом, нам нужно провести 307_200_000 проверок на пересечение луча с треугольниками. Получается достаточно медленно даже в режиме многопоточности.
Поэтому нам придётся это ускорить. Идея проста: дело в том, что не нужно рассматривать пересечение луча со всеми треугольниками. Можно быстро отсекать целые партии треугольников. Если у нас есть набор треугольников, можно на этапе предобработки просто обвести его 3D-фигурой. Теперь, если луч не пересекает этот ограничивающий объём, из этого известно, что ни один из интересующих нас треугольников он тоже не пересекает. Поэтому можно провести одну проверку, воспользовавшись ограничивающим объёмом, а не проводить множество тестов для каждого треугольника.
Разумеется, этот подход односторонний — если луч пересекает объём, он всё равно может разминуться со всеми треугольниками. Но, если умно разместить ограничивающие объёмы (речь о маленьких объёмах, захватывающих множество смежных треугольников), то есть надежда, что удастся сократить себе большой объём работы.
Не будем вдаваться в чрезмерные ухищрения, чтобы решить эту задачу, а воспользуемся простой схемой «разделяй и властвуй». Очертим большой объём вокруг имеющихся у нас треугольников. После этого отметим, в каком измерении получившийся объём получается самым длинным. Например, если область получилась очень высокой, её можно разрезать пополам, и в таком случае в каждом из полуобъёмов будет содержаться половина треугольников. После этого станем рекурсивно уполовинивать по такому принципу все получающиеся у нас объёмы.
В итоге получим двоичное дерево, в каждом узле которого содержится ограничивающий объём и два аналогичных дочерних ограничивающих объёма. В листьях содержатся треугольники. Такая конструкция называется «иерархия ограничивающих объёмов» (bvh).
Чтобы добиться пересечения луча с bvh, решаем эту задачу рекурсивно. Начиная с корневого узла, спускаемся к тем его потомкам, с ограничивающими объёмами которых пересекается луч. Иногда приходится при спуске зайти сразу в оба потомка, но зачастую важно учесть всего один. Если второй дочерний объём не пересекается с лучом, мы можем вообще не учитывать его поддерево.
В щадящем режиме на Rust это можно запрограммировать так:
struct BoundingBox {
// Противоположные углы ёмкости
lo: v64, hi: v64,
}
struct Bvh {
root: BvhNode
}
enum BvhNode {
Split {
bb: BoundingBox,
children: [Box; 2],
/// По какому из измерений X,Y,Z
// мы разрезали bb пополам.
axis: u8,
}
Leaf {
bb: BoundingBox,
/// Индекс треугольника в сетке.
triangle: u32,
}
} В жёстком режиме все эти отдельные объёмы нам в самом деле некстати, мы предпочли бы массивы! Поэтому лучше запрограммировать нечто подобное:
pub struct Bvh<'m> {
splits: &'m mut [BvhSplit],
leaves: &'m mut [BvhLeaf],
}
struct BvhSplit {
/// Индекс, позволяющий углубиться в разделения или листья
/// `tag` - это старший бит.
children: [u32; 2],
bb: BoundingBox,
axis: u8,
}
struct BvhLeaf {
face: u32,
bb: BoundingBox,
}Итак, мы хотим написать следующую функцию, которая рекурсивно конструирует bvh для сетки:
pub fn build(
mem: &mut Mem<'m>,
mesh: &Mesh<'m>,
) -> Result, Oom> { ... } Проблема в том, что, в отличие от ситуации с синтаксическим разбором, невозможно «задёшево» определить итоговое количество листьев и разделений, не выстроив целого дерева.
Затираемое пространство
Вот что мы здесь сделаем: выделим древовидную структуру, поместим её в некоторое затираемое пространство (scratch space), а затем скопируем всё это в массив &'m mut. Как же нам найти это пространство? Наша память — &'m [u8]. Выделяем материал, идя от начала этой области. Поэтому можем предусмотреть затираемое пространство где-нибудь с конца:
&'m mut [u8] -> (&'m mut [u8], &'s mut [u8])Тот материал, который мы выделяем в первой половине, будет доступен перманентно, а материал из второй части — временно. Избавившись от временного буфера, мы сможем вернуть в актив всё это пространство.
Пожалуй… именно эта часть всей моей затеи проработана наиболее фрагментарно. Это пространство unsafe, требует ограничивать времена жизни. В довершение всего я не могу протащить этот код через проверку miri, но… всё же должно кончиться хорошо, верно?
Так что у меня получился такой API:
impl Mem<'m> {
pub fn with_scratch(
&mut self,
size: usize,
f: impl FnOnce(&mut Mem<'m>, &mut Mem<'_>) -> T,
) -> T { ... }
} Им можно пользоваться вот так:
#[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:
pub fn with_scratch(
&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! Мы проделаем это в три этапа:
Разделим память так, чтобы половина её отошла под затираемое пространство.
В этом пространстве построим дерево с динамически подбираемым размером, при этом будем подсчитывать листья и внутренние узлы.
В пространстве для долговременного хранения будем создавать массивы подходящего размера и однократно копировать в них данные.
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, 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 ругается.
Выводы
Честно говоря, я впечатлён. Я был уверен, что проект не выгорит, и что мне придётся писать целые простыни небезопасного кода, чтобы добиться во время выполнения именно такого поведения, какого я хочу. В частности, я полагал, что из-за проблемы с изменчивостью &'m mut T<'m> мне придётся вручную добавлять 'm, 'mm, 'mmm и дальнейшие времена жизни, но без этого обошлось. Оказалось, что &'m mut T<'m> нормально работает с «владеющими» указателями. Только при обработке могут потребоваться дополнительные времена жизни. Parser<'m, 'i, 'a> живёт минимум вдвое дольше, чем меня бы устроило, но с этим я готов смириться.
Интересно, как далеко можно зайти, программируя в таком стиле. Эстетически мне очень нравится следующий момент: можно с точностью определить, сколько именно памяти потребуется программе!
Код к посту: http://github.com/matklad/crt.
Дискуссия на /r/rust.
