В интернете невероятное количество статей о том "как написать свой генератор на С++20", но почти все они сводятся к новичковым хело вордам и почти ни одной статьи о том как написать хороший генератор. Что ж, это нужно исправлять!
что такое генератор
в С++20 добавили корутины(условно говоря функции, которые могут приостанавливать выполнение и продолжать), а генератор это одна из простейших корутин, он просто генерирует значения, причём всегда синхронно.
Пример:
generator<int> ints() {
// после каждого co_yield мы возвращаемся в функцию 'use'
co_yield 1;
co_yield 2;
co_yield 3;
}
void use() {
for(int i : ints()) foo(i);
}Сначала определимся что такое хороший генератор, для меня это когда он:
эффективен, мы всё таки на С++ пишем
удобен в использовании(не провоцирует неявных ошибок, интерфейс понятен даже новичку)
В связи с этим возникает вопрос, зачем писать свой, ведь в С++23 уже добавили std::generator? Ну, во-первых С++23 в проде будет ещё не скоро, а во-вторых std::generator это, к сожалению, одна из худших вещей добавленных в стандартную библиотеку.
Вкратце опишу свои претензии к нему(кстати, его невозможно реализовать без компиляторной магии)
Интерфейс
template<typename Reference, typename Value = void, typename Alloc = void>
class std::generator;Первый = void означает "по дефолту", второй = void означает type erasure! Это сбивает с толку даже матёрого С++ программиста и даже после чтения документации.
Сами авторы признают, что Alloc в этом интерфейсе лишний - логика генератора никак не зависит от того как его аллоцировали. Это должно достигаться специализацией coroutine_traits.
Ну это ещё полбеды, вот вы захотели генератор строк.
Пишем
std::generator<string> foo(); // уже ошиблись = )Это уже будет неэффективно, потому что первый аргумент шаблона - ссылка. Правильно было бы написать generator<string_view>, но тогда на принимающей стороне нужно копировать. В итоге у вас выйдет что то типа generator<string&&, string> или что похуже и одному богу известно будет ли это эффективно.
std::generator буквально неюзабелен. Пройдусь банально по всем его методам:
begin - нельзя вызывать дважды, при этом нет способа проверить вызван ли он уже. Вызовете второй раз - undefined behavior. Хотя ожидаемое лично мной поведение - продолжение итерации с того места, где остановились в предыдущий раз
void foo(std::generator<int> x) {
for(int i : x) // возможно UB, причём проверить будет ли UB нельзя никак
do_smth(i);
}подробный разбор недостатков std::generator
end - возвращает std::default_sentinel всегда, при этом метод не является статическим
деструктор - неявно noexcept, хотя .destroy на хендле который он вызывает может бросить исключение при разрушении локальных объектов на корутине. То есть помимо UB вам подсунули ещё и неявный std::terminate
мув конструктор - проблема в том, что он есть. А дефолтного конструктора нет! Это нонсенс, таким образом после мува конструктор является invalid объектом, который использовать нельзя. Никак. Вообще.
std::pmr::generator - проблема опять же в том, что это существует. Это алиас на генератор с std::pmr::polymorphic_alloc, хотя генератор не является контейнером и не использует этот аллокатор буквально никак, не вдаваясь в подробности - создание этого алиаса это банальный обман пользователя
Ух, что то я увлёкся...
Пишем наконец свой генератор
Итак, мы определились с тем что хотим видеть в генераторе и чего не хотим, для реализации нам понадобится написать
promise type нашей корутины с возможностью yield значение
сущность generator управляющую через промис корутиной
итератор, который будет ссылаться на генератор
Очевидно, что главное что надо сделать это yield и вы можете найти тысячи реализаций в интернете, которые выглядят как-то так:
struct promise {
YieldType value;
auto yield_value(YieldType x) {
value = std::move(x);
return std::suspend_always{};
}
};И это .. неэффективно! Зачем нам хранить и создавать значение, если можно просто взять на него указатель?
struct promise {
YieldType* value;
auto yield_value(Yield&& x) {
value = std::addressof(x);
return std::suspend_always{};
}
};Каждый уважающий себя программист на С++ сразу же, как ему покажется, увидит ошибку. Мы сохраняем указатель на "временный" объект, который разрушится как только вызов yield_value закончится
Но вы забыли, это же корутины! Давайте посмотрим на это из генератора
generator<int> foo() {
co_yield 5;
// мы дойдём до этой точки ТОЛЬКО после того как
// значение будет обработано вызывающей стороной!
}Поэтому, если вспомнить правило "временные значения живут до конца выражения" и цитату стандарта "co_yield x" это yield-expression можно понять, что сохранять указатель это абсолютно безопасно и главное - эффективно.
Теперь насчёт других специальных методов промиса: мы должны решить как будет вести себя генератор на старте, генерировать первое значение сразу или подождать? Тут решение на самом деле неочевидно, но в итоге все реализации приходят к приостановке перед генерацией, чтобы в .begin сгенерировать первое значение и не пропустить ничего... А ещё чтобы генератор не стал за эту первую свою итерацию рекурсивным, сломав что-нибудь по дороге (но о рекурсивности - позже)
std::suspend_always initial_suspend() {
return {};
}
void return_void() {}
// пока приостанавливаемся в конце, чтобы не не уничтожить корутину раньше времени
// но это ещё не окончательно!
std::suspend_always final_suspend() const;Почему то что мы делали до этого неэффективно из зачем нужен рекурсивный генератор
Для этого нужно немного подумать над тем, как наш генератор будут использовать. Представим себе такой код:
generator<int> g() {
for(int x : another_generator())
co_yield x;
}Генератор выбрасывает значения другого генератора. Что при этом происходит?
пробуждается генератор 'g'
он будит генератор 'another_generator'
тот будит какой то ещё генератор и так по цепочке O(N) раз, в конце концов получается значение.
Каждое из пробуждений - достаточно дорогая операция, сравнимая с вызовом функции по указателю
А что если мы будем сразу из самого верхнего генератора в цепочке пробуждать самый нижний, а тот когда сгенерирует значение будет будить опять самый верхний? В этом и кроется суть рекурсивного генератора, он превращает O(N) вызовов для получения значения в гарантированное O(1) и это прекрасно.
Но для реализации подобного поведения нам придётся написать интрузивный список генераторов, а если захочется эффективности, то ещё ооочень много self reference типов промисов.
Но главное - что получается в конце. Нет буквально ни одного лишнего if относительно обычного генератора, весь оверхед - память, 1-2 указателя на 1 генератор. Фактически - оверхед смешной учитывая какие плюсы он даёт.
Идея будет простой: если генератор видит yield другого генератора, то он подключает его в цепочку, говорит ему куда генерировать значения и ... передаёт управление симметричным трансфером. Название сложное, а на деле это просто пробуждение другого генератора. Тот в свою очередь в final_suspend вернёт управление обратно
// Leaf == generator
template <typename Leaf>
struct attach_leaf {
Leaf leaf;
bool await_ready() const noexcept {
return leaf.empty();
}
std::coroutine_handle<> await_suspend(typename Leaf::handle_type owner) const noexcept {
// верим в лучшее, что никто не сделал истинно "рекурсивный"
// генератор и не yield'нул сам себя
assert(owner != leaf.top);
auto& leaf_p = leaf.top.promise();
auto& root_p = *owner.promise().root;
leaf_p.current_worker.promise().root = &root_p;
leaf_p._owner = owner;
root_p.current_worker = leaf_p.current_worker;
return leaf_p.current_worker; // собственно симметричный трансфер управления
}
void await_resume() {
}
};Тут мы вводим несколько новых сущностей:
current_worker - генератор, который сейчас активен(самый нижний в цепочке)
root - самый высокий в цепочке генератор
owner - генератор, в котором yield'нули генератор
Самое интерерсное здесь, пожалуй, то как устроен промис
struct generator_promise {
generator_promise* root = this;
handle_type current_worker = self_handle();
union {
Yield** _current_result_ptr; // setted only in root
handle_type _owner; // setted only in leafs
};
};То есть root по умолчанию это сам генератор, current_worker по умолчанию - тоже он же сам, current_result_ptr вовсе указывает на generator, то есть активный генератор прямо сразу туда складывает значения, минуя вообще всех
Интерфейс нашего генератора:
template <yieldable Y>
struct generator {
private:
Y* current_result = nullptr;
// ещё один хак, чтобы убрать лишние ифы. Можете посмотреть в исходниках
always_done_or<promise_type> top = always_done_coroutine();
public:
...
} // максимально просто и понятноИтог
Мы получили генератор, который эффективен, рекурсивен, имеет дефолтный конструктор и вызов цикл for по дефолтно сконструированному генератору даст 0 значений(напомню std::generator даст UB), можно вызывать begin повторно и просто продолжать итерацию,
dd::generator<int> ints() {
for(int i = 0; i < 50; ++i)
co_yield i;
}
dd::generator<int> other_ints() {
for(int i = 0; i < 50; ++i)
co_yield i;
// elements_of всего лишь тег, рекурсивно yield'им 'ints'
co_yield dd::elements_of(ints());
}
int use_generators() {
auto g = other_ints();
int res = 0;
for(int v : gg) {
res += v;
if (v == 33) break;
}
// спокойно продолжаем итерацию
for (int v : gg)
res += v;
return res;
}Ещё очень много тонкостей с обработкой исключений, кастомизацией аллокаций и мелочами для эффективности, всё это вы можете посмотреть в исходном коде: https://github.com/kelbon/kelcoro
