Как убрать virtual и не сойти с ума: велосипедные генераторы через type loopholes / Хабр

В C++ уже есть корутины. Есть диапазоны. Есть готовые библиотеки.

Но это не мешает взять гаечный ключ и начать собирать генератор вручную.

В предыдущей статье макросы внезапно начинают изображать из себя язык: DO, LET, IS управляют препроцессорным ритуалом и создают DSL. Это синтаксис. Это оболочка. Это фронтенд.

(чтение предыдущей статьи необязательно для понимания этой)

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

В этой статье я строю велосипедный генератор. Самый честный.

С виртуальными методами.
С базовым классом.

Он будет тяжёлым, он будет скрипеть vtabl-ами, он будет оставлять проблемы с производительностью. И именно поэтому он нам нужен.

Потому что прежде чем вырезать virtual, прежде чем призвать ужасы шаблонного метапрограммирования в виде type loopholes, нужно сначала увидеть, что именно мы режем.

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

Она про то, как type erasure ломает оптимизации, и как compile-time фиксация множества continuation-типов позволяет вернуть инлайнинг и оптимизации компилятора.

❯ Первая версия

Основа

В прошлой статье разбирались макросы для следующего DSL:

auto result = DO(
  LET x IS(mx);
  LET y IS(my);
  return make_value(x + y);
);
/*
auto result = ::bind(mx, [&](auto&& x) {
  return ::bind(my, [&](auto&& y) {
    return make_value(x + y);
  })
});
*/

Там поддерживаются и циклы и ветвления, но ядро оно вот.

Можно взять идею этих же трансформаций и сделать на основе этого генераторы.

bind теперь возвращает шаг + continuation
Каждый LET превращается в точку прерывания
Линейный код становится цепочкой состояний

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

Но хранить продолжение в std::function будет совсем не эффективно. Потому используется inplace_function<Signature, Capacity, Alignment>.

Каждый шаг генератора — это значение + функция, которая вернёт следующий шаг. Когда continuation пустой — генератор закончен.

template <typename T>
struct yielder {
  T value;
};

template <typename T, std::size_t Capacity,
          std::size_t Alignment = 8>  // NOLINT
struct generator_continuation {
  using value_type = T;
  struct type {
    T value;
    inplace_function<generator_continuation(), Capacity, Alignment> f;
  };
  std::optional<type> value = std::nullopt;
};

template <typename T, typename F>
constexpr auto bind(yielder<T> value, F&& f) {
  using R = decltype(std::forward<F>(f)(std::monostate{}));
  // R тут это всегда generator_continuation
  return R{.value = typename R::type{.value = std::move(value.value),
                                     .f = [f = std::forward<F>(f)] mutable { return std::move(f)(std::monostate{}); }}}; 
// YIELD(...) это LET _ IS(yielder{...}), который раскрывается в bind и лямбду, 
// которая принимает _. Потому тут передаётся std::monostate в функцию. 
}

Реализация inplace_function

Он должен хранить внутри себя вызываемый объект с описанным интерфейсом вызова, с возможностью перемещения и правильным вызовом деструкторов. Но хранить данные в куче это достаточно медленно, потому используется Small object optimization. Он хранит внутри себя указатель на объект внутри хранилища (чтобы не восстанавливать его потом из адреса хранилища, что может запутать компилятор) и само хранилище. Указатель будет на интерфейс.

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

template <typename R, typename... Args>
struct interface {
  constexpr virtual ~interface() = default;
  constexpr virtual R operator()(Args... args) = 0;
  constexpr virtual interface* move_to(void* ptr) noexcept = 0;
};

Следующим нужно реализовать concrete, который наследуется от base и определяет эти методы. Но тут возникает проблема — placement new не может работать в constexpr контексте в C++23, он так может только начиная с C++26. Потому для constexpr ветки нужно будет забыть про аллокацию в буфере, аллоцировать в куче, а после нужно будет и освобождать там. Это можно сделать через if consteval.

template <typename F, typename R, typename... Args>
struct concrete : interface<R, Args...> {
  F func;
  explicit constexpr concrete(F f) : func(std::move(f)) {
  }
  constexpr R operator()(Args... args) override {
    return func(std::forward<Args>(args)...);
  }
  constexpr interface<R, Args...>* move_to(void* ptr) noexcept override {
    if consteval {
      return new concrete{std::move(this->func)};
    }
    return new(ptr) concrete{std::move(this->func)};
  }
};

Осталось реализовать сам inplace_function:

template <typename Signature, std::size_t Capacity, std::size_t Alignment>
struct inplace_function;

template <typename R, typename... Args, std::size_t Capacity, std::size_t Alignment>
struct inplace_function<R(Args...), Capacity, Alignment> {
  using interface = interface<R, Args...>;

  template <typename F>
  constexpr inplace_function(F&& f) : _ptr(create(std::forward<F>(f))) {}

  constexpr inplace_function(inplace_function&& other) noexcept : _ptr(other._ptr->move_to(_data)) {}
  constexpr inplace_function(const inplace_function&) = delete;
  constexpr inplace_function& operator=(inplace_function&& other) noexcept {
    if (&other == this) {
      return *this;
    }
    std::destroy_at(this);
    std::construct_at(this, std::move(other));
    return *this;
  }
  constexpr auto& operator=(const inplace_function&) = delete;
  constexpr ~inplace_function() {
    if consteval {
      delete _ptr;
      return;
    }
    std::destroy_at(_ptr);
  }
  constexpr R operator()(Args... args) { return (*_ptr)(std::forward<Args>(args)...); }

 private:
  template <typename F>
  constexpr interface* create(F&& f) {
    using T = concrete<std::decay_t<F>, R, Args...>;
    static_assert(sizeof(T) <= Capacity);
    static_assert(Alignment % alignof(T) == 0);
    if consteval {
      return new T{std::forward<F>(f)};
    }
    return new (_data) T{std::forward<F>(f)};
  }
  interface* _ptr;
  alignas(Alignment) std::byte _data[Capacity];
};

Расширение для доступа как к std::ranges

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

struct generator_base {
  template <typename S>
  struct iterator {
    using step_t = decltype(std::declval<S&>().impl()); // impl() возвращает generator_continuation
    using value_type = step_t::value_type;
    using difference_type = std::ptrdiff_t;
    using iterator_concept = std::input_iterator_tag;
    step_t current;

    constexpr value_type operator*() const { return current.value->value; }

    constexpr iterator& operator++() {
      current = current.value->f();
      return *this;
    }

    constexpr void operator++(int) { ++(*this); }

    constexpr bool operator==(std::default_sentinel_t) const { return !current.value; }
  };
  template <typename S>
  constexpr iterator<S> begin(this const S& s) = delete;
  template <typename S>
  constexpr iterator<S> begin(this S& s) {
    return iterator<S>{s.impl()};
  }

  constexpr std::default_sentinel_t end() const noexcept { return std::default_sentinel; }
};

Макросы

И вот уже семантика есть. Осталось лишь адаптировать код для того DSL. Обычно там используется захват по ссылке, но тут лямбда будет вызываться не сразу, захват по ссылке протухнет. Потому нужно его переопределить и взять захват по значению, добавив this для захвата полей объекта генератора.

Использовать DO напрямую не выйдет из-за деталей реализации. Но можно взять его кусок и использовать уже его — EVAL(PARSE_DO_ITERATION(0, 0, _CODE(__VA_ARGS__)))

#undef LAMBDA_CAPTURE
#define LAMBDA_CAPTURE =, this

#define GENERATOR(fields, init, ...)                                                \
  [&] {                                                                             \
    struct : ::generator_base {                                            \
      UNWRAP fields;                                                                \
      constexpr auto impl() { EVAL(PARSE_DO_ITERATION(0, 0, _CODE(__VA_ARGS__))) } \
    } gen{UNWRAP init};                                                             \
    return gen;                                                                     \
  }()

#define YIELD(...) LET _ IS(::yielder{__VA_ARGS__})

И это уже позволяет использовать генераторы:

constexpr auto my_generator() {
  return GENERATOR((int i), (.i = 0),
    YIELD(42);
    WHILE(i != 10) (
      YIELD(i);
      ++i;
    )
    return generator_continuation<int, 24>();
  );
}
static_assert(std::ranges::equal(my_generator(),
                                 std::array{42, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}));

int main() {
  auto gen = my_generator();
  gen.i = 3;
  std::println("{}", gen);  // prints [42, 3, 4, 5, 6, 7, 8, 9]
  /*
  for(auto i : gen) {
    std::println("{}", i);
  }
  */
}

В ходе написания статьи выяснилось, что gcc 15.2 не выдерживает мощи deduction this и уходит в сегфолт, версии до 15.2 просто неправильно с ним работали, но в gcc 15.2.1 уже исправили ошибку.

❯ Производительность первой версии

И вот мы плавно переходим к самому интересному — производительности. Она сейчас весьма печальна. Возьмём простой цикл, который пройдётся по генератору, ничего не сделав:

int main() {
  for(auto _ : my_generator()) {}
}

И если посмотреть в асм, то увидим, что компилятор всё это свернуть не смог.

Это можно увидеть на Godbolt

Минимизация проблемы

Хотелось бы разобраться, что именно так путает компилятор.

Что может быть проще указателей на функции? Почему бы не сделать это на них.

struct type {
  type (*ptr)(int&);
};

type foo(int& i) {
  ++i;
  return type{foo};
}

int main() {
  int i = 0;
  for(type(*f)(int&) = foo;i != 100;f = f(i).ptr);
  return i;
}

И если заглянуть в выхлоп компиляторов (gcc и clang), то они не могут оптимизировать этот код (Godbolt).

Но есть некоторые отличия в оптимизациях между указателями на функции и виртуальными вызовами. Если взять то же самое, но используя виртуальные методы, запихнув всё внутрь namespace {}, то получим результат, что gcc таки может это оптимизировать:

namespace {
struct interface {
  virtual interface* operator()(int&) = 0;
};


struct foo_type : interface {
  interface* operator()(int& ref);
};

foo_type foo;


interface *foo_type::operator()(int& ref) {
    return (ref++, &foo);
}

}
int main() {
  int i = 0;
  for(interface* f = &foo; i != 100; f = (*f)(i));
  return i;
}

В gcc раскрывается в просто return 100, а clang не смог (Godbolt)

Современные компиляторы иногда справляются с девиртуализацией, это возможно благодаря тому, что у компилятора есть полный доступ ко всей информации. Компилятор видит замкнутую иерархию: он точно знает, что нигде более не доступен interface, и он может применить Class Hierarchy Analysis.

Но оптимизация не пройдёт так гладко с указателями на функции. Метаинформация не привязывается к указателям на функции, и компилятору нужно через Interprocedural Dataflow Analysis доказать, что f в каждой точке цикла указывает на одну из конкретных функций. Production-компиляторы выбирают таким не заниматься.

Виртуальные функции выигрывают именно потому, что их «косвенность» формализована семантикой языка: vtable неизменяема, набор возможных реализаций ограничен иерархией, анонимный namespace гарантирует её замкнутость.

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

namespace {
struct interface {
  virtual interface* operator()(int&) = 0;
};


struct bar_type : interface {
  interface* operator()(int& ref) {}
};

struct foo_type : interface {
  interface* operator()(int& ref);
};

foo_type foo;
bar_type bar;

interface *foo_type::operator()(int& ref) {
    return ref++ ? (interface*)&foo : (interface*)&bar;
}

}
int main() {
  int i = 0;
  for(interface* f = &foo; i != 100; f = (*f)(i));
  return i;
}

Godbolt

Тут было несколько типов, анализ из-за этого затруднился. Если же убрать определение метода в bar, то gcc таки сможет провести оптимизацию.

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

❯ Уход от виртуальности

До этого момента мы выяснили главное: проблема не в «стоимости вызова», а в потере информации о множестве возможных continuation-типов.

Девиртуализация компиляторами это достаточно сложная задача, потому можно сделать часть работы самостоятельно. Можно зафиксировать множество типов, создав что-то вроде std::variant.

Для этого нужно собрать список типов, которыми может стать inplace_function, к каждому из них привязать идентификатор, а при вызове на основе этого id выбирать нужную реализацию, подобно тому, что делается в std::visit у std::variant.

За идею использовать лупхолы для сбора типов из функции и помощь с функцией добавления типа в список выражаю благодарность @PaRat07.

Лупхолы

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

template <typename Key>
struct adl_tag {
  friend consteval auto get(adl_tag);
};

template <typename Key, typename Val>
struct injector {
  friend consteval auto get(adl_tag<Key>) {
    return [] -> Val { std::unreachable(); }();
  }
};

template <typename TagT, std::size_t Idx>
struct set_tag {};

template <typename TagT, typename Unique, std::size_t CurIdx = 0>
consteval std::size_t find_first_free() {
  if constexpr (requires {
                  get(adl_tag<set_tag<TagT, CurIdx>>{});
                  typename Unique;
                }) {
    return find_first_free<TagT, Unique, CurIdx + 1>();
  } else {
    return CurIdx;
  }
}

template <typename TagT, typename Val>
consteval auto add_to_set() {
  constexpr std::size_t idx = find_first_free<TagT, Val>();
  std::ignore = injector<set_tag<TagT, idx>, Val>{};
  return idx;
}

template <typename... Ts>
struct type_list {};

template <typename Tag, typename Unique = Tag>
consteval auto read_set() {
  constexpr std::size_t have_cnt = find_first_free<Tag, Tag>();
  return []<std::size_t... Idxs>(std::index_sequence<Idxs...>) {
    return type_list<decltype(get(adl_tag<set_tag<Tag, Idxs>>{}))...>{};
  }(std::make_index_sequence<have_cnt>{});
}

И пример использования

struct tag {};

static_assert(add_to_set<tag, int>() == 0);
static_assert(add_to_set<tag, char>() == 1);
static_assert(find_first_free<tag, tag>() == 2);
static_assert(std::is_same_v<decltype(read_set<tag>()), type_list<int, char>>);

Это можно использовать для сбора типов. И т.к. оно привязано к тегу, то нужно в inplace_function добавить тег:

template <typename Tag, typename Signature, std::size_t Capacity, std::size_t Alignment>
struct inplace_function;

template <typename Tag, typename R, typename... Args, std::size_t Capacity, std::size_t Alignment>
struct inplace_function<Tag, R(Args...), Capacity, Alignment> {
...
};

По причинам, которые будут описаны далее, этот тип не будет работать в constexpr, потому он будет заменён на inline.

Теперь можно добавить добавление типа в это множество в конструкторе, получение Id и выставление его в поле:

...
  template <typename F, auto Id = add_to_set<Tag, std::decay_t<F>>()>
  inline inplace_function(F&& f) : _ptr(create(std::forward<F>(f))), _id(Id) {}
...
 private:
  void* _ptr;
  std::size_t _id;
  alignas(Alignment) std::byte _data[Capacity];
};

И вот уже при каждом inplace_function с новым типом в список будет добавляться новый тип. Но внутри этого же inplace_function должны использоваться move_to, call и destroy, для реализации которых необходимо полное множество этих типов. Нужно отложить задание тела этих функций на потом. Для этого тоже можно использовать лупхолы:

template <typename Tag, typename Signature>
struct declare_function {};

template <typename Tag, typename R, typename... Args>
struct declare_function<Tag, R(Args...)> {
  friend inline void* move_to(declare_function, void* ptr, std::size_t id, void* to);
  friend inline R call(declare_function, void* ptr, std::size_t id, Args...);
  friend inline void destroy(declare_function, void* ptr, std::size_t id);
};

Но если использовать так функции до определения, а определить уже позже, то компилятор не справляется с тем, чтобы выполнить это всё в constexpr. От чего весь код inplace_function и не будет constexpr. Тут используется void*, т.к. от базового типа можно полностью отказаться, а этот код всё равно не работает в constexpr.

Так можно и задать структуру, которая будет определять эти функции:

template <typename Tag, typename Signature>
struct define_function {};

template <typename Tag, typename R, typename... Args>
struct define_function<Tag, R(Args...)> {
  using call_tag = declare_function<Tag, R(Args...)>;
  template <typename Visitor>
  static inline auto visit(Visitor&& visitor, void* ptr, std::size_t id) {
    return visit_ptr(std::forward<Visitor>(visitor), ptr, id, read_set<Tag>());
  }
  friend inline void* move_to(call_tag tag, void* ptr, std::size_t id, void* to) {
    return visit([&]<typename T>(T* ptr) -> void* { return new (to) T{std::move(*ptr)}; }, ptr, id);
  }
  friend inline R call(call_tag tag, void* ptr, std::size_t id, Args... args) {
    return visit([&](auto ptr) -> R { return (*ptr)(std::forward<Args>(args)...); }, ptr, id);
  }
  friend inline void destroy(call_tag tag, void* ptr, std::size_t id) {
    visit([]<typename T>(T* ptr) { ptr->~T(); }, ptr, id);
  }
};

Нужно определить сам visit_ptr для визита:

struct deduct {};

template <typename R = deduct, std::size_t N = 0, typename Visitor, typename... Ts>
inline auto visit_ptr(Visitor&& visitor, void* ptr, std::size_t id, type_list<Ts...> list) {
  using tup = std::tuple<std::type_identity<Ts>...>;
  if constexpr (N == sizeof...(Ts)) {
    return [] -> R { std::unreachable(); }();
  } else {
    auto fn = [&] {
      auto fn = [&] {
        return std::forward<Visitor>(visitor)(static_cast<std::decay_t<decltype(std::get<N>(std::declval<tup>()))>::type*>(ptr));
      };
      if constexpr (std::is_same_v<R, deduct>) {
        return fn();
      } else {
        return [&] -> R { return fn(); }();
      }
    };
    using result = std::conditional_t<std::is_same_v<R, deduct>, decltype(fn()), R>;
    if (id == N) {
      return fn();
    } else {
      return visit_ptr<result, N + 1>(std::forward<Visitor>(visitor), ptr, id, list);
    }
  }
}

Вот так будет выглядеть inplace_function с использованием этих функций (if consteval ветки можно выкинуть):

template <typename Tag, typename Signature, std::size_t Capacity, std::size_t Alignment>
struct inplace_function;

template <typename Tag, typename R, typename... Args, std::size_t Capacity, std::size_t Alignment>
struct inplace_function<Tag, R(Args...), Capacity, Alignment> {
  using call_tag = declare_function<Tag, R(Args...)>;
  template <typename F, auto Id = add_to_set<Tag, std::decay_t<F>>()>
  inline inplace_function(F&& f) : _ptr(create(std::forward<F>(f))), _id(Id) {
  }

  inline inplace_function(inplace_function&& other) noexcept
      : _ptr(move_to(call_tag{}, other._ptr, other._id, _data)), _id(other._id) {}
  inplace_function(const inplace_function&) = delete;
  inline inplace_function& operator=(inplace_function&& other) noexcept {
    if (&other == this) {
      return *this;
    }
    std::destroy_at(this);
    std::construct_at(this, std::move(other));
    return *this;
  }
  auto& operator=(const inplace_function&) = delete;
  inline ~inplace_function() { destroy(call_tag{}, _ptr, _id); }
  inline R operator()(Args... args) { return call(call_tag{}, _ptr, _id, std::forward<Args>(args)...); }

  template <typename F>
  inline void* create(F&& f) {
    using T = std::decay_t<F>;
    static_assert(sizeof(T) <= Capacity);
    static_assert(Alignment % alignof(T) == 0);

    return new (_data) T{std::forward<F>(f)};
  }
 private:
  void* _ptr;
  std::size_t _id;
  alignas(Alignment) std::byte _data[Capacity];
};

И вот пример использования:

int main() {
  struct tag {};
  inplace_function<tag, int(), 1, 0> f = [] {
    return 0;
  };
  inplace_function<tag, int(), 1, 0> f2 = [] {
    return 42;
  };
  f = std::move(f2);
  std::ignore = define_function<tag, int()>{};  
  std::println("{}", f()); // 42
}

И вот уже на основе этого можно сделать генераторы. В текущем виде inplace_function генераторы не будут работать в constexpr, но поддержку constexpr в статье опускаю, так как она не влияет на основной тезис про оптимизацию runtime-кода.

Для изменения генераторов под новый inplace_function нужно изменить generator_continuation:

template <typename Tag, typename T, std::size_t Capacity,
          std::size_t Alignment = 8>
struct generator_continuation {
  using value_type = T;
  struct type {
    T value;
    inplace_function<Tag, generator_continuation(), Capacity, Alignment> f;
  };
  std::optional<type> value = std::nullopt;
};

И изменить макрос GENERATOR, добавив туда define_function и тег:

#define GENERATOR(fields, init, ...)                                                             \
  [&] {                                                                                          \
    struct : ::generator_base {                                                         \
      struct tag {};                                                                             \
      UNWRAP fields;                                                                             \
      constexpr auto impl() {                                                                    \
        EVAL(PARSE_DO_ITERATION(0, 0, _CODE(__VA_ARGS__)));                                      \
        static_assert((std::ignore = define_function<tag, decltype(impl())()>{}, true)); \
      }                                                                                          \
                                                                                                 \
    } gen{UNWRAP init};                                                                          \
    return gen;                                                                                  \
  }()

Теперь проверим оптимизации:

constexpr auto my_generator() {
  return GENERATOR((int i), (.i = 0),
    YIELD(42);
    WHILE(i != 10) (
      YIELD(i);
      ++i;
    )
    return generator_continuation<tag, int, 24>();
  );
}

int main() {
  for(auto _ : my_generator()) {}
}

И если прогнать этот код через clang с O3, то мы увидим… цикл. Он смог оптимизировать это всё в простой цикл, а дальше его убрать не смог. Как говорится, clang переплыл море, но утонул в луже. Но если добавить LTO, то результат меняется в лучшую сторону и всё схлопывается в 0. gcc не смог и с LTO в том числе. Godbolt

❯ Заключение

Мы только что собрали генератор.

Не потому что в C++ их нет. Они есть. Есть корутины, диапазоны, макросные стейт машины через нюансы работы switch. Мы просто решили собрать свой. В начале — с виртуальными функциями, а после — с compile-time реестром типов и ADL-магией.

Сначала всё было динамическим. Компилятор смотрел на это и вежливо говорил: «Раз вы не уверены, то и я не буду».

Потом мы зафиксировали множество типов, выдали каждому id, написали собственный visit и сделали динамический выбор вручную — только так, чтобы компилятор знал весь список типов заранее.

И всё схлопнулось в ноль.

Мораль простая:

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

А этот генератор? Он работает (в том числе может и в constexpr) и хорошо оптимизируется некоторыми компиляторами.

Эта статья это не руководство для «реального кода», но про то, как форма абстракции определяет не только удобство кода, но и то, сколько информации доживает до компилятора.

Иногда велосипед строят не чтобы на нём ездить.

Код из статьи можно увидеть в GitHub репозитории - https://github.com/j4niwzis/do_let_is

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

Как убрать virtual и не сойти с ума: велосипедные генераторы через type loopholes