Анонимные функции, type erasure, std::function

• Статья про девиртуализацию
• Запись лекции №1
• Запись лекции №2
• Запись лекции №3
• Код std::function
• Презентация про type erasure

Мотивирующий пример и оптимизации

Какой вариант быстрее?

bool int_less(int a, int b) {
    return a < b;
}

template <typename T>
struct less {
    bool operator()(T const& a, T const& b) const {
        return a < b;
    }
};
// можно сделать класс со static-функцией, но это не даёт выигрыша
// так как ABI устроен так, что пустые структуры можно не копировать

int foo (vector& v) {
    std::sort(v.begin(), v.end(), less<int>());
    std::sort(v.begin(), v.end(), &int_less);
}

Оказывается, что первый вариант работает процентов на 30 быстрее на случайных массивах и в 3 раза на отсортированных.

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

Если скомпилировать с -flto, компилятор может соптимизировать, но только в том случае, если в sort передаётся указатель только на одну функцию. При этом с -O3 может произойти так, что даже если передавать указатели на разные функции, время работы будет одинаковым.

-flto уже упоминалось в лекции про компиляцию программ, это ключик, который включает link time optimization, смысл которой понятен из названия.

-O3 добавляет некоторые оптимизации, например, -fipa-cp-clone, которая создаёт копию функции и оптимизирует её, если в неё передаётся константа. Почему эти оптимизации не включены по умолчанию? Из-за них может ухудшаться производительность. Например, эта оптимизация может создать много копий функции, что заметно увеличит размер бинарного файла. Почему это плохо? Помимо кэша для данных, у процессора есть кэш инструкций, в таком случае он будет забиваться копиями функции и портить общую производительность. Это можно не заметить на микробенчмарках, но при сборке всего проекта будет заметно равномерное ухудшение, причина которого неочевидна.

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

Помимо этого, девиртуализация может быть "спекулятивной" (в GCC она называется -fdevirtualize-speculatively), эта оптимизация генерирует примерно такой код:

bool int_less(int a, int b) {
    return a < b;
}

void sort(int* a, bool(*comp)(int, int)) {
    // ...
    if (comp == &int_less) {
        int_less(a[4], a[5]);
    } else {
        comp(a[4], a[5]);
    }
}

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

Такая оптимизация даёт выигрыш, если использовать её с profile-guided optimization - техникой оптимизации, которая заключается в запуске программы на каких-то репрезентативных данных и последующей её оптимизации, в зависимости от профайлинга. Например, если чаще всего компаратор это int_less, то применение спекулятивной девиртуализации сделает if как в коде выше.

Анонимные функции

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

int main() {
    std::vector<int> v;
    std::sort(v.begin(), v.end(), [](int a, int b) -> bool {
        return a % 10 < b % 10;
    });
}

Такая конструкция называется лямбдой. На самом деле, это генерит почти такой же код, как определение структуры и передача её инстанса по значению. Компилятор генерит структуру с operator(), тип его возвращаемого значения выводится из return'ов (как auto), но его можно указать и явно (как в примере выше).

Синтаксис у лямбд следующий: в круглых скобках - аргументы, которые принимает функция, в фигурных - тело функции, а квадратные скобки нужны для захвата переменных из контекста (такой объект называется closure).

struct mod_comparer {
    mod_comparer(int mod) : mod(mod) {}
    
    bool operator()(int a, int b) const {
        return a % mod < b % mod;
    }
  private:
    int mod;
}

void foo(int mod) {
    std::vector<int> v;
    std::sort(v.begin(), v.end(), mod_comparer(mod));
    std::sort(v.begin(), v.end(), [mod](int a, int b) -> bool {
        return a % mod < b % mod;
    });
}

Захват в примере выше происходит по значению, захватывать можно и по ссылке. Кроме того, можно захватить весь контекст по значению, а некоторые переменные по ссылке (и наоборот).

int main() {
    int x, y, z;
    [x, &y, z](){}; // y - по ссылке, остальные по значению
    [=](){}; // всё по значению
    [=, &y](){}; // всё по значению, y - по ссылке
    [&](){}; // всё по ссылке
    [&, x](){}; // всё по ссылке, x - по значению
}

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

Если в теле лямбды, которая объявлена внутри класса, используется this, то это this, который соответствует структуре, а не внутреннему представлению лямбды. Это происходит из-за того, что все имена резолвятся в коде ещё до создания структуры.

В общем случае, синтаксис лямбды выглядит так:

[capture-list] (params) specifiers exception-specification -> return-type { body }

• capture-list - список захвата, о котором рассказано выше.

  Кроме упомянутых возможностей захвата, в C++14 появилась возможность захватывать новую переменную с заданным значением ([x = 2 + 3] или move-only типы [x = std::move(x)]), а так же захватывать ссылки по новому имени ([&x = a]), где a может быть любой ссылкой, например, элементом массива. В частности, это позволяет захватывать объекты по константной ссылке &cr = std::as_const(x).

  По умолчанию переменные, захваченные по значению, нельзя изменять в теле лямбды (см. specifiers).

• params - список параметров, при этом параметры по умолчанию появились только в C++14

• specifiers - спецификаторы. Например, mutable позволяет изменять переменные, захваченные по значению, и вызывать у них не-const методы. При этом значение переменной снаружи не изменится, так как при захвате по значению они копируются.

• exception-specification - спецификаторы throw, noexcept (как у обычных функций)

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

Смотреть на то, во что разворачиваются лямбды, можно на C++ insights.

Свойства лямбд

Так как лямбды - это некоторые классы (типы), то имеет смысл рассуждать про свойства этих классов.

• Есть operator().

• Есть конструктор копирования и перемещения.

• Нет присваивания.

• До C++20 запрещён дефолтный конструктор, в C++20 разрёшен, если лямбда ничего не захватывает.

• Незахватывающие лямбды имеют оператор конверсии в указатель на функцию:

  int main {
      auto b = [](){
          // ...
      };
      void (*a)();
      a = b;
  }
  

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

  auto foo() {
      std::vector<int> v;
      return [&v] {
          // ...
      };
  } // v уничтожится при выходе из функции, обращение внутри лямбды - UB
  

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

Шаблонные лямбды

Может ли лямбда быть шаблонной?

Чтобы говорить об этом, нужно понимать, шаблон у чего имеется в виду - у класса или у operator().

template <typename T>
struct less {
  bool operator()(T const& a, T const& b) const {
      return a < b;
  }  
};

struct polymorphic_less {
  template <typename T>
  bool operator()(T const& a, T const& b) const {
      return a < b;
  }  
};

void foo() {
    std::vector<int> v;
    std::sort(v.begin(), v.end(), less<int>());
    std::sort(v.begin(), v.end(), polymorphic_less());
}

Делать лямбду шаблонной, как шаблонный класс, смысла не имеет, так как мы её создаём один раз.

В C++20 можно писать лямбдам шаблонные параметры:

int main() {
    auto less = []<typename T>(T a, T b) { return a < b; };
    bool val = less(42, 43);
}

До C++20 существовал auto для типов аргументов (не только для лямбд, но и для обычных функций). По сути, это означало, что для аргумента неявно создаётся шаблонный параметр:

void foo(auto a) {}

int main() {
    foo(1.0);
    foo<int>(42); // можно даже явно передать тип
}

Такой синтаксис имеет ограничение - нельзя иметь параметры только одного типа, так как на каждый создаётся свой шаблонный параметр:

void foo(auto a, auto b) {};

template <typename A, typename B>
void foo(A a, B b) {}; // эквивалентно

std::function

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

void (bool flag) {
    ??? func;
    if (flag) {
        func = [](){};
    } else {
        func = [](){};
    }
}

Так как func присваиваются объекты разных типов, в зависимости от flag, то не понятно, каким типом должен бытьfunc.

Для такого в стандартной библиотеке есть std::function. Единственное ограничение - ему нужна сигнатура функции.

void (bool flag) {
    std::function<void (int, int)> func; // void (int, int) - это тип функции.
    if (flag) {
        func = [](int a, int b){};
    } else {
        func = [](int a, int b){};
    }
}

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

Возможная реализация

Что нужно сохранять?

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

Пример для двух аргументов и без возвращаемого значения:

#include <functional>

template <typename F>
void delete_func(void* obj) {
    delete static_cast<F*>(obj);
}

template <typename F>
void invoke_func(void* obj, int a, int b) {
    return static_cast<F*>(obj)(a, b);
}

template <typename T>
struct function {
    typedef void(*deleter_t)(void*);
    typedef void(*invoker_t)(void*, int, int);
    
    function(); 
    template <typename F>
    function (F f) 
        : obj(new F(f)),
    	  deleter(delete_func<F>),
    	  invoker(invoke_func<F>)
	{}
    
    void operator()(int a, int b) {
        return invoker(obj a, b);
    }
    
    ~function() {
        deleter(obj);
    }
  private:
    void* obj;
    deleter_t deleter;
    invoker_t invoker;
}

Чтобы сделать это для общего случая, достаточно просто добавить variadic шаблонные параметры для аргументов и шаблонный параметр для возвращаемого значения:

template <typename Sig>
struct function;

template <typename Ret, typename... Args.
struct function<Ret (Args...)> {
    // специализация для того, чтобы развернуть сигнатуру
    // ...
}

Вспомогательные функции

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

struct mytype {
    void myfunc(int a);
}

void foo() {
    void (mytype::* f)(int) = &mytype::myfunc;
    mytype* p;
    (p->*f)(42);
}

В C++11 появилась вспомогательная функция std::mem_fn:

void foo() {
    void (mytype::* f)(int) = &mytype::myfunc;
    mytype* p;
    auto g = std::mem_fn(f);
    g(p, 42);
}

Можно пользоваться для этого лямбдами:

void foo() {
    void (mytype::* f)(int) = &mytype::myfunc;
    mytype* p;
    std::function<void (mytype*, int)> x = std::mem_fn(f);
    std::function<void (mytype*, int)> y = [](mytype* p, int a){
        p->myfunc(a);
    };
}

Также есть std::bind, который позволяет "запомнить" аргументы для функции и частично реализован примерно так:

template <typename F, typename... Args>
auto bind(F f, Args... args) {
    return [f, args...]() {
        return f(args...);
    }
}

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

Рекурсивный вызов лямбд

std::function позволяет решить проблему рекурсивного вызова лямбд.

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

int main() {
    auto fib = [&fib] (int n) {
        return (n <= 1) ? 1 : fib(n - 1) + fib(n - 2);
    };
    std::cout << fib(4) << std::endl;
}

Это происходит из-за того, что тип переменной fib ещё не выведен в момент её использования, а указать его явно мы не может. Это решается несколькими способами: можно передавать лямбде её же как параметр, а можно сохранить её в std::function:

int main() {
    std::function<int(int)> fib = [&fib] (int n) {
        return (n <= 1) ? 1 : fib(n - 1) + fib(n - 2);
    };
    std::cout << fib(4) << std::endl;
}

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

struct mytype {
    mytype(mytype&) {}
};

int main() {
    mytype a = a; // OK
}

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

std::any

Продолжая тему type erasure - в стандартной библиотеке есть тип std::any, который может хранить внутри себя объект любого типа.

int main() {
    std::any a = 42;
    int v = any_cast<int&>(a);
    
    a = std::string("hello");
    std::string s = any_cast<std::string&>(a);
    
    a = mytype();
}

При any_cast к неправильному типу, получим исключение bad_any_cast.

Реализация any

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

struct any {
    struct base_concept {
        virtual ~base_concept() {}
        
        virtual base_concept* clone() = 0;
    };
    
    template <typename T>
    struct model : base_concept {
        model(T value)
            : value(std::move(value)) {}
        model<T>* clone() override {
            return new model<T>(value);
        }
        T value;
    }
    
    template <typename T>
    any(T val) 
    	: obj(new model<T>(val)) {}
    
    any(any const& other) 
        : obj(other.obj ? other.obj->clone : nullptr) {}
	~any() {
        delete obj;
    }
  private:
    base_concept* obj;
    
    template <typename T>
    friend T* any_cast(any* a);
};
template <typename T>
T* any_cast(any* a) {
	if (a) {
		// if (model<T>* m = dynamic_cast<model<T>*>(a->obj)) {
        if (typeid(*a->obj) == typeid(any::model<T>)) {
			return &static_cast<any::model<T>*>(a->obj)->value;
		} else {
            throw std::bad_any_cast;
        }
	}
	return nullptr;
} 

Базовый класс принято называть concept, но это стало ключевым словом в C++20, поэтому назовём егоbase_concept, а производный от него принято называть model.

Note: как можно заметить, у функции clone() в derived-классе возвращаемый тип не совпадает с тем, который указан в базовом. Так можно делать, если в базовом классе функция возвращает указатель или ссылку на базовый класс, то в производном можно возвращать указатель или ссылку на него же.

Иногда может возникнуть желание, чтобы комплировалось c -fnortti (например, чтобы избежать оверхеда на виртуальные таблицы). Можно попытаться сделать так:

template <typename T>
void noop() {}

struct any {
    struct base_concept {
        // ...
        typedef void (*func_t)();
    	virtual func_t get_tag() = 0;
    }
    template <typename T>
    struct model : base_concept {
        // ...
        func_t get_tag() override {
            return &noop<T>;
        }
    }
    // ...
}
template <typename T>
T* any_cast(any* a) {
	if (a) {
        if (a->obj->get_tag() == &noop<T>) {
			return &static_cast<any::model<T>*>(a->obj)->value;
		} else {
            throw std::bad_any_cast;
        }
	}
	return nullptr;
} 

Заводим функцию noop<T>, которая для каждого типа T в одном экземпляре, так как то, как работает линковщик, гарантирует нам это.

Можно вместо функции, использовать глобальную шаблонную переменную:

template <typename T>
char tag;

any_iterator

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

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

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

int main() {
    std::vector<int> v;
    std::list<int> l;
    int* p;
    any_bidirectional_iterator<int> i = v.begin();
    ++i;
    i = l.begin();
    *i;
    i = p;
}

Type erasure

В общем случае такой приём (как в function и any) называется type erasure. Иногда это очень похоже на таблицу виртуальных функций, только написанную руками, но у него есть несколько преимуществ:

• Это эффективная модель, когда не нужен полиморфизм

• Хорошо работает с value-семантикой (перемещения, копирования) - тип ведёт себя так, как будто это обычное значение

• Можно использовать полиморфно классы, у которых нет общего базового, но общий интерфейс

Пример третьего пункта: у классов std::fstream и std::stringstream общий интерфейс, который был продуман заранее. Но это может быть не очевидно на этапе дизайна, поэтому это вполне могли бы быть два разных класса. Тогда, если бы возникло желание использовать их в одном месте, можно было бы прибегнуть к type erasure.

Type alias

Иногда возникает желание сделать шаблонный typedef. Так как typedef пришёл из C, шаблонов у неё не было, поэтому ближайшее, что можно было получить - это сделать шаблонную структуру с typedef внутри неё (например, type_traits реализованы таким образом). Поэтому в C++11 появились type alias со следующим синтаксисом:

template <typename Ret>
typedef Ret (*func_t)(); // так нельзя

template <typename Ret>
using func_t = Ret (*)(); // а так можно

using void_ptr = void*;