Встраивание функциональных объектов, функций и лямбд через шаблоны и унификация при помощи virtual на C++

в 21:31, , рубрики: c++, c++11, functor, inline, lambda

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

О задаче

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

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

Первые шаги

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

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

Простой пример такого класса:

struct MyObj
{
    using FType = int( *)(int, int);

    virtual int operator() ( int a, int b ) = 0;
    virtual ~MyObj() = default;
};

Здесь основным является виртуальный оператор "()", Виртуальный деструктор нужен из очевидных соображений, а FType всего-лишь определяет семантику основного метода в плане типов аргументов и возврата.

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

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

Встраивание

Собственно важнейшим шагом к оптимальной работе программы является написание встраиваемого (inline) кода. По сути для этого нужно, чтобы выполняемая последовательность инструкций минимально зависела от runtime данных. В таком случае компилятор сможет встраивать код функций на место их вызова вместо перехода (вызова) по адресу и/или выкидывать ненужные куски кода. Эти же критерии позволяют собрать машинный код избегая лонг джампов и частого изменения процессорного кеша, но это уже совсем другая история.

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

Наследование

Первым делом стоит разобраться непосредственно с наследованием абстрактного класса. Простейший способ это «ручная» перегрузка оператора при наследовании. К примеру:

struct : public MyObj {
    int operator()( int a, int b ) override { return a + b; };
}addObj;    // manually inherited structure

MyObj* po = &addObj;

int res = (*po)( a, b );

В этом случае получается так, что оптимизированный вызов виртуального метода перенесет сразу на складывание двух чисел. MSVS при оптимизации О2 выдает примерно такой машинный код для вызова* (подготовка регистров, укладка аргументов):

push        dword ptr [b]  
mov         eax,dword ptr [esi]  
mov         ecx,esi  
push        dword ptr [a]  
call        dword ptr [eax]  

и такой код для собственно перегруженного метода:

push        ebp  
mov         ebp,esp  
mov         eax,dword ptr [a]  
add         eax,dword ptr [b]  
pop         ebp  
ret         8  

*Первая часть абсолютно одинакова для всех случаев, по скольку зависит только от семантики самого вызова, потому этот код дальше будет упускаться. В этой статье всегда используется вариант res = (*po)(a, b);.

В некоторых случаях оптимизация бывает еще лучше, например g++ может сжать складывание целых чисел до 2 инструкций: lea, ret. В данной статье для краткости я ограничусь примерами, полученными на майкрософтовском компиляторе, при этом замечу, что код также проверялся на g++ под linux.

Функторы

Логичным продолжением является вопрос «а что если надо выполнять сложный код, реализованный в сторонних функциях?». Естественно этот код надо выполнять внутри перегруженного метода у наследника MyObj, но если вручную создавать для каждого случая свой (пусть даже анонимный) класс, инициализировать его объект и передавать его адрес, то про понятность и масштабируемость можно даже не вспоминать.

К счастью в С++ для этого есть великолепный механизм шаблонов, который подразумевает именно compile-time разрешение кода и, соответственно, встраивание. Таким образом можно оформить простой шаблон, который будет принимать параметром какой-либо функтор, создавать анонимный класс-наследник MyObj и внутри перегруженного метода вызывать полученный параметр.

Но (конечно есть «но»), как же лямбды и другие динамические объекты? Стоит заметить что лямбды в C++ ввиду их реализации и поведения надо воспринимать именно как объекты, а не как функции. К большому сожалению ламбда-выражения в C++ не удовлетворяют требованиям параметра шаблона. Эту проблему рвутся исправить в 17-ом стандарте, а даже и без него не всё так плохо.

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

В результате можно написать небольшую пару: класс-обёртка и функция-заворачиватель, которые будут давать нужный нам результат:

template<class Func>
class Wrapping : public MyObj
{
    Func _f;
public:

    Wrapping( Func f ) : _f( f ) {};
    int operator()( int a, int b ) override { return _f( a, b ); }
};

template<class Func>
Wrapping<Func>* Wrap( Func f )
{
    static Wrapping<Func> W( f );
    return &W;
}

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

Примером вызова может быть:

po = Wrap( []( int a, int b ) {return a + b; } );

Несмотря на сложный вид — набор инструкций у перегруженного оператора «()» будет очень простой, собственно идентичный полученному при ручном наследовании и встраивании:

push        ebp  
mov         ebp,esp  
mov         eax,dword ptr [a]  
add         eax,dword ptr [b]  
pop         ebp  
ret         8  

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

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

struct AddStruct {
    int operator()( int a, int b ) { return a + b; }
};
...
op = Wrap( AddStruct() );

Будет иметь следующий машинный код перегруженного оператора:

push        ebp  
mov         ebp,esp  
mov         eax,dword ptr [a]  
add         eax,dword ptr [b]  
pop         ebp  
ret         8

Т.е. такой-же как и при ручном встраивании. Мне удавалось получить подобный машинный код даже для объекта, созданного через new. Но этот пример оставим в стороне.

Функции

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

int sub( int a, int b ) { return a + b; };
...
po = Wrap( sub );

Но в машинном коде перегруженного метода будет находиться еще один вызов соответственно с переходом:

push        ebp  
mov         ebp,esp  
push        dword ptr [b]  
mov         eax,dword ptr [ecx+4]  
push        dword ptr [a]  
call        eax  
add         esp,8  
pop         ebp  
ret         8  

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

Функции с идентичной семантикой

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

template<class Func, Func f>
struct FWrapping : public MyObj
{
    int operator ()( int a, int b ) override { return f( a, b ); }
};

template<MyObj::FType f>
FWrapping<MyObj::FType, f>* Wrap()
{
    static FWrapping<MyObj::FType, f> W;
    return &W;
}

Оборачивая перегруженную Wrap для функций вида:


int add( int a, int b ) { return a + b; }
...
po = Wrap<add>();

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

push        ebp  
mov         ebp,esp  
mov         eax,dword ptr [a]  
add         eax,dword ptr [b]  
pop         ebp  
ret         8  

Функции с отличной семантикой

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

template<class Func, Func f>
FWrapping<Func, f>* Wrap()
{
    static FWrapping<Func, f> W;
    return &W;
}

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

po = Wrap<decltype( add )*, add>();

Важно заметить необходимость ставить «*» после decltype, иначе среда разработки может выдавать сообщение об ошибке про отсутствие реализации Wrap, удовлетворяющей данным аргументам. Несмотря на это скорее всего проект нормально скомпилируется. Данное несоответствие вызвано правилами определения типов при передаче в шаблон и, собственно, принципом работы decltype. Чтобы избежать сообщения об ошибке можно воспользоваться такой конструкцией, как std::decay для гарантированно корректной подстановки типа, которую удобно завернуть в простой макрос:

#define declarate( X ) std::decay< decltype( X ) >::type
...
po = Wrap<declarate( add ), add>();

Либо же просто отслеживать соответствие вручную, если вы не хотите плодить сущности.

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

float fadd( float a, float b ) { return a + b; }
...
op = Wrap<declarate(fadd), fadd>();

Из дезассемблера выйдет примерно это:

push        ebp  
mov         ebp,esp  
movd        xmm1,dword ptr [a]  
movd        xmm0,dword ptr [b]  
cvtdq2ps    xmm1,xmm1  
cvtdq2ps    xmm0,xmm0  
addss       xmm1,xmm0  
cvttss2si   eax,xmm1  
pop         ebp  
ret         8

Функции вместе

Получив дополнительные перегрузки функции Wrap для встраивания собственно других функций можно во избежание повторения кода и для приближения к Дзен переопределить один из вариантов через вызов другого:

template<class Func, Func f>
FWrapping<Func, f>* Wrap()
{
    static FWrapping<Func, f> W;
    return &W;
}
template<MyObj::FType f>
FWrapping<MyObj::FType, f>* Wrap()
{
    return Wrap<MyObj::FType, f>();
}

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

Всё вместе

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

*достаточно близкий для данного примера означает совпадение по количеству аргументов и при условии совпадения либо возможности неявного преобразования типов.

struct MyObj
{
    using FType = int( *)(int, int);

    virtual int operator() ( int a, int b ) = 0;
    virtual ~MyObj() = default;
};

template<class Func>
class Wrapping : public MyObj
{
    Func _f;
public:

    Wrapping( Func f ) : _f( f ) {};
    int operator()( int a, int b ) override { return _f( a, b ); }
};
template<class Func, Func f>
struct FWrapping : public MyObj
{
    int operator ()( int a, int b ) override { return f( a, b ); }
};

template<class Func>
Wrapping<Func>* Wrap( Func f )
{
    static Wrapping<Func> W( f );
    return &W;
}
template<class Func, Func f>
FWrapping<Func, f>* Wrap()
{
    static FWrapping<Func, f> W;
    return &W;
}
template<MyObj::FType f>
FWrapping<MyObj::FType, f>* Wrap()
{
    return Wrap<MyObj::FType, f>();
}

#define declarate( X ) std::decay< decltype( X ) >::type

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

int volume( const double& a, const double& b, const double& c ) { return a*b*c; };
...
po = Wrap( []( int a, int b )->int { return volume( a, b, 10 ); } );

Примеры кода находятся здесь. Для сборки нужно использовать С++11. Для того чтобы разглядеть разницу во встраивании — оптимизацию О2. Код подготовлен так, чтобы избежать излишнего встраивания.

Автор: kgill-leebr

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js