- PVSM.RU - https://www.pvsm.ru -
Сегодня речь пойдет про одну интересную идиому, которую ввел Шон Парент (Adobe) — известный деятель в C++-сообществе. Он часто выступает с докладами и публикует цикл статей Better Code. Одна из его идей, которую используют в Photoshop — это Concept-Based Polymorphism. Это когда мы реализуем полиморфизм не через явное наследование, а с помощью техники, включающей обобщенное программирование, и по итогам получаем некоторые дополнительные преимущества.
Статья устроена следующим образом:
Картинка, иллюстрирующая тезис «Наследование — это зло». Источник [1]
В С++ динамический полиморфизм реализуется с помощью виртуальных функций и наследования, а статический полиморфизм с помощью шаблонов. Здесь мы совместим эти два подхода и возьмем лучшее из них.
Явное использование наследования зачастую приводит к избыточной связности кода и нарушению принципа разделения интерфейса (ISP [2]). Как реализовать динамический полиморфизм без этих недостатков?
Шон Парент предложил идиому под названием Concept-Based Polymorphism, где наследование неявно, и оно скрыто от пользователя. Подробнее об этом можно узнать из его доклада Inheritance Is The Base Class Of Evil [3] — где он показывает всю идею на примере Photoshop и истории действий — вы узнаете, как работает в действительности «историческая кисть».
Хотелось бы показать преимущества этой идиомы на примере LLVM. Кто не знает, LLVM — это инфраструктура для разработки компиляторов. Ниже представлена очень высокоуровневая архитектура LLVM, в которой освещены только те сущности, которые используются далее в статье. За более подробной информацией можно обратиться к официальной документации [4].
Так выглядит архитектура LLVM, и в принципе, любого современного компилятора
Основные части такие:
Компилятор представляет программу в виде нескольких основных сущностей. Это модуль (условно .cpp-файл), функция, базовый блок, который содержит в себе набор инструкций.
Сейчас в LLVM есть две версии PassManager:
Идея статьи в том, чтобы продемонстрировать концепт на реальном продуктовом коде, который реализован двумя разными способами, и показать плюсы последнего подхода.
Вначале, как всё устроено классически, в LegacyPassManager. Допустим, у нас есть некий класс PassManager и есть класс Pass — один проход. Имеем такую иерархию: ModulePass, от которого идет наследование нашего класса, к примеру Constant Propagation. Есть метод runOnModule, здесь он виртуальный. Итак, мы имеем обычный runtime-полиморфизм:
/// ModulePass class - This class is used to implement unstructured
/// interprocedural optimizations and analyses. ModulePasses may do anything
/// they want to the program.
///
class ModulePass : public Pass {
...
/// runOnModule - Virtual method overriden by subclasses to process the module
/// being operated on.
virtual bool runOnModule(Module &M) = 0;
};
...
/// IPCP - The interprocedural constant propagation pass
///
struct IPCP : public ModulePass {
...
bool runOnModule(Module &M) override;
};
Давайте посмотрим на код, в чем здесь проблема? Мы видим, что в этой иерархии методы запуска прохода различны в зависимости от того, над чем они должны выполняться (над функцией — runOnFunction, модулем — runOnModule, циклом — runOnLoop и тд). В свою очередь, это делает невозможным обрабатывать коллекцию проходов, которые работают с разными IR сущностями, единым способом (собственно применять полиморфизм). Казалось бы, очевидно, как сделать правильно: нужен виртуальный метод run, который будет переопределяться в наследниках. Но тут же возникает проблема: у методов run в классах-наследниках будет разная сигнатура, поскольку передается параметр всегда своего типа — функция, модуль и так далее. Значит, придется делать фиктивный базовый класс для Module, Function и т.д., передавать в run указатель на этот класс, а внутри метода делать down-cast, в зависимости от того, что за объект находится по данному указателю. И начинается что-то странное: при появлении новой нижестоящей сущности мы вынуждены теперь переписывать каждый раз вышестоящий код, что противоречит всем принципам проектирования.
Можно вручную написать класс-адаптер для каждого случая. Но это долго и неинтересно, да и вообще странная идея писать классы-обертки для удобной работы всего лишь обслуживающей компоненты. Лучше было бы генерить этот код автоматически при помощи шаблонов. Вот именно этим и предлагается заняться в обсуждаемом подходе. Плюс, как вы увидите далее, мы получим еще несколько полезных следствий.
В новом PassManager происходит следующее. Понятие полиморфного объекта обобщаем следующим образом. Говорим, что если объект реализует какой-то метод, то мы вводим набор методов, которые мы хотим, чтобы были полиморфные, и говорим, что все классы, которые реализуют данный метод, являются полиморфными, то есть мы можем их использовать во взаимозаменяемых контекстах в этом PassManager.
Рассмотрим класс PassManager в LLVM. Здесь приведена его упрощенная версия, а полную можно посмотреть в llvm/include/llvm/IR/PassManager.h. Шаблонный параметр IR специализируется непосредственно сущностью, над которой мы выполняем проход (функция run). Это может быть модуль, функция либо цикл. Смотрим код, дальше будут пояснения:
template <typename IR, typename... ArgTs> class PassManager {
public:
void run(IR& ir, ArgTs... args) {
for (auto& Pass : Passes) {
Pass->run(graph, args...);
}
}
template <typename PassT>
void addPass(PassT Pass) {
Passes.emplace_back(new detail::PassModel<IR, PassT, ArgTs...>(std::move(Pass)));
}
private:
std::vector<std::unique_ptr<detail::PassConcept<IR, ArgTs...>>> Passes;
};
Давайте посмотрим на следующие основные сущности:
Итак, что это должен быть за тип? Что хранится в векторе Passes?
Для начала разберемся, что такое PassModel и PassConcept. Это вспомогательные классы, внутренние для PassManager. Они оба находятся в пространстве имен detail. Вначале посмотрим, как выглядит класс PassConcept. В нем находится опять тот же самый метод run, здесь это чисто виртуальный метод.
namespace detail {
template <typename IR, typename... ArgTs> class PassConcept {
public:
virtual ~PassConcept() = default;
virtual void run(IR& ir, ArgTs... args) = 0;
};
Второй класс, PassModel, тоже шаблонный. Он унаследован от PassConcept.
template <typename IR, typename PassT, typename... ArgTs> class PassModel final : public PassConcept<IR, ArgTs...> {
public:
explicit PassModel(PassT Pass) : pass_(std::move(pass)) {}
void run(IR& ir, ArgTs... args) final {
pass_.run(ir, args...);
}
private:
PassT pass_;
};
} // end namespace detail
Что в нем содержится:
Вспоминаем теперь, с чего начинали. В свою очередь, PassManager хранит в себе все эти проходы. В векторе Passes из элементов типа PassConcept.
Итак, общая картина. Создается PassManager. С помощью AddPass в нем регистрируются те проходы, которые мы хотим сделать над модулем, функцией циклом и т.д. Например, inline, constant propagation, loop unrolling, etc. Сами они ни от кого не наследуются, они должны только иметь метод run. И как раз вся эта концепция это обеспечивает. Каким образом?
Допустим, у нас есть Inline-оптимизация. Мы в addPass передаем объект типа Inline. Соответственно в Passes, в вектор, мы кладем этот Inline, уже в виде PassConcept. Как мы можем это сделать? Inline же не наследуется от класса PassConcept. Как же мы положим элемент в вектор? Приведение к базовому типу (upcasting) мы не можем здесь сделать, потому что нет никакого наследования И вот здесь как раз делается такой трюк. У нас есть вот этот вспомогательный класс PassConcept, который определяет интерфейс. Он говорит, что все его наследники должны реализовать метод run. У нас есть PassModel, который в свою очередь шаблонный. И вот, когда кладем Inline, происходит инстанциация этого PassModel с этим типом Inline, внутри этого класса композируется этот объект. Сам PassModel переопределяет run, который для себя вызывает уже run для вот этого прохода, то есть run из класса Inline. Все это в compile-time разруливается: если у нас Inline не определит метод run, у нас будет ошибка времени компиляции.
Таким образом достигается этот полиморфизм без наследования. Может возникнуть вопрос: а как это нет наследования, ведь вот оно же, PassModel унаследовано от PassConcept? Ответ: тут есть наследование, но оно внутреннее, оно не торчит наружу, пользователь не знает о нем ничего.
Мы говорим на концептуальном уровне. Вот у нас есть пользователь, он хочет переопределить некий метод. При этом он не хочет наследоваться, чтобы лишние зависимости к себе не тянуть. Как это сделать? Мы внутри себя, через PassConcept, PassModel-ом, делаем runtime-полиморфизм, через наследование, но пользователь об этом не знает: это все внутренности этих двух классов, они там в своем namespace определены.
Еще раз, как это достигается? У меня есть класс, назовем его, пусть это будет Inline, в терминах компилятора. Мы добавляем Inline в вектор, соответственно создаем объект PassModel. Он имеет конструктор, который принимает в себя объект вот этого шаблонного параметра. И вот, когда мы в PassManager вызываем метод run, он бежит по всем проходам, в данном случае у нас только один проход, он имеет тип Inline. Он вызывает метод run у PassConcept’а. Тот самый метод run, который внутри PassModel лежит, который инстанциирован типом Inline. И уже этот метод вызывает метод run у зарегистрированного прохода, в данном случае Inline, и в итоге у нас вызывается run у Inline’а.
Вот так мы сделали разное поведение без явного использования наследования. У нас теперь нет явной зависимости, которая была раньше, в LegacyPassManager.
Какая необычная рекуррентная штука получается. Мы можем использовать полиморфизм для любого объекта, который переопределяет метод run. Поскольку метод run переопределяет сам PassManager, он сам может зарегистрировать себя, то есть самого себя вложить в вектор проходов Passes и вызвать себя еще раз.
Получается, мы можем всё смешать. В старом PassManager, который Legacy, есть четкое разделение. Там есть модульная оптимизация, которая на модуль делается; есть оптимизация, которая происходит на функцию. А здесь это всё происходит плавно. Мы делаем PassManager, инстанциируем его типом «Модуль», кладем в него Inline, еще что-то, еще какие-нибудь помодульные оптимизации. Потом второй PassManager, инстанциируем его типом «Функция», кладем оптимизации на функцию. И потом в PassManager, который инстанциирован модулем, можно положить другой PassManager, который инстанциирован функцией, через этот вектор Passes.
PassManager<Module> MPM;
// ... register passes on module
MPM.addPass(GlobalDCEPass())
MPM.addPass(PGOInstrumentationGen());
//... register passes on function
PassManager<Function> FPM;
FPM.addPass(CallSiteSplittingPass());
//... register all registered passes on function in module pass manager MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
Успеваете следить? У нас есть два PassManager’а. Один с типом IR Module, другой с типом IR Function. Допустим, в тот, который с модулем, мы уже положили какое-то количество проходов. Теперь мы хотим перемешать их с проходами, которые выполняются на функцию. Что мы делаем? Мы вызываем addPass и в качестве Pass’а передаем PassManager, который инстанциирован IR-типом «Функция» (в реальном коде там кладется не сам PassManager, а специальный класс, который его оборачивает, но на концептуальном уровне это не имеет значения).
Таким образом, мы можем перемешивать разные уровни оптимизации — благодаря вложенности PassManager'ов, попеременно выполнять проходы на модуль, на функцию, цикл и т.д. В Legacy PassManager с этим сложнее, там отдельный класс для модулей, который имеет виртуальную функцию runOnModule, отдельный класс для функций c виртуальным методом runOnFunction и т.д. Оба эти класса наследуются от общего предка Pass, но между собой они независимы и имеют различный интерфейс, что делает использование LegacyPassManager неудобным для вызова проходов на разных IR сущностях (модуль, функция, цикл)
Материалы для дополнительного чтения:
Авторы:
Роман Русяев,
Expert Engineer
AI Compiler Team
Samsung R&D Institute, Russia
Скоро Роман выступит на конференции С++ Russia 2020 Moscow вместе с Антоном Полухиным: там они поговорят о настоящем и будущем copy elision: ссылка на доклад [9]
Татьяна Волкова,
Lead Specialist
Business Development Team
Samsung R&D Institute, Russia
Автор: Татьяна Волкова
Источник [10]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-3/353816
Ссылки в тексте:
[1] Источник: https://codeburst.io/inheritance-is-evil-stop-using-it-6c4f1caf5117
[2] ISP: https://en.wikipedia.org/wiki/Interface_segregation_principle
[3] Inheritance Is The Base Class Of Evil: https://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil
[4] документации: http://llvm.org/docs
[5] LLVM for Grad Students: https://www.cs.cornell.edu/~asampson/blog/llvm.html
[6] Презентация: https://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf
[7] Презентация: http://llvm.org/devmtg/2014-10/Slides/Carruth-TheLLVMPassManagerPart2.pdf
[8] Тред: http://lists.llvm.org/pipermail/llvm-dev/2018-April/122613.html
[9] ссылка на доклад: https://cppconf-moscow.ru/2020/msk/talks/7oisht3acspmwd6ogp97u/?utm_source=habr&utm_medium=494986
[10] Источник: https://habr.com/ru/post/505850/?utm_source=habrahabr&utm_medium=rss&utm_campaign=505850
Нажмите здесь для печати.