RVO pro korutiny (C++20)

RVO znamená Return Value Optimization a tentokrát se podíváme na to, jak toto téma ovlivňují korutiny v C++

Co je RVO (Return Value Optimization)

RVO je v C++ standardizované od verze 17. Takže se v tomhle pohledu jedná celkem o novinku. Přesto se překladače snažily o tento typ optimalizace před verzí 17. Pro  vysvětlení, o co přesně jde, začnu příkladem

std::string rvo_hello_world() {
    std::string s = "Hello world";
    return s;
}

int main() {
   std::string v  = rvo_hello_world();
   std::cout << v << std::endl;
}

Pamatuji si dobu, kdy se nedoporučovalo takto programovat, protože výše uvedený kód mohl obsahovat až 3× volání kopírovacího konstruktoru objektu std::string. První kopírování se provádělo z s do dočasné proměnné v return, druhé kopírování z return dočasné proměnné do dočasné proměnné ve výrazu kde se funkce volala a třetí kopírování z dočasné proměnné do v. 

Lze si tedy představit, že každý, kdo takový kód viděl si trhal vlasy

Tak to už neplatí,a od verze 17 je RVO standardizované. Tedy aspoň v základním použití v ve výrazu return a přitom je tvůrcům překladačů doporučeno implementovat optimalizace při vracení lokální proměnné

RVO v return (základní – guaranteed copy elision)

std::string rvo_hello_world() {
    return std::string ("Hello world")
}

int main() {
   std::string v  = rvo_hello_world();
   std::cout << v << std::endl;
}

V tomto případě konstruujeme string přímo ve výrazu return. V C++17 je tato optimalizace povinná, takže lze takto konstruovat i objekt, který má zakázané kopírování a přesouvání. Překladače toto překládají tak, že volající strana dodá ukazatel na místo, kde volaný provede konstrukci návratové hodnoty. V GCC na platformě x86 se k tomuto používá registr rdi. Příklad: https://godbolt.or­g/z/zbazEGsd6

main:
        push    rbx
        sub     rsp, 32
        mov     rdi, rsp 
        call    rvo_hello_world()

RVO z lokální proměnné (Non-mandatory copy/move elision)

V prvním odstavci  tohoto článku je příklad na použití RVO z lokální proměnné. Překladač může lokální proměnnou konstruovat jako návratovou hodnotu. Tato optimalizace je nepovinná a jsou situace, kdy se nedá použít, například, pokud z funkce na různých místech vracíme různé lokální proměnné.

Foo bar() {
   Foo x =...;
   ...
   return x; //RVO
}

Zde překladač bude vyžadovat existenci kopírovacího nebo přesouvacího konstruktoru, i když je nakonec nepoužije. Následující příklad demonstruje aktivaci RVO, protože třída MyString má sice deklarovaný kopírovací konstruktor, ale nikde není jeho definice. Přesto se příklad přeloží a spustí. Pokud by RVO nebylo aktivní, bude si linker stěžovat, že nemůže najít definici kopírovacího konstruktoru

https://godbolt.org/z/zMxE4bEe7

GCC tyto optimalizace provádí i pro ladící sestavení (Debug)

RVO a korutiny (co_return)

Pokud nahradíme return za co_return, tak zjistíme, že všechno je jinak. Rychle odhalíme, že nefunguje ani základní ani rozšířené RVO

task<std::string> rvo_hello_world() {
    co_return std::string ("Hello world"); //není RVO
}

Ukázku s nekopírovatelným MyString najdete zde: https://godbolt.org/z/eMrvbe19E. Zjistíte, že ukázka nejde přeložit, protože MyString nelze konvertovat samu na sebe… protože by to vyžadovalo kopírování.

Ve skutečnosti RVO u co_return nefunguje, protože co_return se překládá jako volání funkce promise_type::return_value(ret). Tato funkce přijímá výsledek výrazu za co_return jako jediný parametr. Pokud tedy funkce přijímá parametr typu jako je návratový typ, pak dochází ke konstrukci návratové hodnoty před zavoláním funkce. Pro uložení návratové hodnoty tak musíme objekt zkopírovat, nebo přesunou.

Z toho vyplývá, že RVO u co_return není možný. Leda že by existoval nějaký trik

Dva způsoby jak udělat RVO v co_return

Nejprve je třeba dodat, že funkci return_value v třídě promise_type lze napsat jako šablonu.

template<std::convertible_to<T> Arg>
void promise_type::return_value(Arg &&arg) {
    _retval.emplace(std::forward<Arg>(arg));
}

Jedinou podmínkou je, že náš argument lze převést na T.  To pak umožňuje zavolat emplace u optional, který zde slouží jako úložiště. Funkce emplace zavolá konstruktor T a předá mu parametr Arg. Nedochází sice ke kopírování, ale s jedním argumentem se moc muziky taky udělat nedá.

Speciální objekt

Toto řešení vyžaduje použití speciálního objektu, který ponese argumenty jako návratovou hodnotu až do konstruktoru. Tady je vyžadována součinnost s cílovým objektem, který tento objekt přijímá v konstruktoru. Například budu mít objekt Foo a ten bude možné konstruovat objektem FooConfig. Objekt Foo není kopírovatelný avšak FooConfig je (nemusí). V co_return tak konstruujeme FooConfig, který pak zkonstruuje Foo na cílovém místě

https://godbolt.org/z/xh838ddGv

Poznámka: V tomto jednoduchém příkladě by se jako speciální objekt dal použít i ukazatel na řetězec (char *), takže program lze přeložit, pokud kód upravíme takto: co_return "Hello world";. Zde funkce return_value() je volána s const char * a ten lze konvertovat na MyString

(Lambda) funkce

O tomto způsobu jsem se dozvěděl v článku Superconstructing super elider a přišlo mi to docela chytrý. I když to nese znaky rovnáku na ohejbák, je to nástroj, který vytrhne trn z paty i v korutinách.

Příkaz co_return připomíná funkci emplace kterou najdete na různých kontejnerech, ať už na optional, nebo mapách, případně na vektoru jako emplace_back nebo emplace_front. Ve všech případech funkce přijímá argumenty, kterými lze zavolat konstruktor typu, který je v kontejneru ukládán. Typicky se používá std::construct_at a tato funkce, která slouží k zahájení života (lifetime) objektu, je typicky implementována pomocí placement new: new (adresa) T( argumenty...)

A přesně tato konstrukce má speciální chování, pokud to zapíšeme takto

new (adresa) T( funkce_vracející_T() )

Tady překladač použije RVO a zavolá funkci, přičemž jí předá pointer na adresa jako místo, kde má zkonstruovat návratovou hodnotu. 

Ovšem k naší smůle už nejde napsat co_return funkce_vracejici_T(), protože se funkce nejprve zavolá a do co_return už vstupuje již zkonstruovaná návratová hodnota té funkce, kterou třeba již nelze kopírovat. Takže to není stejný případ. Nemůžeme ani pouze předat lambdu, protože jak bude placement new vědět, že ji má zavolat? Existuje vůbec nějaký objekt, který se pouhým použitím v parametru „zavolá“ jako funkce?

Naštěstí existuje, takovým horkým kandidátem je objekt, který obsahuje operátor přetypování  operator T(). Tento operátor je ta funkce, která se zavolá při konstrukci T.

Ve výše uvedeném článku se třída, která implementuje tuto vlastnost jmenuje with_result_of. Implementace je jednoduchá

template<std::invocable<> Fn>
class with_result_of {
public:
    using value_type = std::invoke_result_t<Fn>;

    explicit with_result_of(Fn &fn):_fn(fn) {}
    explicit with_result_of(Fn &&fn):_fn(fn) {}

    operator value_type() const {
        return _fn();
    }

protected:
    Fn &_fn;
};

V korutině by se použila takto:

task<MyString> rvo_hello_world() {
    co_return with_result_of([]{return MyString{"Hello world"};});
}

https://godbolt.org/z/ordqY5fxf

Když budete kód krokovat, zjistíte, že lambda se volá až když funkce return_value zavolá emplace nad interní proměnnou typu optional a tam lze pak provést RVO a výsledek uložit přímo uvnitř této instance. 

Výsledný zápis je sice prkenný, ale je to v zásadě jediný obecný způsob, jak provést RVO v korutině. Asi má smysl se tím zabývat tam, kde je o rychlost, nebo kde pracujeme s nepřesouvatelný objekty.

Ještě tu zbývá vyřešit jednoho slona v místnosti. Jde o to, kde je vlastně objekt konstruován. V případě zápisu MyString s = co_await  rvo_hello_world() narazíme na stejný problém. Operátor co_await bude chtít kopírovat výsledek do proměnné s a bude si opět stěžovat na zakázaný kopírovací konstruktor. V příkladě výše se používá jiný přístup. Třída task nabízí funkci get_value() která vrací referenci na uloženou proměnnou. Toto je v zásadě ten způsob, jak si zařídit RVO na straně volajícího. V případě libcoro se používá objekt future, který v určitých situacích umí vracet referenci na proměnnou uloženou uvnitř future.

future<MyString> fs = rvo_funkce();
const MyString &s = co_await fs;

Pozor na to, že se nesmím použít přímý zápis přes co_await:

const MyString &s = co_await rvo_funkce(); //chyba

protože obdržím referenci na zničenou proměnnou (future je zničena na konci výrazu) – naštěstí překladač na to upozorní.

Použití co_await nelze demonstrovat v uvedených příkladech bez netriviální implementace awaiteru, tak snad je to pochopitelné bez příkladu.

RVO u korutin tedy můžeme realizovat na straně volaného pomocí vracení lambda funkce, která se zavolá při konstrukci hodnoty uvnitř promise_type korutiny (task) nebo future (libcoro). Přístup ke zkonstruované proměnné lze zajistit tak, že promise_type nebo future použijeme jako úložiště hodnoty a přistupujeme přes referenci.

Známe problémy

Kromě onoho prkenného zápisu existuje ještě jedna situace, kdy to nebude fungovat. Tím je případ, kdy cílový objekt má konstruktor, který přijímá jakýkoliv argument

template<typename Arg>
Foo::Foo(Arg &&arg);

Tady má tento konstruktor přednost místo volání lambdy. Instance třídy with_result_of je tedy předána jako parametr a záleží už pak na Foo co s tím udělá. Pokud takový objekt máme a chceme, aby se správně volala lambda, je třeba Arg omezit přes vhodně použitý concept.

template<typename T, typename ToObj>
concept hasnt_cast_operator = !requires(T t) {
    {t.operator ToObj()};
};

template<hasnt_cast_operator<Foo> Arg>
Foo::Foo(Arg &&arg);

Řešení v libcoro

Knihovna libcoro má promise_type svých korutin navržené tak, že umožňuje z co_return vždycky vracet  lambdu, bez nutnost přepisu přes with_result_of. Lze tedy psát toto:

future<MyString> rvo_hello_world() {
    co_return []{return MyString{"Hello world"};};
}

Podmínkou je, že vrácený typ musí být invocable vracející T. Pak vrácená lambda je zavolána při konstrukci hodnoty uvnitř vracené future. Implementace má jinou vyhodnocovací větev pro tento případ (přes if constexpr)

template<typename ... Args>
void future::set_value(Args && ... args) {
     try {
         clearStorage();
         if constexpr(std::is_reference_v<T>) {
            std::construct_at(&_value, &args...);
         } else if constexpr(sizeof...(Args) == 1 && (invocable_r_exact<Args, value_store_type> && ...)) {
            new (&_value) value_store_type(args()...);
         } else {
            std::construct_at(&_value, std::forward<Args>(args)...);
         }
         _result = Result::value;

// .....

        } catch (...) {
            set_exception(std::current_exception());
        }
    }

Struktura korutiny pro RVO prakticky.

future<T> korutina(...) {
      //kód...
      co_await...;
      //kód...
      co_await...; //poslední co_await

      co_return [&]{  // "patička" korutiny bez co_await
         T res;
         // nastavení result
         res.xyz = abc;
         return res; //RVO
      };
}

Závěr

Tento článek vznikl na popud studia p1663r0, ve kterém se snaží autoři změnit design korutin tak, aby RVO bylo možné v korutinách. Nezdá se ovšem, že by tento návrh byl kdy přijat. Já jsem se snažil jít cestou, která by nejlépe rezonovala s mou knihovnou libcoro. Není to optimální řešení, ale je to určitá cesta.