Lewigh Jul 4 at 10:33

Гайд на полиморфизм. Что там под капотом?

Medium

19 min

5.6K

Tutorial

Гайд на полиморфизм. Основные идеи
Гайд на полиморфизм. Что там под капотом?
Гайд на полиморфизм. Rust

В прошлой статье мы рассмотрели теоретическую основу такого понятия как полиморфизм и изучили различные его виды. Теперь предлагаю перейти к рассмотрению того как оно устроено «под капотом».

Проблема

Неискушенный читатель может задаться вопросом:

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

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

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

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

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

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

Однако у неё есть важное ограничение: все передаваемые данные должны быть заранее известного, фиксированного размера. С регистрами всё очевидно — мы не можем поместить в них что угодно. Что касается стека, адресация переменных в нём осуществляется через смещение относительно базового указателя, а значит, это смещение должно быть фиксированным.

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

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

резервированием
упаковкой
синтетически

Резервирование

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

Предположим, у нас есть зеленый тип размером 4 байта, синий — 8 байт, а красный — 16 байт. Чтобы все типы гарантированно помещались в отведенную область памяти, в качестве базового выбирается самый крупный — красный.

Простые примеры на C:

int64_t mul2_n(int64_t n) {
    return n * 2;
}

int main() {
    int8_t i8 = 1;
    int16_t i16 = 2;
    int32_t i32 = 3;
    int64_t i64 = 4;

    int64_t res1 = mul2_n(i8);
    int64_t res2 = mul2_n(i16);
    int64_t res3 = mul2_n(i32);
    int64_t res4 = mul2_n(i64);

    printf("%d %d %d %d\n", res1, res2, res3, res4);

    return 0;
}

Функция mul2_n может принимать любые типы, размер которых меньше или равен 8 байтам. Рассмотрим нечто более интересное. В языке C для таких случаев предусмотрены объединения (union), позволяющие представить значение в виде одного из нескольких возможных вариантов.

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

Результат может быть следующим:

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

Эту задачу можно решить довольно элегантно — описав все возможные состояния через union.

Реализация вариантов

typedef struct {
    uint32_t total;
    uint32_t left;
} loading_t;

typedef struct {
    uintptr_t *body;
    uint32_t len;
    uint32_t _padding;
} done_t;

typedef struct {
    uint8_t _dummy;
} not_found_t;

typedef struct {
    char *msg_ptr;
    uint32_t len;
    uint32_t status;
} error_t;

typedef union {
    // 8 bytes
    loading_t loading;
    // 16 bytes
    done_t done;
    // 1 byte
    not_found_t not_found;
    // 16 bytes
    error_t error;
} response_status_t;

response_status_t check_response(int32_t ops_descriptor) {
    // ...
}

Напомню: response_status_t объединяет в себе несколько вариантов данных, но фактически в переменной хранится только один из них.

Возникает небольшая проблема — как определить, какой именно вариант был возвращен функцией check_response?

response_status_t response = check_response(desc);
//response???

Исправить ситуацию можно по разному, например добавлением тэгов:

#define RES_TYPE_LOADING 0
#define RES_TYPE_DONE 1
#define RES_TYPE_NOT_FOUND 2
#define RES_TYPE_ERROR 3

typedef struct {
    response_status_t status;
    uint8_t tag;
    uint8_t _padding[7];
} response_t;

response_t check_response(int32_t ops_descriptor) {
    // ...
}

Использовать можно подобным образом:

//...
response_t response = check_response(desc);

uint8_t tag = response.tag;

if (tag == RES_TYPE_LOADING) {
    loading_t loading = response.status.loading;
    printf("Is loading. Total:%d Left:%d\n", loading.total, loading.left);
}
else if (tag == RES_TYPE_DONE) {
    done_t done = response.status.done;
    printf("Is done. Len:%d\n", done.len);
}
else if (tag == RES_TYPE_NOT_FOUND) {
    printf("Not found\n");
}
else if (tag == RES_TYPE_ERROR) {
    error_t err = response.status.error;
    printf("Is err. Status:%d Msg:%s\n", err.status, err.msg_ptr);
}
else {
    printf("Unexpected status with tag %d\n", tag);
}
//...

Получаем: payload — 1-16 байт, tag — 1 байт, выравнивание — 7 байт. Итого — 24 байта.

К плюсам такого подхода можно отнести высокую производительность (при разумном размере) и простоту реализации.

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

Упаковка(boxing)

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

Итак, данные произвольных размеров хранятся в куче, указатели можно передавать без ограничений — но как работать с разнородными типами? Логичный ответ — обобщить. А как быть с обобщённым API, где разные типы реализуют свои методы по-разному?

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

Начнём с простого: у нас есть функция fu2(), расположенная по адресу 0x7ffc1f2e977d. В месте вызова (call site) этой функции будет находиться её адрес. Таким образом, при вызове функции мы можем перейти к её определению напрямую. Такой вызов называется прямым (direct call).

Но что, если на этапе компиляции неизвестен адрес определения функции?

Допустим, у нас есть некий абстрактный тип Document и его реализации —MainDocument и AccompanyingDocument. Вопрос: какие адреса будут у методов типа Document? Думаю, очевидно, что у абстрактного типа их быть не может.

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

Для решения этой проблемы используются виртуальные методы.

Виртуальный метод — это метод, реализация которого заранее неизвестна и определяется только в момент вызова.

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

В этом примере вызывается метод tostring у объекта типа Child. Сначала извлекается таблица дескрипторов, затем в ней выполняется поиск метода по имени. Метода там нет, так как он не переопределён типом. Поэтому поиск продолжается в родительской таблице, после чего происходит вызов.

Очевидно, что такой способ крайне неэффективен. Мало того, что вместо обычного вызова нам нужно сначала получить таблицу дескрипторов — так ещё и приходится искать нужный метод перебором, сравнивая строки по имени.

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

Чуть лучше, но всё ещё слишком медленно. Есть решение поинтересней — таблица виртуальных методов (или vtable/vmt).

Суть довольно проста: мы по-прежнему создаем таблицу для каждого типа, но вместо дескрипторов методов храним в ней адреса их реализаций. И главное — в месте вызова (call site) хранится не имя метода, а его индекс в vtable.

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

Уже намного лучше. Для лучшего понимания рассмотрим данную идею на C. Определим структуру и методы родителя:

typedef struct {
    intptr_t *_vmt;
    int32_t id;
} base_t;

void base_tostring(base_t *this) {
    printf("{id: %d}\n", this->id);
}

bool base_equals(base_t *one, base_t *other) {
    return one->id == other->id;
}

Обратите внимание на base_t: в нём, помимо полезной нагрузки в виде id, есть дополнительное поле _vmt. Это указатель на ту самую таблицу виртуальных методов.

Также имеется дочерняя сущность, созданная по аналогии, но с переопределённым методом tostring.

Child

typedef struct {
    intptr_t *_vmt;
    int32_t id;
    char *name;
} child_t;

void child_tostring(child_t *this) {
    printf("{id: %d, text: \"%s\"}\n", this->id, this->name);
}

Определим псевдонимы для типов указателей на функции:

typedef void (*base_t_to_string_type)(base_t *);
typedef void (*child_t_to_string_type)(child_t *);

typedef bool (*base_t_equals_type)(base_t *, base_t *);
typedef bool (*child_t_equals_type)(child_t *, child_t *);

Теперь самое интересное — определяем таблицы виртуальных методов:

const int32_t TO_STRING_SLOT = 0;
const int32_t EQUALS_SLOT = 1;

intptr_t base_vmt[] = {(intptr_t)base_tostring, (intptr_t)base_equals};
intptr_t child_vmt[] = {(intptr_t)child_tostring, (intptr_t)base_equals};

Слот 0 указывает на метод tostring, а слот 1 — соответственно на equals. Готовим две таблицы и заполняем их в соответствии со слотами. Таблица содержит указатели, которые ссылаются на целевые функции: слот — указатель на конкретную реализацию для данного типа.

Для удобства определяем вспомогательные функции:

Функции создания

base_t *new_base(int id) {
    base_t *base_ptr = malloc(sizeof(base_t));
    *base_ptr = (base_t){._vmt = base_vmt, .id = id};

    return base_ptr;
}

child_t *new_child(int id, char *name) {
    child_t *ptr = malloc(sizeof(child_t));
    *ptr = (child_t){._vmt = child_vmt, .id = id, .name = name};

    return ptr;
}

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

// new base_t(1)
base_t *base_ptr = new_base(1);
// new child_t(1, 2)
child_t *child_ptr = new_child(1, "John Smith");
child_t *child_ptr2 = new_child(2, "Alex Johnson");

// base_ptr.to_string();
// Получаем указатель на функцию
intptr_t tostring_ptr = base_ptr->_vmt[TO_STRING_SLOT];
// Приводим указатель к нужному типу функции
base_t_to_string_type tostring = (base_t_to_string_type)(tostring_ptr);
// Вызываем
tostring(base_ptr); // {id: 1}

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

То же самое справедливо и для потомка.

Вызов tostring потомком

// child_ptr.to_string();
intptr_t tostring_ptr2 = child_ptr->_vmt[TO_STRING_SLOT];
child_t_to_string_type tostring2 = (child_t_to_string_type)(tostring_ptr2);
tostring2(child_ptr); //{id: 1, text: "John Smith"}

Если же потомок вызовет метод equals, то, так как он его не переопределял, — вызовется equals родителя:

intptr_t equals_addr = child_ptr->_vmt[EQUALS_SLOT];
base_t_equals_type equals = (base_t_equals_type)(equals_addr);

bool equal = equals(base_ptr, child_ptr);
if (equal) {
    printf("Equal\n");
}
else {
    printf("Not equal\n");
}

И мы получим true, так как родительский метод сравнивает по id, и в данном конкретном примере id родителя и потомка намеренно сделаны одинаковыми.

Код примера полностью

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

typedef struct {
    intptr_t *_vmt;
    int32_t id;
} base_t;

void base_tostring(base_t *this) {
    printf("{id: %d}\n", this->id);
}

bool base_equals(base_t *one, base_t *other) {
    return one->id == other->id;
}

typedef struct {
    intptr_t *_vmt;
    int32_t id;
    char *name;
} child_t;

void child_tostring(child_t *this) {
    printf("{id: %d, text: \"%s\"}\n", this->id, this->name);
}

typedef void (*base_t_to_string_type)(base_t *);
typedef void (*child_t_to_string_type)(child_t *);

typedef bool (*base_t_equals_type)(base_t *, base_t *);
typedef bool (*child_t_equals_type)(child_t *, child_t *);

const int32_t TO_STRING_SLOT = 0;
const int32_t EQUALS_SLOT = 1;

intptr_t base_vmt[] = {(intptr_t)base_tostring, (intptr_t)base_equals};
intptr_t child_vmt[] = {(intptr_t)child_tostring, (intptr_t)base_equals};

base_t *new_base(int id) {
    base_t *base_ptr = malloc(sizeof(base_t));
    *base_ptr = (base_t){._vmt = base_vmt, .id = id};

    return base_ptr;
}

child_t *new_child(int id, char *name) {
    child_t *ptr = malloc(sizeof(child_t));
    *ptr = (child_t){._vmt = child_vmt, .id = id, .name = name};

    return ptr;
}

int main() {
    // new base_t(1)
    base_t *base_ptr = new_base(1);
    // new child_t(1, 2)
    child_t *child_ptr = new_child(1, "John Smith");
    child_t *child_ptr2 = new_child(2, "Alex Johnson");

    // base_ptr.to_string();
    // Получаем указатель на функцию
    intptr_t tostring_ptr = base_ptr->_vmt[TO_STRING_SLOT];
    // Приводим указатель к нужному типу функции
    base_t_to_string_type tostring = (base_t_to_string_type)(tostring_ptr);
    // Вызываем
    tostring(base_ptr);
    // child_ptr.to_string();
    intptr_t tostring_ptr2 = child_ptr->_vmt[TO_STRING_SLOT];
    child_t_to_string_type tostring2 = (child_t_to_string_type)(tostring_ptr2);
    tostring2(child_ptr);

    intptr_t equals_addr = child_ptr->_vmt[EQUALS_SLOT];
    base_t_equals_type equals = (base_t_equals_type)(equals_addr);

    bool equal = equals(base_ptr, child_ptr);

    if (equal) {
        printf("Equal\n");
    }
    else {
        printf("Not equal\n");
    }

    free(base_ptr);
    free(child_ptr);
    free(child_ptr2);

    return 0;
}

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

Реализация на "толстых" указателях

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

typedef struct {
    int32_t id;
} base_t;

void base_tostring(base_t *this) {
    printf("{id: %d}\n", this->id);
}

bool base_equals(base_t *one, base_t *other) {
    return one->id == other->id;
}

typedef struct {
    intptr_t *_vmt;
    base_t *ptr;

} base_ptr_t;

typedef struct {
    int32_t id;
    char *name;
} child_t;

void child_tostring(child_t *this) {
    printf("{id: %d, text: \"%s\"}\n", this->id, this->name);
}

typedef struct {
    intptr_t *_vmt;
    child_t *ptr;

} child_ptr_t;

typedef void (*t_base_to_string_type)(base_t *);
typedef void (*child_t_to_string_type)(child_t *);

typedef bool (*t_base_equals_type)(base_t *, base_t *);
typedef bool (*child_t_equals_type)(child_t *, child_t *);

const int32_t TO_STRING_SLOT = 0;
const int32_t EQUALS_SLOT = 1;

intptr_t base_vmt[] = {(intptr_t)base_tostring, (intptr_t)base_equals};
intptr_t child_vmt[] = {(intptr_t)child_tostring, (intptr_t)base_equals};

base_ptr_t new_base(int id) {
    base_t *ptr = malloc(sizeof(base_t));

    *ptr = (base_t){.id = id};

    base_ptr_t fat_ptr = (base_ptr_t){.ptr = ptr, ._vmt = base_vmt};

    return fat_ptr;
}

child_ptr_t new_child(int id, char *name) {
    child_t *ptr = malloc(sizeof(child_t));

    *ptr = (child_t){.id = id, .name = name};

    child_ptr_t fat_ptr = (child_ptr_t){.ptr = ptr, ._vmt = child_vmt};

    return fat_ptr;
}

int main() {
    // new base_t(1)
    base_ptr_t base_ptr = new_base(1);
    // new t_child(1, 2)
    child_ptr_t child_ptr = new_child(1, "John Smith");
    child_ptr_t child_ptr2 = new_child(2, "Alex Johnson");

    // base_ptr.to_string();
    // Получаем указатель на функцию
    intptr_t tostring_ptr = base_ptr._vmt[TO_STRING_SLOT];
    // Приводим указатель к нужному типу функции
    t_base_to_string_type tostring = (t_base_to_string_type)(tostring_ptr);
    // Вызываем
    tostring(base_ptr.ptr);
    // child_ptr.to_string();
    intptr_t tostring_ptr2 = child_ptr._vmt[TO_STRING_SLOT];
    child_t_to_string_type tostring2 = (child_t_to_string_type)(tostring_ptr2);
    tostring2(child_ptr.ptr);

    intptr_t equals_addr = child_ptr._vmt[EQUALS_SLOT];
    t_base_equals_type equals = (t_base_equals_type)(equals_addr);

    bool equal = equals(base_ptr.ptr, child_ptr.ptr);

    if (equal) {
        printf("Equal\n");
    }
    else {
        printf("Not equal\n");
    }

    free(base_ptr.ptr);
    free(child_ptr.ptr);
    free(child_ptr2.ptr);

    return 0;
}

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

Также стоит отметить, что существуют более сложные, чем привязка к типу, техники выполнения диспетчеризации, например multimethods / multiple dispatch.

Девиртуализация

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

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

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

Так или иначе, для виртуальных машин характерно использование различных переходников, реализующих определённую вспомогательную логику. Например: если целевой код ещё не JIT-ован, нужно проверить статистику и сделать JIT-компиляцию метода по необходимости, попутно заменив переходник.

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

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

Синтетика

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

Начнем с простого. Пример из прошлой статьи:

public static Connection Connect(Address address) {
    return new Connection();
}

Метод Connect создаёт новое соединение, используя адрес. В то же время для Address определена функция неявного приведения типа:

public static implicit operator Address(string address) {
    Validator.Validate(address);
    var pair = address.Split(":");
    return new Address(pair[0], Convert.ToInt32(pair[1]));
}

Поэтому в Connect можно передавать строки так же, как и Address:

var connection = Connect(new Address("192.168.1.1", 8453));
var connection2 = Connect("192.168.1.1:8453");

Под капотом — обычный синтаксический сахар:

Connect(new Address("192.168.1.1", 8453));
Connect(Address.op_Implicit("192.168.1.1:8453"));

То же самое с перегрузкой функций, например, операторов:

var pointA = new Point(1.0, 2.0);
var pointB = new Point(4.0, 5.0);
var pointC = pointA + pointB;

Никаких сюрпризов:

Point.op_Addition(new Point(1.0, 2.0), new Point(4.0, 5.0));

Предлагаю перейти к более интересной теме— параметрическому полиморфизму. Мы уже обсуждали в прошлой статье, что идея параметрического полиморфизма — вынести обобщенный тип в отдельный параметр и работать с ним как с шаблоном. Будем разбираться на примерах. Начнём традиционно с Java — напишем какую-нибудь невероятно полезную функцию.

  public static <T> List<T> map(List<T> src, UnaryOperator<T> mapper) {
      var dst = new ArrayList<T>(src.size());
      for (var item : src) {
          dst.add(mapper.apply(item));
      }
      return dst;
  }

В данном примере всё просто: есть функция map, которая принимает список типа T и создаёт новый список такого же типа, но с применением к каждому элементу указанной функции. В Java T реализуется ранее упомянутой упаковкой. Это значит, что в качестве T могут выступать только типы, которые возможно разместить в куче. С этим проблем нет. В Java у каждого скалярного типа есть тип-компаньон, размещаемый в куче. Во время исполнения параметра типа T не существует. Огромная проблема такого подхода — ужасная производительность, особенно, если речь заходит о коллекциях.

Inlining

Посмотрим на такую же функцию на языке Kotlin:

fun <T> map(src: List<T>, mapper: (T) -> T): List<T> {
    val dst = ArrayList<T>(src.size)
    for (item in src) {
        dst.add(mapper(item))
    }
    return dst
}

Всё то же самое. Все проблемы Java в данной части честно унаследованы. Но есть интересная фича — та самая синтетика, оптимизация под названием встраивание (inlining).

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

А если мы заменяем вызов телом, то можем в целевое место подставить любые типы вместо T, обойдя проблему с размерами параметров.

Нет функции — нет параметров — нет проблемы.

В Kotlin можно сохранить информацию о параметрах типов ключевым словом reified, и сделать это можно только для встраиваемых (inline) функций:

inline fun <reified T> map(src: List<T>, mapper: (T) -> T): List<T> {
    println("Преобразование коллекции типа ${typeOf<T>()}")
    val dst = ArrayList<T>(src.size)
    for (item in src) {
        dst.add(mapper(item))
    }
    return dst
}

Вызов данной функции дополнительно выведет на экран: «Преобразование коллекции типа int», что доказывает, что мы сохранили доступ к типу. Но, к сожалению, Kotlin использует коллекции из стандартной библиотеки Java, и, следовательно, встраивай не встраивай — упаковки тут не избежать. Но это интересный пример, чтобы посмотреть, как встраивание в принципе могло бы решить проблему в «параллельной вселенной»:

println("Преобразование коллекции типа Int")
val dst = ArrayListInt(src.size)
for (item in src) {
    dst.add(item + 1)
}
...
println("Преобразование коллекции типа String")
val dst = ArrayListString(src.size)
for (item in src) {
    dst.add(item.toUpperCase())
}

На самом деле в Kotlin можно подставлять конкретные типы вместо T, но только для очень простых случаев.

Monomorphization

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

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

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

Вспомним пример на Java. Я намеренно упрощаю, в стиле псевдокода, как выглядит этот метод «под капотом»:

public static void main(String[] args) {
    List<Integer> result1 = map(List.of(1, 2, 3), n -> n + 1);
    List<String> result2 = map(List.of("One", "Two", "Three"), n -> n.toUpperCase());
    out.printf("1:%s, 2:%s\n", result1, result2);
}

public static List/*<Object>*/ map(List/*<Object>*/ src, UnaryOperator/*<Object>*/ mapper) {
    var dst = new ArrayList/*<Object>*/(src.size());
    for (var item : src) {
        dst.add(mapper.apply(item));
    }
    return dst;
}

Возьмём ту же функцию, но на этот раз напишем её на C#:

public static List<T> Map<T>(List<T> src, Func<T, T> mapper) {
    var dst = new List<T>(src.Count);
    foreach (var item in src) {
        dst.Add(mapper(item));
    }
    return dst;
}

Несмотря на то, что код очень напоминает пример на Java, «под капотом» дела обстоят совершенно иначе. И снова пример в стиле псевдокода:

public static List<int> Map_int(List<int> src, Func<int, int> mapper) {
    var dst = new List<int>(src.Count);
    foreach (var item in src) {
        dst.Add(mapper(item));
    }
    return dst;
}
public static List<System.__Canon> Map_string(List<System.__Canon> src, Func<System.__Canon, System.__Canon> mapper) {
    var dst = new List<System.__Canon>(src.Count);
    foreach (var item in src) {
        dst.Add(mapper(item));
    }
    return dst;

Если в Java для двух разных типов функция map с помощью упаковки стала общей для типов int и String, то в C# для каждого из типов индивидуально создаётся отдельный вариант функции.

Но это ещё не всё. Помимо самой функции, есть ещё параметризированные типы, такие как List<T> из примера. С ними дела обстоят аналогично.
В Java есть всего один тип ArrayList для всех вариантов использования, ограниченный ссылочными типами.
В C# на каждый вариант типа-значения генерируется отдельный специальный тип, а для типов, хранящих ссылки, обычно создается один универсальный экземпляр. Например:

16	List<short>	List_System.Int16
32	List<int>	List_System.Int32
64	List<double>	List_System.Int64
128	List<Point>	List_Monomor.Point
32-64	List<string>	List_System.__Canon
32-64	List<User>	List_System.__Canon

Разумеется, возможность работать напрямую с конкретными типами и прямыми вызовами методов положительно сказывается на производительности.

Это всё красивые слова, а что на практике? Давайте заглянем «под капот». Для начала возьмём дамп работающей программы и посмотрим на таблицу методов класса, где лежит наш метод Map:

MethodDesc Table
           Entry       MethodDesc    JIT Slot             Name
00007FFABA0E0000 00007ffaba034690   NONE 0000000000000000 System.Object.Finalize()
00007FFABA433E70 00007ffaba0346a8 PreJIT 0000000000000001 System.Object.ToString()
00007FFABA0E0E70 00007ffaba0346c0   NONE 0000000000000002 System.Object.Equals(System.Object)
00007FFABA0E0E88 00007ffaba034718   NONE 0000000000000003 System.Object.GetHashCode()
0000000000000000 00007ffaba371518   NONE 0000000000000004 Monomor.Program..ctor()
0000000000000000 00007ffaba3714e8   NONE 0000000000000005 Monomor.Program.Map(System.Collections.Generic.List`1<!!0>,System.Func`2<!!0,!!0>)
00007FFABA3521A8 00007ffaba3714c8    JIT 0000000000000006 Monomor.Program.Main(System.String[])

Занимательно. Метод Monomor.Program.Map всего один, да ещё и не подвергся JIT-компиляции. Для тех, кто не в курсе: виртуальная машина .Net CLR, в отличие, например, от Hotspot JVM, не интерпретирует промежуточный код, а при первом же вызове производит JIT-компиляцию. Здесь же, учитывая, что метод вызывался, мало того, что мономорфизация не производилась, так и вообще даже JIT не пахнет.

На самом деле всё логично. Просто мономорфизация производится во время JIT-компиляции, и в таблице методов мономорфные варианты не присутствуют, остаётся только обобщенный вариант оригинального метода. Для того чтобы найти вызовы мономорфных методов, нужно идти дальше — в JIT-код функции Main, который можно найти в дескрипторе данного метода:

Method Name:          Monomor.Program.Main(System.String[])
Class:                00007ffaba371530
MethodTable:          00007ffaba371530
mdToken:              0000000006000001
Module:               00007ffaba34fb10
IsJitted:             yes
Current CodeAddr:     00007ffaba1759e0
Version History:
  ILCodeVersion:      0000000000000000
  ReJIT ID:           0
  IL Addr:            000002a294022050
     CodeAddr:           00007ffaba1759e0  (MinOptJitted)
     NativeCodeVersion:  0000000000000000

Здесь он находится по адресу 0x00007FFABA1759E0. Немного покопавшись, можно найти те самые вызовы конкретных мономорфных методов:

00007ffa`ba175b65 e8b6c61d00      call    Monomor.Program.Map[[System.Int32, System.Private.CoreLib]](System.Collections.Generic.List`1<Int32>, System.Func`2<Int32,Int32>) (00007ffa`ba352220)
...
00007ffa`ba175c9f e894c51d00      call    Monomor.Program.Map[[System.__Canon, System.Private.CoreLib]](System.Collections.Generic.List`1<System.__Canon>, System.Func`2<System.__Canon,System.__Canon>) (00007ffa`ba352238)

Обратите внимание: две разные реализации — одна из которых System.Int32, а другая — System.__Canon. Поскольку строка (string) — это ссылочный тип, нет смысла для всех возможных передаваемых в метод ссылочных типов делать свою реализацию, так как размеры всех ссылок одинаковые.

У такого способа есть и свои ограничения. Классический пример — это гетерогенные (т. е. разнотиповые) коллекции данных. Допустим, у нас есть интерфейс IA и две его реализации — структуры B и C. Мы хотим такой список, чтобы туда можно было положить как B, так и C. Добиться этого можно с помощью упаковки:

List<IA> list = [new B(), new C()];

Или даже использовать резервирование — выделять под каждый элемент список памяти с запасом, равным максимальному возможному размеру:

enum AType : byte {
    B,
    C
}
[StructLayout(LayoutKind.Explicit)]
struct AUnion {
    [FieldOffset(0)] public B B;
    [FieldOffset(0)] public C C;
    
}
struct APack {
    public AUnion union;
    public AType type;

    public APack(AUnion union, AType type) {
        this.union = union;
        this.type = type;
    }
}

List<APack> list = [
    new(new AUnion { B = new B(1) }, ATypes.B),
    new(new AUnion { C = new C(10, true) }, ATypes.C)
];

Но вот конкретно мономорфизацией решить проблему не удастся.

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

Заключение

Мы рассмотрели наиболее популярные методы реализации различных видов полиморфизма. Каждый из методов имеет свои плюсы и минусы.

Резервирование удобно для работы с разнородными данными, но может страдать от излишнего потребления памяти, а также в плане производительности, если нужно будет копировать данные приличных размеров.

Упаковка — довольно простой и гибкий метод, часто выручающий там, где другие невозможны или неэффективны, но уступающий по производительности остальным.

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

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

Спасибо за внимание

Hubs: