Coroutine generator i C++23

Med C++20 fick vi stöd för s.k. stackless coroutines, där man dessvärre var tvungen att skriva en stor del boilerplate code även för tämligen triviala coroutines. Med C++23 fick vi std::generator, som underlättar enormt för en viss kategori av coroutines. I några tidigare artiklar har jag diskuterat hur man kan använda ranges och views för att räkna ord i en textfil. I den här artikeln kommer jag att presentera en lösning baserad på std::generator för att räkna ord i en textfil.

Vad är en coroutine?

En coroutine är en funktion som kan pausa och återuppta sin körning vid behov. Detta gör det möjligt att skapa effektiva generatorer och asynkrona programflöden utan att behöva skriva komplex kod för att hantera tillstånd och kontrollflöde.

Konceptet coroutine föreslogs ursprungligen av Melvin Conway 1963 som en vidareutveckling av begreppet subroutine. Till skillnad från vanliga funktioner som bara har en ingångs- och en utgångspunkt, kan en coroutine pausa och återuppta sin exekvering vid flera punkter. Denna idé implementerades i flera tidiga programmeringsspråk, däribland Simula, som var ett av de första språken att realisera coroutines i praktiken.

Melvin är också upphovet till Conway's lag, som på ett litet spydigt sätt är en observation att system-arkitekturen av en större applikation har samma indelning i subsystem, som avdelningarna hos organisationen.

C++20 coroutines

I C++20 blir en funktion en coroutine genom att innehålla minst ett av nyckelorden co_await, co_yield eller co_return. När kompilatorn upptäcker något av dessa nyckelord i en funktionskropp behandlas funktionen automatiskt som en coroutine istället för en vanlig funktion. Detta innebär att funktionens returvärde inte är det deklarerade typen, utan en s.k. promise type som hanterar coroutinens livscykel och tillstånd.

Tyvärr är det tämligen omständligt att skriva icke-triviala användbara coroutines i C++20. För att en coroutine ska fungera måste man implementera en hel uppsättning av typer och metoder: en promise-typ, en coroutine_handle, och ofta även en iterator-typ om man vill kunna iterera över värden. Detta innebär hundratals rader boilerplate-kod även för relativt enkla användningsfall, vilket gör att många utvecklare tvekar att använda coroutines i praktiken trots deras teoretiska fördelar.

En viktig begränsning med C++20 coroutines är att de är stackless. Detta innebär att man inte kan suspendera körningen inne i en anropad funktion - alla co_await, co_yield och co_return anrop måste finnas direkt i själva coroutine-funktionen. Om man försöker använda dessa nyckelord i en hjälpfunktion som anropas från coroutinen kommer koden inte att kompilera. Denna begränsning kan göra koden mer svårläst då man inte kan dela upp logiken i mindre hjälpfunktioner på samma sätt som med vanliga funktioner.

Det pågår standardiseringsarbete kring stackful coroutines (ibland beskrivet som fibers), men exakt form och tidplan är inte spikad. En stackful coroutine, innebär att man kan suspendera körningen inne i anropade funktioner. Detta kommer att göra coroutines mer flexibla och lättare att använda, men kommer också att förändra hur man skriver och använder coroutines.

C++23 Generator

Med C++23 introducerades std::generator, en standardiserad generator-typ som dramatiskt förenklar skapandet av coroutine-baserade generatorer. std::generator är en template-klass som representerar en lazy-evaluerad sekvens av värden. När man deklarerar en funktion som returnerar std::generator<T> och använder co_yield inuti funktionen, skapar man en generator som producerar värden av typ T på begäran. Generatorn är lazy, vilket innebär att värden endast beräknas när de efterfrågas via iteration, vilket kan ge prestandafördelar för stora datamängder.

En praktisk egenskap, är att std::generator är automatiskt kompatibel med C++20 ranges, vilket innebär att den kan användas med alla range-algoritmer och kombineras med views för kraftfulla datapipelines.

Ett inledande exempel

Låt mig börja med ett mycket trivialt exempel, visat i två versioner så att du får en bättre förståelse för hur std::generator kan användas. Så här ser själva coroutine funktionen ut

#include <generator>
#include <array>
#include <string>
using namespace std::string_literals;

auto ListWord() -> std::generator<std::string> {
    auto const words = std::array{
        "C++"s, "is"s, "cool"s
    };
    for (auto& w : words) co_yield w;
}

Funktionen emitterar värden med hjälp av co_yield. Det som händer "bakom kulisserna" är att generatorn suspenderas och värdet (w) blir tillgängligt för huvudprogrammet. När nästa värde efterfrågas, fortsätter generatorn där den slutade och producerar nästa värde.

Explicit hantering

Så här ser första versionen av huvudprogrammet ut, där jag visar alla steg i hur man interagerar med en generator:

#include <print>

void use_iterator() {
    std::print("iter: ");
    auto coro  = ListWord();     //skapa coroutine
    auto first = coro.begin();   //starta coroutine
    auto last  = coro.end();     //slut-markör
    while (first != last) {      //fortsätt tills slutet
        auto&& word = *first;    //hämta nästa värde
        std::print("{} ", word); //skriv ut
        ++first;                 //fortsätt till nästa värde
    }
    std::println();
}

Anropar vi denna i main(), kompilerar och kör, får vi följande utskrift:

Yes> g++ -std=c++23 -Wall ../list-words.cxx -o list-words
Yes> ./list-words 
iter: C++ is cool

Implicit hantering

Det man kan se i kod-fragmentet ovan är att en generator realiserar en input-iterator, vilket innebär att vi kan använda standard-algoritmer och views för att arbeta med generatorer. Detta medför att vi kan radikalt korta ned funktionen till detta:

void use_for() {
    std::print("for : ");
    for (auto&& w : ListWord()) std::print("{} ", w);
    std::println();
}

int main() {
    use_iterator();
    use_for();
}

Yes> g++ -std=c++23 -Wall ../list-words.cxx -o list-words
Yes> ./list-words 
iter: C++ is cool
for : C++ is cool

Obegränsad generator

Vitsen med lazy-evaluation är att man kan skapa generatorer som emitterar en obegränsad sekvens av värden, givet att det finns en begränsnings-mekanism, såsom t.ex. std::views::take(N).

Namn-listning

Här följer en liten generator som returnerar ett namn slumpat från en intern lista av förnamn.

#include <generator>
#include <string>
#include <array>
#include <random>
#include <ranges>
using namespace std::string_literals;
namespace v = std::ranges::views;

auto generate_name() -> std::generator<std::string> {
    static auto const names = std::array{
        "Anna"s, "Berit"s, "Carin"s, "Doris"s, "Eva"s, "Frida"s, "Gun"s,
        "Adam"s, "Bertil"s, "Carl"s, "Dan"s, "Erik"s, "Fred"s, "Gunnar"s,
    };
    static auto r     = std::default_random_engine{std::random_device{}()};
    static auto index = std::uniform_int_distribution<unsigned>{0, names.size() - 1};

    auto name = ""s;
    while (true) {
        name = names[index(r)];
        co_yield std::move(name);
    }
}

Huvudprogrammet ser ut som följande:

#include <print>
int main() {
    for (auto&& name : generate_name() | v::take(10)) std::print("{} ", name);
    std::println();
}

Kompilerar vi och kör programmet kan det se ut på följande vis:

Yes> g++ -std=c++23 -Wall ../list-names.cxx -o list-names
Yes> ./list-names 
Gunnar Doris Carl Frida Erik Adam Carl Carl Carl Frida 

Fibonacci

Generering av Fibonacci-tal är en klar klassiker och här visar jag en variant som kan emittera en obegränsad sekvens av dylika tal:

#include <generator>
#include <ranges>
#include <utility>
#include <print>
namespace v = std::ranges::views;

auto fibonacci() -> std::generator<unsigned long> {
    auto f0 = 1UL, f1 = 1UL;
    while (true) {
        co_yield f0;
        f0 = std::exchange(f1, f0 + f1);
    }
}

int main(int argc, char* argv[]) {
    auto const N = argc == 1 ? 10U : std::stoi(argv[1]);
    for (auto k: fibonacci() | v::take(N)) std::print("{} ", k);
    std::println();
}

std::exchange sätter f1 till (f0 + f1) och returnerar det gamla värdet av f1, som sedan tilldelas f0

Yes> g++ -std=c++23 -Wall ../fibonacci.cxx -o fibonacci
Yes> ./fibonacci 20
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 
Yes> 

Word-Reader coroutine

I tidigare artiklar har jag visat olika former av en iterator som läser in ord som sekvenser av bokstäver. Rent abstrakt kan man betrakta den som en nästlad tillståndsmaskin (state machine). På övre nivån håller den reda på om det finns ett inläst ord att leverera och på den undre nivån håller den reda på om det finns mer bokstäver att läsa in för det aktuella ordet, samt skannar förbi icke-bokstäver.

En coroutine kan betraktas som en tillståndsmaskin, genom att den vilar i ett tillstånd då den är suspenderad. Här visar jag en motsvarande coroutine som läser in ord från en std::istream och ger ut dem som std::string-objekt.

#pragma once
#include <generator>
#include <istream>
#include <string>
#include "is-letter.hxx"

inline auto WordReaderCoroutine(std::istream& input) -> std::generator<std::string> {
    auto word = std::string{};
    for (char ch; input.get(ch);) {
        if (is_letter(ch)) {
            word.push_back(ch);
        } else {
            if (not word.empty()) {
                co_yield std::move(word);
                word.clear();
            }
        }
    }
    if (not word.empty()) {
        co_yield std::move(word);
    }
}

Så här ser funktionen is_letter ut. Den är avsiktligt enkel och hanterar bara engelsk text och inte fullständig Unicode.

#pragma once
#include <string>
#include <cctype>
inline bool is_letter(int c) {
    if (c == std::char_traits<char>::eof()) return false;
    auto uc = static_cast<unsigned char>(static_cast<char>(c));
    return std::isalpha(uc) || uc == static_cast<unsigned char>('\'');
}

Så här kan ett litet demo program se ut, vilket läser från en istream.

#include <print>
#include <sstream>
#include "word-reader-coroutine.hxx"

int main() {
    auto buffer = std::istringstream{"Anna Berit Carin Doris"};
    for (auto&& word : WordReaderCoroutine(buffer))
        std::println("{}", word);
}

Samt, kompilerar och kör man programmet, kan det se ut så här:

Yes> g++ -std=c++23 -Wall -I../word-reader ../word-reader/word-reader-demo.cxx -o word-reader-demo
Yes> ./word-reader-demo 
Anna
Berit
Carin
Doris

Word-Reader jämförelse

Det kan vara intressant att jämföra iterator versionen med coroutine versionen. All programkod finns i den GitHub repo du finner i länksamlingen i slutet på artikeln. Programkoden för iteratorn har jag visat flera gånger i olika artiklar så av utrymmesskäl visar jag den inte här utan hänvisar till tidigare artiklar eller repon.

Testfallet modelleras som en funktion som tar en reader-factory som argument. Denna kommer antingen skapa en iterator range eller en coroutine. Sedan läser den in ord och räknar upp deras frekvenser. Slutligen skriver den ut de mest vanliga orden och deras frekvenser. Orden som läses in filtreras bort om de är för korta, eller för långa för att rymmas i den SSO buffert som finns i std::string. Dessutom, normaliserar vi orden till gemener. När det är klart, sorteras orden efter frekvens i fallande ordning, samt det mest frekventa orden skrivs ut.

SSO står för Short String Optimization och innebär att kortare ord kan lagras i en liten buffert i std::string istället för att använda heap-allokering. Detta kan förbättra prestanda och minnesanvändning. För GCC är denna buffert 15+1 tecken. Det här är förvisso en implementations specifik optimering och baserad på GCC toolchain.

void use_case(std::string const& name, Params const& params, auto readerFactory) {
    std::println("---- {} ----", name);
    auto start_time = c::steady_clock::now();
    {
        auto freqs = std::unordered_map<std::string, unsigned>{};
        freqs.reserve((fs::file_size(params.filename) / 8) / 4);

        auto non_tiny = [&params](std::string const& w) { 
            return w.size() >= params.min_word_size; 
        };
        auto non_sso  = [&params](std::string const& w) { 
            return w.size() <= params.sso_cutoff; 
        };
        auto lowcase  = [](std::string w) {
            for (char& c: w) {
                c = static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
            }
            return w;
        };

        auto reader   = readerFactory();
        auto pipeline = std::move(reader)
                        | v::filter(non_tiny)
                        | v::filter(non_sso)
                        | v::transform(lowcase);
        for (auto&& word: pipeline) ++freqs[word];

        using WF      = std::pair<std::string, unsigned>;
        auto sortable = std::vector<WF>{};
        sortable.reserve(freqs.size());
        sortable.insert(sortable.end(),
                        std::make_move_iterator(freqs.begin()),
                        std::make_move_iterator(freqs.end()));

        auto top_n        = std::min(sortable.size(), static_cast<size_t>(params.max_words));
        auto cutoff       = sortable.begin() + static_cast<std::ptrdiff_t>(top_n);
        auto by_freq_desc = [](WF const& a, WF const& b) { return a.second > b.second; };
        r::partial_sort(sortable, cutoff, by_freq_desc);

        for (auto const& [word, freq]: sortable | v::take(top_n)) {
            std::println("{}: {}", word, freq);
        }
    }
    auto stop_time = c::steady_clock::now();
    auto elapsed   = c::duration_cast<c::milliseconds>(stop_time - start_time);
    std::println("Elapsed time: {} ms", elapsed.count());
}

Huvudprogrammet ser ut som kod-fragmentet nedan.

struct Params {
    fs::path filename      = fs::path{"../data/shakespeare.txt"};
    unsigned min_word_size = 5;
    unsigned max_words     = 10;
    unsigned sso_cutoff    = 15;
};

int main(int argc, char* argv[]) {
    auto params = Params{};
    //...parse CLI params, check file exists...
    {
        auto file = std::ifstream{params.filename};
        use_case("Coroutine", params, [&file]() {
            return WordReaderCoroutine(file);
        });
    }
    {
        auto file = std::ifstream{params.filename};
        use_case("Iterator", params, [&file]() {
            auto first = WordReaderIterator{file};
            auto last  = WordReaderIterator{};
            return r::subrange{first, last};
        });
    }
}

Till sist, kompilerar och kör vi programmet kan det se ut så här:

Yes> g++ -std=c++23 -Wall -O3 -I../word-reader ../word-reader/word-reader-comparison.cxx -o word-reader-comparison
Yes> ./word-reader-comparison 
---- Coroutine ----
shall: 3586
enter: 2350
which: 2327
would: 2294
their: 2079
there: 1813
should: 1576
these: 1326
where: 1234
speak: 1167
Elapsed time: 187 ms
---- Iterator ----
shall: 3586
enter: 2350
which: 2327
would: 2294
their: 2079
there: 1813
should: 1576
these: 1326
where: 1234
speak: 1167
Elapsed time: 279 ms
Yes>

Upprepar man körningen några gånger, så varierar respektive förfluten tid. Ibland är den ena snabbare än den andra och vice versa. Min toolchain är GCC 15.2 och CPU är en äldre Intel Core i7 1.8 GHz, med 32 GB RAM.

Blocking I/O

Det finns en viktig aspekt att ta hänsyn till innan du springer iväg och konverterar all din programkod till coroutines. Det saknas stöd i standardbiblioteket för asynkron I/O, vilket innebär att anropen till input.get(ch) suspenderar hela programmet tills det finns ett nytt tecken att läsa.

På denna punkt skiljer sig C++ från andra språk/ramverk såsom Node.js där det finns en event-loop och att system-anrop sköts av en dedikerad thread, vilken emitterar en event efter slutförd operation.

Vill man uppnå de riktigt stora fördelarna med coroutines, så får man dessvärre implementera hela detta maskineri på egen hand, vilket är långt ifrån fixat på en kafferast. Eventuellt, återkommer jag i en senare artikel och illustrerar hur detta kan göras.

Sammanfattning

I denna artikel har vi utforskat hur C++23:s std::generator dramatiskt förenklar skapandet av coroutine-baserade generatorer jämfört med C++20:s mer omständliga approach. Vi har sett hur generatorer fungerar som lazy-evaluerade sekvenser som automatiskt är kompatibla med ranges och views, vilket möjliggör kraftfulla datapipelines med minimal boilerplate-kod.

Genom konkreta exempel - från enkla ordlistor och namn-generatorer till Fibonacci-sekvenser - har vi demonstrerat hur co_yield används för att skapa både begränsade och obegränsade sekvenser. Den praktiska tillämpningen kulminerade i en word-reader coroutine som läser och räknar ord från textfiler, där vi kunde jämföra prestanda mellan en traditionell iterator-implementation och coroutine-varianten.

Resultaten visar att båda ansatserna har jämförbar prestanda, men coroutine-varianten erbjuder betydligt enklare och mer läsbar kod. Med std::generator får vi en elegant lösning som kombinerar expressivitet med effektivitet, vilket gör coroutines till ett attraktivt verktyg för att hantera sekventiell databehandling i modern C++.