Как Rust реализует трейт-объекты и почему dyn Trait медленнее дженериков / Хабр

Спросите разработчика: «Почему dyn Trait медленнее дженериков?», в 9 из 10 случаях услышите: «Потому что косвенный вызов через vtable». Один дополнительный переход по указателю, промах по кешу, вот и вся разница. Звучит убедительно. И это процентов на десять правда.

Настоящая цена динамической диспетчеризации не в самом прыжке через vtable, а в том, что этот прыжок прячет от оптимизатора. LLVM видит непрозрачный call по указателю и пасует. Не может встроить тело, не может раскрутить цикл, не может протащить константу через границу вызова. Один косвенный вызов и целый каскад оптимизаций становится невозможным.

Но чтобы понять, почему так происходит, нужно сначала разобраться, как dyn Trait устроен внутри. Что лежит в этом толстяке, как выглядит vtable в памяти, и чем всё это отличается от того, что делает компилятор с дженериками.

Что такое dyn Trait на уровне памяти

Когда вы пишете &dyn Draw или Box<dyn Draw>, Rust создаёт не обычный указатель, а так называемый fat pointer — «толстый указатель». Он занимает два машинных слова вместо одного. На x86-64 это 16 байтиков.

Первое слово — указатель на данные. Просто адрес в памяти, где лежит конкретное значение: ваш Button, TextField, или что бы там ни было.

Второе слово — указатель на vtable. Таблицу виртуальных методов, которая описывает, какой именно тип спрятан за этим dyn Draw.

Тут у нас виднеется первое отличие от C++, там указатель на vtable хранится внутри объекта. Каждый экземпляр класса с виртуальными методами несёт в себе скрытое поле — vptr. Короче говоря сам факт наличия виртуальных методов меняет layout объекта и увеличивает его размер.

В Rust всё наоборот, cам объект ниче не знает о трейтах. Структура Button выглядит в памяти одинаково, независимо от того, используете вы её через dyn Draw, через дженерик или напрямую. Никакого скрытого поля. Указатель на vtable живёт снаружи — в ссылке, в Box, в Rc. Он появляется только тогда, когда вы создаёте трейт-объект.

Это красивое решение, тип не платит за полиморфизм, пока его не попросят. Если вы никогда не оборачиваете Button в dyn Draw — vtable для этой пары вообще не нужна. Но у этой красоты есть цена, и мы до неё дойдём.

Структура vtable

Vtable — это массив указателей, который компилятор генерирует для каждой пары (тип, трейт). Не для каждого экземпляра, а для каждой комбинации типа и трейта. Все Box<dyn Draw>, внутри которых лежит Button, указывают на одну и ту же vtable. Все Box<dyn Draw> с TextField на другую.

Как она выглядит в памяти:

vtable для <Button as Draw>:
  [0] drop_in_place::<Button>    — указатель на деструктор
  [1] size_of::<Button>          — размер типа в байтах
  [2] align_of::<Button>         — выравнивание типа
  [3] <Button as Draw>::draw     — указатель на метод draw
  [4] <Button as Draw>::resize   — указатель на метод resize
  ...                            — остальные методы трейта

Первые три записи — метаданные. Деструктор нужен, чтобы Box<dyn Draw> при выходе из области видимости знал, как очистить то, что внутри. Размер и выравнивание чтобы аллокатор знал, сколько памяти освобождать. Без этих данных Box не смог бы вызвать dealloc, ведь конкретный тип стёрт.

После метаданных идут указатели на методы трейта, в порядке объявления. Каждый — адрес конкретной функции: не обобщённой, а уже мономорфизированной для конкретного типа.

Сама vtable — static. Она живёт в секции .rodata бинарника, существует на протяжении всего времени работы программы, и создаётся на этапе компиляции. Никакого рантайм-создания, никакой аллокации. Это просто кусок данных, вшитый в исполняемый файл.

Можно посмотреть на это глазками:

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

struct Circle { radius: f64 }

impl Draw for Circle {
    fn draw(&self) { /* ... */ }
    fn area(&self) -> f64 { std::f64::consts::PI * self.radius * self.radius }
}

Для пары (Circle, Draw) компилятор сгенерирует vtable примерно такого вида:

vtable_Circle_Draw:
    .quad   drop_in_place<Circle>  // деструктор
    .quad   8                      // size_of::<Circle>() = 8
    .quad   8                      // align_of::<Circle>() = 8
    .quad   Circle::draw           // метод draw
    .quad   Circle::area           // метод area

Когда вы пишете let shape: &dyn Draw = &circle;, компилятор создаёт fat pointer: { data: &circle, vtable: &vtable_Circle_Draw }. Когда вызываете shape.draw(), происходит: загрузить адрес vtable, прочитать указатель по смещению 24 (3 х 8, пропустив метаданные), прыгнуть по этому адресу. Всё.

Дженерики: а как оно работает по-другому

Чтобы понять, почему dyn Trait медленнее, нужно сначала понять, что делают дженерики. Разница не в «прямой vs. косвенный вызов»,она гораздо глубже.

Когда вы пишете обобщённую функцию:

fn draw_all<T: Draw>(shapes: &[T]) {
    for shape in shapes {
        shape.draw();
    }
}

…компилятор мономорфизирует её. Для каждого конкретного типа, с которым вы вызвали draw_all, создаётся отдельная копия:

// компилятор генерирует (концептуально):
fn draw_all_Circle(shapes: &[Circle]) {
    for shape in shapes {
        Circle::draw(shape);  // прямой вызов
    }
}

fn draw_all_Rectangle(shapes: &[Rectangle]) {
    for shape in shapes {
        Rectangle::draw(shape);  // прямой вызов
    }
}

В draw_all_Circle LLVM видит конкретный вызов Circle::draw. Не указатель на функцию,а саму функцию. Он знает, что внутри. И может:

Встроить тело — заменить call на тело Circle::draw прямо в цикле
Протащить константы — если radius известен, упростить вычисления
Автовекторизировать — обработать несколько элементов массива за одну SIMD-инструкцию
Убрать мёртвые ветки — если для конкретного типа какой-то if всегда ложен
Развернуть цикл — зная размер тела, оценить выгоду от разворачивания

Каждая из этих оптимизаций сама по себе даёт процентов пять-десять. Вместе логично в разы.

А теперь сравните с dyn-версией:

fn draw_all_dyn(shapes: &[Box<dyn Draw>]) {
    for shape in shapes {
        shape.draw();  // косвенный вызов через vtable
    }
}

LLVM видит: «Тут вызывается что-то по указателю. Я не знаю что. Может Circle::draw, может Rectangle::draw, может функция, которую подключили из другого крейта и которую я вообще не видел». Оптимизатор сдаётся, ни инлайнинга, ни автовекторизации, ни протаскивания констант.

Это цена dyn Trait.

Один mov — или всё-таки больше?

Ладно,сам косвенный вызов тоже не бесплатен.

При прямом вызове (дженерик, после мономорфизации):

call Circle::draw        ; адрес известен на этапе компиляции

Процессор знает адрес заране и предсказатель переходов легко справляется. Инструкция в pipeline ещё до того, как дойдёт до исполнения.

При косвенном вызове (через vtable):

mov  rax, [rsi + 8]      ; загрузить адрес vtable из fat pointer
mov  rax, [rax + 24]     ; загрузить адрес метода из vtable (смещение 24 = 3 × 8)
call rax                  ; вызвать по указателю

Два чтения из памяти перед вызовом. Если vtable в L1-кеше — это пара наносекунд. Если нет — десятки.

На практике vtable обычно в кеше, потому что она static и маленькая. Но вот предсказатель переходов уже другая история. call rax — непрямой переход, и процессор должен угадать, куда он ведёт. Если в цикле всегда один и тот же тип, предсказатель быстро обучится. Если типы чередуются (Circle, Rectangle, Circle, Rectangle…) — промахи почти точно будут.

Но конечно все это мелочевка по сравнению с потерянными оптимизациями. Косвенный вызов дорог не потому, что он сам по себе медленны, он дорог потому, что убивает всё остальное.

Стирание типов: что теряется и что остаётся

Когда вы создаёте dyn Trait, происходит стирание типа, на языке документаци type erasure. Компилятор забывает, какой конкретно тип спрятан за указателем. Это фундаментальное свойство, и из него вытекают все ограничения.

Что компилятор теряет:

Размер типа (восстанавливается из vtable, поле size)
Выравнивание (из vtable, поле align)
Конкретные реализации методов (через vtable, но без возможности инлайнинга)
Все методы, которых нет в трейте, их просто не существует в vtable

Что остаётся:

Указатель на данные
Указатель на vtable
Гарантия, что тип реализует трейт

Насчет «теряет размер типа» это и есть причина, по которой dyn Trait — это !Sized. Вы не можете положить dyn Draw на стек, не можете передать по значению, не можете вернуть из функции напрямую. Только через указатель: &dyn Draw, Box<dyn Draw>, Rc<dyn Draw>.

// Не скомпилируется:
fn make_shape() -> dyn Draw { ... }  // ошибка: размер неизвестен

// Скомпилируется:
fn make_shape() -> Box<dyn Draw> { ... }  // Box знает размер из vtable

Это, кстати, объясняет, почему Box<dyn Draw> может вызывать drop, он читает размер и деструктор из vtable. Без этих метаданных память утекла бы: Box не знал бы, сколько байт освобождать.

Почему не каждый трейт помещается в vtable

Не любой трейт можно превратить в dyn Trait. Раньше это называли «object safety» — безопасность для создания объектов. С Rust edition 2024 терминологию поменяли на «dyn compatibility» — совместимость с динамической диспетчеризацией. Суть осталась той же.

Ограничения вытекают из устройства vtable. Каждая запись в таблице — указатель на функцию с конкретной сигнатурой. Если сигнатуру невозможно определить без знания конкретного типа — запись невозможно создать.

Вот правила:

Методы не могут возвращать Self. Если метод возвращает Self, то возвращаемый тип зависит от конкретного типа. Circle::clone() возвращает Circle, Rectangle::clone() возвращает Rectangle. А в vtable — один слот на метод clone. Какой тип возвращает функция по этому указателю? Неизвестно. Компилятор не может сгенерировать код, который правильно обработает результат.

trait Clonable {
    fn clone(&self) -> Self;  // dyn-несовместимый: возвращает Self
}

Методы не могут иметь обобщённых параметров. Обобщённый метод fn foo<T>(&self, x: T) мономорфизируется для каждого T. Это значит, что для Circle::foo::<i32> и Circle::foo::<String> — разные функции. Сколько записей ставить в vtable? Компилятор не знает, с какими T метод будет вызван. Невозможно составить таблицу конечного размера.

trait Processor {
    fn process<T: Display>(&self, item: T);  // dyn-несовместимый: дженерик
}

Трейт не должен требовать Self: Sized. dyn Trait по определению !Sized — размер неизвестен на этапе компиляции. Если трейт требует Self: Sized, то dyn Trait не может его реализовать — противоречие.

Методы должны принимать self через ссылку или указатель. Статические методы (без self) некому вызывать, у vtable нет «получателя», через которого можно найти нужную таблицу.

Есть спасательный люк: where Self: Sized на отдельном методе. Он исключает метод из vtable, но оставляет трейт dyn-совместимым:

trait MyTrait {
    fn normal(&self);                          // попадает в vtable
    fn generic<T>(&self, x: T) where Self: Sized;  // исключён из vtable
}

// Работает:
let obj: &dyn MyTrait = &my_value;
obj.normal();      // ок
// obj.generic(42);  // ошибка компиляции: метод недоступен через dyn

Хороший приём, если нужна dyn-совместимость, но хочется оставить обобщённые методы для тех, кто работает с конкретными типами.

Гетерогенные коллекции: единственное, чего не умеют дженерики

Окей, dyn медленнее. Зачем он тогда? Ответ простой: дженерики работают только с однородными данными.

fn draw_all<T: Draw>(shapes: &[T]) { ... }

Все элементы shapes одного типа. &[Circle] или &[Rectangle], но не смесь. Компилятор обязан знать тип на этапе компиляции, чтобы мономорфизировать функцию.

А если вам нужен вектор из разных типов, которые реализуют один трейт?

let widgets: Vec<Box<dyn Draw>> = vec![
    Box::new(Button { label: "OK".into() }),
    Box::new(TextField { text: "hello".into() }),
    Box::new(Slider { value: 0.5 }),
];

for w in &widgets {
    w.draw();  // каждый элемент может быть другого типа
}

Вот это дженерики не умеют. Это территория dyn Trait. Гетерогенная коллекция — самый базовый случай, когда динамическая диспетчеризация не просто допустима, а единственно возможна.

Ещё один случай — когда конкретный тип определяется в рантайме:

fn make_backend(config: &Config) -> Box<dyn Storage> {
    match config.storage_type {
        StorageType::S3 => Box::new(S3Backend::new(config)),
        StorageType::Local => Box::new(LocalBackend::new(config)),
        StorageType::Memory => Box::new(MemoryBackend::new()),
    }
}

Какой тип вернёт функция? Зависит от конфигурации. Компилятор не может мономорфизировать то, что неизвестно на этапе компиляции. dyn Trait — единственный выход.

Enum dispatch: третий путь, о котором забывают

Но есть хитрый приемчик, если вы знаете все возможные типы на этапе компиляции — вам, может быть, не нужен ни dyn, ни дженерик. Есть enum dispatch.

enum Shape {
    Circle(Circle),
    Rectangle(Rectangle),
    Triangle(Triangle),
}

impl Shape {
    fn draw(&self) {
        match self {
            Shape::Circle(c) => c.draw(),
            Shape::Rectangle(r) => r.draw(),
            Shape::Triangle(t) => t.draw(),
        }
    }
    
    fn area(&self) -> f64 {
        match self {
            Shape::Circle(c) => c.area(),
            Shape::Rectangle(r) => r.area(),
            Shape::Triangle(t) => t.area(),
        }
    }
}

Vec<Shape> — гетерогенная коллекция, но без vtable. Диспетчеризация через match — прямые переходы, предсказуемые процессором. LLVM может заглянуть внутрь каждой ветки и оптимизировать.

Цена: все типы должны быть известны заранее.

Добавление нового варианта — это правка enum и всех match. Для плагинной архитектуры не подходит. Для закрытого набора типов — очень даже годный вариант.

Кеш и layout

Есть ещё один моментик, о котором редко говорят. Vec<Box<dyn Draw>> — это вектор указателей. Каждый Box — адрес где-то в куче. Сами объекты разбросаны по памяти. Когда вы итерируете по такому вектору, процессор на каждом шаге прыгает по новому адресу.

Сравните с Vec<Circle> , все Circle лежат плотно, один за другим. Процессор загружает кеш-линию и в ней сразу несколько элементов. Итерация по такому массиву намного быстрее.

Это, кстати, аргумент в пользу enum dispatch. Vec<Shape> тоже лежит плотно (хотя с оговоркой,размер каждого элемента — максимум из вариантов, и маленькие типы будут платить за большие. Но всё равно — это один непрерывный блок памяти, а не бардак из указателей.

Если вам необходим dyn Trait, но важна локальность данных, можно использовать arena-аллокатор (например, bumpalo). Вы аллоцируете все объекты в одном регионе памяти и они физически лежат рядом, даже будучи разных типов. В общем интересно что вы насчет этого думаете, пишите в комменты.

Что происходит при приведении: конструирование fat pointer

Момент, когда тип заворачивается в dyn Trait, стоит рассмотреть отдельно. В C++ приведение к базовому классу у нас бесплатная операция (или сложение со смещением при множественном наследовании). В Rust не совсем.

let circle = Circle { radius: 5.0 };
let shape: &dyn Draw = &circle;

Что происходит: компилятор конструирует fat pointer. Он берёт адрес circle и добавляет к нему адрес vtable для пары (Circle, Draw). Получается { data: &circle, vtable: &vtable_Circle_Draw }.

Это не бесплатно,но стоимость мизерная: один lea для загрузки адреса vtable. Vtable — static, адрес известен на этапе компиляции.

Обратная операция — downcast, приведение обратно к конкретному типу — в Rust без помощи невозможна. Стандартный dyn Trait не знает, какой тип внутри. Для этого нужна либо дополнительная инфраструктура (трейт Any с downcast_ref), либо собственная логика через enum.

use std::any::Any;

let shape: Box<dyn Any> = Box::new(Circle { radius: 5.0 });
if let Some(circle) = shape.downcast_ref::<Circle>() {
    println!("radius: {}", circle.radius);
}

Any работает через TypeId — уникальный идентификатор типа. downcast_ref сравнивает TypeId запрошенного типа с TypeId реального типа, хранящегося в объекте. Если совпали — возвращает ссылку, если нет — None. Это рантайм-проверка, но оч дешевая.

Когда dyn, когда дженерик

Я долго шёл к тому, чтобы перестать думать об этом как о «быстро vs. медленно» и начать думать в категориях задач. Вот как я принимаю решение.

Дженерик — когда набор типов известен на этапе компиляции, и вы хотите максимальную производительность. Библиотечные функции, алгоритмы, горячие пути. fn sort<T: Ord>(slice: &mut [T]) — классический пример. Компилятор создаст специализированную версию для каждого типа, и LLVM выжмет из неё максимум.

dyn Trait — когда типы определяются в рантайме, или когда нужна гетерогенная коллекция, или когда вы хотите скрыть конкретный тип за абстракцией (плагины, trait objects). Также когда мономорфизация раздувает бинарник до неприличия и вы осознанно жертвуете производительностью ради размера.

Enum dispatch — когда типов конечное количество, все известны заранее, и вы хотите гетерогенность без vtable. Закрытые наборы: виды AST-узлов, варианты команд, типы событий.

И ещё: impl Trait в возвращаемом типе. Это не dyn — это статическая диспетчеризация, но с скрытым конкретным типом:

fn make_iter() -> impl Iterator<Item = i32> {
    (0..10).filter(|x| x % 2 == 0)
}

Компилятор знает конкретный тип, мономорфизирует, инлайнит. Вызывающий код не видит тип, но LLVM видит.

Суперрейты и vtable

Когда трейт наследуется от другого трейта, vtable становится интереснее:

trait Shape: Draw {
    fn perimeter(&self) -> f64;
}

Shape требует Draw. Vtable для dyn Shape содержит методы обоих трейтов. И метаданные тоже — drop, size, align. Если цепочка наследования длинная, vtable растёт.

С Rust 1.76 появилась возможность upcasting трейт-объектов: можно привести &dyn Shape к &dyn Draw. Для этого vtable Shape может содержать дополнительный указатель на vtable Draw (поле TraitVPtr), если layout не позволяет просто отрезать хвостик таблицы.

Всё это конечно просто детали реализации, которые могут меняться между версиями компилятора. Vtable layout в Rust не стабилизирован и не является частью публичного ABI.

Размер бинарника

Всю статью я тут рассказывал, что дженерики быстрее. Это правда, но у них тоже есть своя цена!

Каждая мономорфизация fn foo<T: Trait>(x: T) для нового типа T — это отдельная копия функции в бинарнике. Если foo вызывается с двадцатью типами — двадцать копий. Если foo большая и вызывает другие обобщённые функции, которые тоже мономорфизируются — комбинаторный взрыв.

Десериализация serde_json::from_str::<T>() мономорфизируется для каждого T, и каждая версия тащит за собой цепочку обобщённых вызовов. В гига проектах с десятками типов данных вклад serde в размер бинарника может исчисляться мегабайтами.

dyn Trait эту проблему решит, одна копия функции, которая работает с любым типом через vtable. Меньше кода, быстрее компиляция, меньше бинарник, меньше давление на кеш инструкций.

Та же самая дилемма, которую мы видели с #[inline]: больше встроенного кода — быстрее выполнение, но больше бинарник и давление на L1i. Адекватный выбор зависит от конкретной задачи.

Что со всем этим делать

Если тип известен — дженерик. Если нет — dyn. Если типов конечный набор — enum dispatch.

А самый продуктивный рефакторинг, который я видел в контексте трейт-объектов — это замена Vec<Box<dyn Handler>> на enum из четырёх вариантов.

Спасибо за прочтение статьи. Делитесь опытом в комментариях.

Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.

Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.

Как Rust реализует трейт-объекты и почему dyn Trait медленнее дженериков