Статическая и динамическая диспетчеризация

Дженерики и dyn Trait решают одну задачу — полиморфизм, — но платят за него в разных валютах: размером бинарника или косвенным вызовом.

Диспетчеризация — выбор конкретной реализации метода: статическая делает это компилятор, динамическая — рантайм по таблице виртуальных функций.

Вопрос: «В чём разница между impl Trait и dyn Trait?»

Возьмём для примеров трейт фигуры — он понадобится дальше во всём уроке.

trait Shape {
    fn area(&self) -> f64;
}

struct Circle { r: f64 }
struct Square { a: f64 }

impl Shape for Circle {
    fn area(&self) -> f64 { std::f64::consts::PI * self.r * self.r }
}

impl Shape for Square {
    fn area(&self) -> f64 { self.a * self.a }
}

Что на самом деле проверяет интервьюер

• Знаете ли вы слово мономорфизация и что она делает с кодом.
• Понимаете ли, что dyn Trait — это fat pointer, а не «объект».
• Умеете ли выбирать между ними по ситуации, а не «всегда generics, потому что быстрее».

Статическая диспетчеризация: мономорфизация

Дженерик-функция — это шаблон. Для каждого конкретного типа, с которым её позвали, компилятор генерирует отдельную копию машинного кода и подставляет прямой вызов метода. Дальше работает инлайнинг и остальные оптимизации.

fn describe<T: Shape>(s: &T) {
    println!("площадь {:.2}", s.area());
}

// то же самое, но короче: impl Trait в позиции аргумента
fn describe_sugar(s: &impl Shape) {
    println!("площадь {:.2}", s.area());
}

fn main() {
    describe(&Circle { r: 1.0 });
    describe_sugar(&Square { a: 2.0 });
}

Вывод:

площадь 3.14
площадь 4.00

После компиляции существуют две независимые функции: одна знает только про Circle, вторая — только про Square. Цена — размер бинарника и время компиляции; выгода — нулевая стоимость абстракции.

Динамическая диспетчеризация: fat pointer и vtable

&dyn Shape занимает два машинных слова: указатель на данные и указатель на vtable — таблицу с адресами методов, размером и деструктором конкретного типа. Вызов s.area() превращается в чтение адреса из таблицы и косвенный переход. Копия функции одна на всех.

fn describe_dyn(s: &dyn Shape) {
    println!("площадь {:.2}", s.area());
}

Вопрос: «Почему Vec<Box<dyn Shape>>, а не Vec<dyn Shape>?»

Классический вопрос на понимание DST. Попробуем написать «как хочется».

fn main() {
    let mut shapes: Vec<dyn Shape> = Vec::new();
    shapes.push(Circle { r: 1.0 });
}

Ошибка компиляции:

error[E0277]: the size for values of type `dyn Shape` cannot be known at compilation time
 --> src/main.rs:12:20
   |
12 |     let mut shapes: Vec<dyn Shape> = Vec::new();
   |                     ^^^^^^^^^^^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `Sized` is not implemented for `dyn Shape`
note: required by an implicit `Sized` bound in `Vec`
   = help: consider using `Box<dyn Shape>` instead

Что на самом деле проверяет интервьюер

Знаете ли вы про DST — dynamically sized types. dyn Shape — это не тип фиксированного размера: за ним может стоять Circle в 8 байт или структура в 200 байт. Vec<T> хранит элементы подряд и обязан знать шаг, поэтому требует T: Sized (этот bound подставляется молча ко всем параметрам типов). Размер становится известен, как только значение спрятано за указателем — Box<dyn Shape>, &dyn Shape, Rc<dyn Shape> имеют фиксированный размер в два слова.

fn main() {
    let shapes: Vec<Box<dyn Shape>> = vec![
        Box::new(Circle { r: 1.0 }),
        Box::new(Square { a: 2.0 }),
    ];

    let total: f64 = shapes.iter().map(|s| s.area()).sum();
    println!("итого {:.2}", total);
}

Вывод:

итого 7.14

Обратите внимание: с дженериками такой вектор не собрать в принципе — Vec<T> хранит один конкретный тип. Гетерогенная коллекция — главная причина брать dyn.

Вопрос: «Что такое object safety?»

Не всякий trait можно превратить в dyn. Правило (сейчас в документации его называют dyn compatibility, старое имя — object safety) отсекает методы, которые невозможно вызвать через vtable.

trait Spawn {
    fn create() -> Self;      // нет &self и возвращает Self
    fn id(&self) -> u32;
}

struct Db;

impl Spawn for Db {
    fn create() -> Self { Db }
    fn id(&self) -> u32 { 1 }
}

fn main() {
    let r: &dyn Spawn = &Db;
    println!("{}", r.id());
}

Ошибка компиляции:

error[E0038]: the trait `Spawn` is not dyn compatible
  --> src/main.rs:15:13
   |
15 |     let r: &dyn Spawn = &Db;
   |             ^^^^^^^^^ `Spawn` is not dyn compatible
   |
note: for a trait to be dyn compatible it must not have any associated functions without a `self` parameter
  --> src/main.rs:2:8
   |
2  |     fn create() -> Self;
   |        ^^^^^^ ...because associated function `create` has no `self` parameter
   = help: consider moving `create` to another trait

Причины несовместимости всегда одни и те же: метод возвращает Self (размер неизвестен вызывающей стороне), метод без self (нет объекта — нет vtable), метод с собственными дженерик-параметрами (сколько копий класть в таблицу?). Поэтому dyn Clone написать нельзя: clone возвращает Self. Обход — свой trait с fn clone_box(&self) -> Box<dyn Shape>.

impl Trait в возврате

-> impl Shape означает «здесь ровно один конкретный тип, но я его не называю». Это по-прежнему статическая диспетчеризация; вернуть из разных веток разные типы нельзя — для этого нужен Box<dyn Shape>. Приём незаменим для замыканий и итераторов, у которых имя типа невыразимо.

Таблица сравнения

Типичные ошибки кандидатов

• Говорить «dyn медленнее» без цифр и контекста: косвенный вызов стоит единицы наносекунд, а вот потерянный инлайн в горячем цикле — уже заметно.
• Считать, что Box<dyn Trait> нужен из-за кучи. Он нужен из-за неизвестного размера; &dyn Trait кучи не требует вовсе.
• Забывать про неявный bound Sized и не понимать, откуда взялся E0277.
• Путать impl Trait в возврате с dyn: первый — один скрытый тип, второй — любой из многих.
• Пытаться сделать Vec<Box<dyn Clone>> и удивляться E0038.
• Выбирать generics «по умолчанию» в коде, где реально нужны плагины и гетерогенность, и получать взрывной рост бинарника.

Как ответить кратко

«Дженерики — статическая диспетчеризация: компилятор мономорфизирует функцию под каждый тип, вызовы прямые и инлайнятся, но код дублируется. dyn Trait — динамическая: значение представлено fat pointer из данных и vtable, вызов идёт через таблицу, зато код один. Vec<dyn Shape> не компилируется, потому что dyn Shape — DST без известного размера, а Vec требует Sized; размер появляется за указателем, отсюда Box<dyn Shape>. Object safety — набор ограничений, при которых trait вообще можно превратить в dyn: никаких методов без self, возвращающих Self или дженерик-методов. Беру dyn для гетерогенных коллекций и плагинов, generics — на горячем пути.»