Вывод

Полиморфизм в Rust

Перевод | Автор оригинала: Matt Oswalt

В предыдущем посте мы исследовали использование универсальных типов в Rust и некоторые из распространенных причин для этого. В этом посте я хотел бы сделать шаг назад и взглянуть на полный спектр возможностей, которые Rust предоставляет для реализации полиморфизма, и углубиться в подробности, чтобы мы полностью понимали компромиссы в решениях, которые мы принимаем как разработчики Rust.

Полиморфный выбор Rust

Если вы читаете этот пост, то почти наверняка слышали о термине «полиморфизм». По-моему, полиморфизм дает нам возможность представить единый интерфейс для потенциально многих различных конкретных типов. Это позволяет нам создавать более гибкие API-интерфейсы, которые дают больше контроля потребителю и проще в обслуживании.

Использование полиморфизма дает несколько практических преимуществ, но одно из самых больших - это повторное использование кода. Если вы разрабатываете API на основе определенных конкретных типов, то вы, как и ваши потребители, привержены этому подходу.

Например, если мы написали функцию, которая требует типа - Lion в качестве параметра, мы строго привязаны к этому решению. Если бы мы хотели иметь аналогичные функции, но для других типов, нам пришлось бы создать дополнительные функции, принимающие эти типы. Это приводит к излишнему дублированию кода, который становится трудно поддерживать.

Вместо этого полиморфизм позволяет нам создавать функции, которые принимают любой тип, если эти типы демонстрируют определенное поведение или свойства, которые нам нужны. В этом примере мы можем принять любой конкретный тип, если они реализуют метод Growl().

В данном случае это поведение - это все, что нас волнует, поэтому мы можем использовать полиморфизм, чтобы быть более гибкими, но при этом поддерживать набор необходимых функций. Благодаря этому мы можем писать одну функцию, которая принимает несколько типов.

Это общая идея, почему мы хотели бы использовать полиморфизм на любом языке, но какие варианты полиморфизма существуют в Rust? Есть два основных способа, и оба из них требуют компромиссов, когда речь идет о производительности, а также о размере двоичного файла:

Статическая диспетчеризация - этот подход использует универсальные шаблоны (также называемые параметрическим полиморфизмом) и (обычно) границы трэйтов, чтобы обеспечить необходимую гибкость, сохраняя при этом полную безопасность типов и не требуя большого количества повторяющегося кода. Этот подход чрезвычайно производительный (в Rust это известно как «абстракция с нулевой стоимостью»), однако из-за мономорфизации это создает больший двоичный размер.
Динамическая диспетчеризация - этот подход использует «характерные объекты» для принятия решения о том, какой тип требуется для удовлетворения некоторого вида полиморфного интерфейса для среды выполнения. Это сокращает двоичный размер (поскольку здесь не используется мономорфизация), но снижает производительность из-за дополнительного поиска во время выполнения. Этот подход также явно запрещает использование дженериков.

Хотя есть и другие причины выбрать тот или иной подход - например, удобочитаемость - в целом, вы можете рассматривать это решение как компромисс между размером двоичного файла и производительностью. Если вы можете терпеть немного больший размер двоичного файла, но производительность важна, статический подход, вероятно, будет вашим лучшим выбором. Для тех, кому не нужна максимальная производительность, но размер двоичного файла имеет решающее значение (вероятным примером могут быть встроенные системы), динамический подход, вероятно, предпочтительнее.

Что лично для меня более интересно, так это то, что Rust - это первый язык, который я использовал, который дает такой выбор. Языки, в которых нет универсальных шаблонов, вынуждают разработчика либо написать кучу дублированного кода, чтобы получить преимущества «статического» подхода, либо снизить производительность, вызванную «динамическим» подходом. Я знаю, что есть другие языки, которые предоставляют такой выбор (C++ - один из них), но способ, которым это делается в Rust, действительно хорош.

Именно этот выбор я хочу изучить более глубоко.

РЕДАКТИРОВАТЬ: очень полезный редактор указал на несколько вещей, о которых следует помнить при чтении этого сообщения в блоге. Примеры для подражания были сделаны путем отключения встраивания и сборки в режиме «отладки», чтобы немного облегчить процесс обучения, но я не очень хорошо выделил этот вариант. Сборка в режиме выпуска и возможность встраивания Rust там, где это необходимо, вероятно, значительно изменит итоговую программу.

Трэйта «Growler» и ее реализации

Для этого поста я создал трейт под названием Growler, который обеспечивает реализацию единственного метода Growl(), не имеющего параметров или возвращаемых типов. Я также создал три типа Льва, Тигра и Медведя, которые имеют свои собственные реализации этой трэйты. Мы будем использовать эти три типа, чтобы продемонстрировать разницу между статической и динамической отправкой:

trait Growler {
    fn growl(&self);
}

struct Lion;
impl Growler for Lion {
    #[inline(never)]
    fn growl(&self) {
        println!("Lion says GROWL!");
    }
}
struct Tiger;
impl Growler for Tiger {
    #[inline(never)]
    fn growl(&self) {
        println!("Tiger says GROWL!");
    }
}
struct Bear;
impl Growler for Bear {
    #[inline(never)]
    fn growl(&self) {
        println!("Bear says GROWL!");
    }
}

Независимо от метода, который мы исследуем ниже (статического и динамического), этот код останется прежним. Разница между статической и динамической диспетчеризацией не в объявлении этой трэйты или в типах и методах, которые ее реализуют, а в том, как мы их используем в нашем коде Rust, и, что более важно, в том, как эти два подхода на самом деле работают под капотом в наша скомпилированная программа.

Статическая отправка

В качестве напоминания о дженериках в Rust мы можем использовать дженерики в нескольких местах. При определении функции мы можем определить универсальный тип в сигнатуре функции, а затем ссылаться на этот тип для одного из параметров:

fn static_dispatch<T: Growler>(t: T) {
    t.growl();
}

Как мы узнали ранее, определяя трэйту Growler как привязку к универсальному параметру T, любой передаваемый тип должен реализовывать эту трэйту. Итак, в нашей функции main() мы можем передать наши три конкретных типа, которые, как мы знаем, реализуют эту трэйту:

pub fn main() {
    static_dispatch(Lion{});
    static_dispatch(Tiger{});
    static_dispatch(Bear{});
}

Этот подход использует подход «статической диспетчеризации», который использует «мономорфизацию» во время компиляции для создания нескольких копий нашей функции static_dispatch - по одной для каждого типа, который когда-либо в нее передавался. Это более эффективный подход, поскольку мы можем по существу встроить все наши пути выполнения в результирующую программу без необходимости вычислять это во время выполнения.

Признаки мономорфизации можно сразу увидеть, используя objdump для просмотра инструкций в нашей скомпилированной программе на Rust:

objdump --disassemble=polymorphism::main -S -C target/debug/polymorphism -EL -M intel --insn-width=8

target/debug/polymorphism:     file format elf64-x86-64

0000000000005510 <polymorphism::main>:
    5510:       48 83 ec 18                     sub    rsp,0x18
    5514:       e8 47 fe ff ff                  call   5360 <polymorphism::static_dispatch>
    5519:       e8 12 fe ff ff                  call   5330 <polymorphism::static_dispatch>
    551e:       e8 6d fe ff ff                  call   5390 <polymorphism::static_dispatch>

Наша функция static_dispatch не имеет параметров, и ее вызов - это первое, что мы делаем в нашей функции main(), поэтому первое, что мы видим, - это три вызова местоположения этой функции в памяти. Однако вы заметите, что все три местоположения разные - 5360, 5330 и 5390. Это потому, что на самом деле это три разные функции - по одной для каждого из наших конкретных типов.

0000000000005330 <polymorphism::static_dispatch>:
    5330:       48 83 ec 18                     sub    rsp,0x18
    5334:       48 89 e7                        mov    rdi,rsp
    5337:       e8 34 01 00 00                  call   5470 <<polymorphism::Tiger as polymorphism::Growler>::growl>
    ...

0000000000005360 <polymorphism::static_dispatch>:
    5360:       48 83 ec 18                     sub    rsp,0x18
    5364:       48 89 e7                        mov    rdi,rsp
    5367:       e8 b4 00 00 00                  call   5420 <<polymorphism::Lion as polymorphism::Growler>::growl>
    ...

0000000000005390 <polymorphism::static_dispatch>:
    5390:       48 83 ec 18                     sub    rsp,0x18
    5394:       48 89 e7                        mov    rdi,rsp
    5397:       e8 24 01 00 00                  call   54c0 <<polymorphism::Bear as polymorphism::Growler>::growl>
    ...

Компилятор взял нашу единственную функцию static_dispatch в Rust и во время компиляции создал по одному экземпляру для каждого конкретного типа, который ему когда-либо передавался. Затем в каждой из этих функций выполняется запекание вызова соответствующей реализации метода, поэтому в каждой из них вы видите вызов метода Growl() трех разных типов.

Теперь должно быть очевидно, почему подход «статической диспетчеризации» приводит к большему двоичному размеру - компилятор может выполнять все эти предварительные оптимизации, но должен хранить весь мономорфный код в самом двоичном файле. Однако наша программа более эффективна, поскольку решения о том, какие функции вызывать, в зависимости от того, какие типы, принимаются во время компиляции, а не во время выполнения. Код на Rust, который мы должны поддерживать, по-прежнему настолько элегантен и лаконичен, насколько мы хотим.

Между прочим, на этот подход никак не влияет с точки зрения производительности присутствие граничного трэйта (фактически, полученная скомпилированная программа идентична). Это по-прежнему абстракция с нулевой стоимостью - единственное отличие состоит в том, что добавление границ характеристик добавляет проверки во время компиляции, для каких конкретных типов можно использовать в качестве параметра нашей функции. Если бы мы передали тип, в котором не реализована трэйта Growler, наш код просто не компилировался бы.

В этом суть того, что делает этот «статический» подход к полиморфизму таким мощным. Мы пишем краткий код, а компилятор позаботится обо всем остальном, чтобы производительность оставалась высокой.

Динамическая отправка

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

В Rust этот подход использует «Trait Objects» для достижения полиморфизма. В отличие от границ трэйтов, которые являются необязательным ограничением, которое вы можете добавить к универсальным параметрам, объекты трэйтов на самом деле вообще не могут использоваться с универсальными шаблонами, и вместо этого являются обязательным методом для выполнения динамической диспетчеризации в Rust.

В наши дни синтаксис объектов-трэйтов характеризуется ключевым словом dyn, за которым следует имя трэйта:

fn dynamic_dispatch(t: &dyn Growler) {
    t.growl();
}

Ключевое слово dyn было введено в Rust 1.27 и теперь является идиоматическим способом явно указать, что вы хотите использовать динамическую диспетчеризацию через объекты трейтов. Несмотря на то, что на момент написания этой статьи все еще можно подразумевать использование трейт-объектов без этого ключевого слова, оно официально признано устаревшим, и в конечном итоге у вас не будет другого выбора, кроме как использовать это ключевое слово в будущей версии Rust.

Несмотря на то, что мы не используем общие параметры, компилятору все равно нужна небольшая помощь, чтобы узнать размер наших типов во время компиляции. Вот почему вы обычно видите границы трэйтов, переданные через ссылку, как в приведенном выше примере, но это также можно сделать, заключив объект трэйта в контейнеры, такие как Box, Rc или Arc<dyn Гроулер>.

Затем мы можем вызвать их из основной функции, передав ссылки на каждый тип:

dynamic_dispatch(&Lion{});
dynamic_dispatch(&Tiger{});
dynamic_dispatch(&Bear{});

Давайте заглянем под капот и посмотрим, что компилятор Rust произвел для этих вызовов:

0000000000005510 <polymorphism::main>:
    ...
    # "dynamic_dispatch" call with "Lion" type
    #
    # Populates "rax" with a pointer to 0x43558
    5523:   48 8d 05 2e e0 03 00        lea    rax,[rip+0x3e02e]        # 43558
    552a:   48 8b 0d ef df 03 00        mov    rcx,QWORD PTR [rip+0x3dfef]        # 43520
    5531:   48 89 cf                    mov    rdi,rcx
    # Moves pointer in "rax" into "rsi" register
    5534:   48 89 c6                    mov    rsi,rax
    5537:   e8 44 00 00 00              call   5580 <polymorphism::dynamic_dispatch>

    # "dynamic_dispatch" call with "Tiger" type
    553c:   48 8d 05 35 e0 03 00        lea    rax,[rip+0x3e035]        # 43578
    5543:   48 8b 0d d6 df 03 00        mov    rcx,QWORD PTR [rip+0x3dfd6]        # 43520
    554a:   48 89 cf                    mov    rdi,rcx
    554d:   48 89 c6                    mov    rsi,rax
    5550:   e8 2b 00 00 00              call   5580 <polymorphism::dynamic_dispatch>

    # "dynamic_dispatch" call with "Bear" type
    5555:   48 8d 05 3c e0 03 00        lea    rax,[rip+0x3e03c]        # 43598
    555c:   48 8b 0d bd df 03 00        mov    rcx,QWORD PTR [rip+0x3dfbd]        # 43520
    5563:   48 89 cf                    mov    rdi,rcx
    5566:   48 89 c6                    mov    rsi,rax
    5569:   e8 12 00 00 00              call   5580 <polymorphism::dynamic_dispatch>
    ...

Выше я добавил интервал, чтобы было легче следить за ним. Короче говоря, каждый раздел отвечает за выполнение некоторых вычислений перед вызовом функции dynamic_dispatch, которая в конечном итоге будет использоваться для определения того, какой базовый конкретный тип и метод используется.

Наиболее важные вычисления выполняются первой инструкцией в каждом разделе, которая загружает указатель (инструкцию lea) в регистр rax. Например, раздел «Лев» загружает локацию, полученную в результате добавления rip + 0x3e02e. К счастью, компилятор намекнул, к чему это приведет - 0x43558 (показано как комментарий справа). Раздел Tiger загружает 0x43578, а раздел Bear загружает 0x43598. Мы немного разберемся, что означают эти значения.
Затем в четвертой строке содержимое регистра rax (который содержит результат первой инструкции) копируется в rsi.
Наконец, в последней строке каждого раздела вы можете увидеть вызов местоположения 5580 - нашей функции dynamic_dispatch. Все три раздела вызывают одно и то же местоположение - это разительно отличается от того, что мы видели в разделе статической диспетчеризации, где каждый вызов выполнялся в разное место в памяти. Это сильный ранний трэйт того, что здесь не использовалась мономорфизация!

Затем давайте взглянем на нашу функцию dynamic_dispatch. В отличие от раздела, в котором мы обсуждали статическую отправку и «мономорфизацию», мы находим только одну копию этой функции в скомпилированной программе:

0000000000005580 <polymorphism::dynamic_dispatch>:
fn dynamic_dispatch(t: &dyn Growler) {
    5580:   48 83 ec 18                 sub    rsp,0x18
    5584:   48 89 7c 24 08              mov    QWORD PTR [rsp+0x8],rdi
    5589:   48 89 74 24 10              mov    QWORD PTR [rsp+0x10],rsi

    # This is where the concrete type's method is called
    558e:   ff 56 18                    call   QWORD PTR [rsi+0x18]
    ...

Причина, по которой наша функция dynamic_dispatch может появляться один раз в скомпилированной программе, заключается в том, что она предназначена для вызова функции в вычисленном месте, в частности, смещении на основе любого значения в регистре rsi. Вот почему наша программа выполняет тяжелую работу по вычислению указателя на нужное место в памяти и размещению его в rsi перед вызовом функции dynamic_dispatch.

Итак, из предыдущего примера мы знаем, что rsi будет содержать 0x43558, когда используется наш тип Lion, 0x43578 для Tiger и 0x43598 для Bear. Но что на самом деле означают эти значения? И почему программа добавляет к этому значению 0x18 перед вызовом полученной ячейки памяти?

Это подводит нас к сути того, что на самом деле представляет собой типаж-объект. Короче говоря, это указатель. В частности, это указатель на часть памяти, в которой можно найти методы привязки типа, а также на некоторые другие вещи (например, деструкторы). Это обычно называется «таблицей виртуальных методов» или «vtable».

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

Каждая из трех ячеек памяти, загружаемых в rsi на протяжении всего жизненного цикла нашей программы, является местом, где находится vtable другого типа:

К сожалению, у меня возникли проблемы с поиском vtable в выводе objdump - по какой-то причине то, что я нашел в указанном смещении, полностью отличалось от того, что мне показывали другие инструменты, и я не мог понять, почему. Итак, текст ниже скопирован с действительно классного визуального дизассемблера Cutter.

0x00043558      .qword 0x00000000000052b0 ; sym.core::ptr::drop_in_place::h1a84c45b0db95228 ; dbg.drop_in_place_polymorphism::Lion; RELOC 64 
0x00043560      .qword 0x0000000000000000
0x00043568      .qword 0x0000000000000001
0x00043570      .qword 0x0000000000005420 ; sym._polymorphism::Lion_as_polymorphism::Growler_::growl::h9ba07c281cda2327; RELOC 64 

0x00043578      .qword 0x00000000000052d0 ; sym.core::ptr::drop_in_place::hbe44f9f0e5cd7b58 ; dbg.drop_in_place_polymorphism::Tiger; RELOC 64 
0x00043580      .qword 0x0000000000000000
0x00043588      .qword 0x0000000000000001
0x00043590      .qword 0x0000000000005470 ; sym._polymorphism::Tiger_as_polymorphism::Growler_::growl::hd8d4c2f459b86277; RELOC 64

0x00043598      .qword 0x00000000000052c0 ; sym.core::ptr::drop_in_place::h5b23dc3563c0609b ; dbg.drop_in_place_polymorphism::Bear; RELOC 64 
0x000435a0      .qword 0x0000000000000000
0x000435a8      .qword 0x0000000000000001
0x000435b0      .qword 0x00000000000054c0 ; sym._polymorphism::Bear_as_polymorphism::Growler_::growl::h4af959d647eb2439 ; dbg.growl; RELOC 64

Опять же, я добавил некоторый интервал, чтобы было легче следовать. Вы заметите, что каждая из трех ячеек памяти, загруженных в rsi, отмечает начало vtable каждого типа в памяти. Однако часть vtable, содержащая указатель на метод, который мы хотим вызвать, на самом деле находится со смещением в 24 байта от начала каждой таблицы. Между прочим, шестнадцатеричный эквивалент для этого - 0x18, поэтому наша функция dynamic_dispatch добавляет это к rsi перед инструкцией вызова. rsi содержит расположение vtable для нужного нам типа, и добавление к нему 0x18 приводит нас к записи в этой vtable, к которой мы хотим получить доступ.

Однако то, что здесь находится, все же не наш метод, а скорее еще один указатель. Например, ячейка памяти 0x43570 просто содержит указатель на 0x5420. Именно здесь мы можем найти наш метод. Вот почему функция dynamic_dispatch использует вызов инструкции QWORD PTR [rsi + 0x18] - сначала загружает значение, расположенное в rsi + 0x18, в качестве указателя, а затем вызывает ячейку памяти, представленную этим указателем.

Если присмотреться, каждый из этих указателей должен показаться знакомым - 5420, 5470, 54c0. Это те же адреса, по которым мы видели методы для каждого типа в разделе статической отправки! Независимо от того, используем ли мы статическую или динамическую отправку, эти функции все равно должны существовать в нашей программе - разница в том, как мы получаем к ним доступ.

Как видите, динамическая отправка использует противоположный подход по сравнению со статической отправкой. Вместо дублирования полиморфных функций на основе используемых типов создается одна реализация, но эта реализация предназначена для вызова различных базовых типов и методов на основе указателя, который вычисляется во время выполнения. Из-за отсутствия дублирования кода размер двоичного файла меньше, но из-за необходимости выполнения дополнительного поиска наблюдается небольшое снижение производительности. Я оставлю анализ этого удара по производительности другим - есть много сообщений в блогах, которые делают работу по сравнительному анализу динамической диспетчеризации намного лучше, чем я когда-либо.

Вывод

Это была забавная запись в блоге, которая дала мне гораздо лучшее понимание не только вариантов полиморфизма Rust, но и лучшего понимания того, как другие языки предлагают аналогичные компромиссы. Надеюсь, это было полезно и для вас.

Я создал проект в Compiler Explorer, который содержит полную программу с обоими подходами. Это отличный инструмент, который позволяет очень легко увидеть, как наша программа на самом деле работает под капотом, поэтому, если вам не нравится использовать objdump или Cutter, это также отличный инструмент для обучения.

Дополнительные ссылки

Некоторые дополнительные ссылки, которые я нашел в своем исследовании, не вошли в текст этого сообщения:

Очень полезный и поучительный пример Compiler Explorer; был вдохновлен на создание своего собственного из этого.
Полезный SO-поток, в котором обсуждаются контейнеры трейт-объектов и таблицы vtables.
Еще один полезный пост о том, как это делается в Rust, с некоторыми классными графическими диаграммами Cutter.