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

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

О задаче

Некоторое время назад появилась необходимость реализовать небольшой модуль, который в зависимости от пользовательской (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. Код подготовлен так, чтобы избежать излишнего встраивания.
______________________________

Дополнение

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

1) Отличия от std::function:

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

Второй важный момент — данная реализация НЕ работает с динамической памятью. Это дает потенциальное преимущество с точки зрения производительности. При этом если на практике возникнет острая необходимость все-же применять динамическую память — потребуется изменить всего пару строк внутри каждой функции с добавлением оператора new. Однако в таком случае обязательно понадобиться контролировать очистку памяти (что сейчас происходит автоматически).
При таком подходе всё-еще возможно встраивание выполняемого кода (аналогично тому, что происходит в std::function, и при этом остается рабочим механизм виртуальных вызовов.

2) Неправильная работа Wrap при многократном вызове для однотипных объектов с разным состоянием

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

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

template<class Func>
Wrapping<Func>* Wrap( Func f )
{
    static int recallFlag{};
    if( recallFlag ) throw "Second Wrap of the same type!\n";
    recallFlag++;

    static Wrapping<Func> W( f );
    return &W;
}

(Прошу прощения за нестандартный объект для throw)

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

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

template<int i = 0, class Func>
Wrapping<Func>* Wrap( Func f ) {...}

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

Первое решение весьма надежно и просто. Однако следует обратить внимание, что при использовании Wrap в разных файлах макрос __LINE__ может давать одинаковый результат, а макрос __COUNTER__ не является стандартным, хотя реализован на большинстве компиляторов. Так-же могут возникнуть конфликты, если другие модули программы каким-то образом используют этот макрос и требуют единоличных прав на него. В общем же решение выглядит примерно так:

#define OWrap( ... ) \
Wrap<__COUNTER__>( __VA_ARGS__ )

В дополнение можно определить макросы для простого вызова Wrap под аргументы-функции:

#define FWrap( ... ) \
Wrap<declarate( __VA_ARGS__ ), __VA_ARGS__>()

Второй вариант можно реализовать воспользовавшись например решениями отсюда и вот отсюда. Дальше можно точно так-же подставить результат внутри макроса.

Последний, но как по моему — самый интересный вариант вдохновлен вот этой статьей. На самом деле это достаточно тонкая реализация, хотя полностью в рамках стандарта C++11. Результат дает возможность напрямую подставить счетчик в шаблон без применения дополнительных макросов, например вот так:

template<int i = next(), class Func>
Wrapping<Func>* Wrap( Func f ) {...}

где next() — реализация шаблонного счетчика.

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