Weniger Code dank Fold Expressions

Entfaltet

Andreas Fertig

Die mit C++17 eingeführten Fold Expressions machen variadische Templates noch wertvoller. Mit weniger Code lässt sich das gleiche Ergebnis erzielen.

Variadische Templates gehören zu den einflussreichsten Neuerungen in C++11. Diese Art der Klassen und Funktionen kann statt einer vorgegebenen eine beliebige Menge an Argumenten annehmen. Auch deren Typ spielt keine Rolle. Gehalten werden die Argumente in einem Parameter-Pack.

C++17 erweiterte die variadischen Templates um Fold Expressions. Dank ihrer lassen sich die Parameter-Packs direkt durch einen Operator reduzieren. Es existiert eine unäre und eine binäre Version. Beide unterteilen sich wiederum in eine linke und eine rechte Variante. Die Richtung gibt an, von welcher Seite das Parameter-Pack reduziert wird, also wo die Ellipsis steht.

Insgesamt existieren vier Fold-Varianten: unärer Links-Fold, unärer Rechts-Fold, binärer Links-Fold und binärer Rechts-Fold. Ein unärer Rechts-Fold hätte die Form (args + ...), ein binärer Links-Fold die Form (0 + ... + args). Der Vorteil der binären Variante liegt im möglichen initialen Wert, im Beispiel 0. Der ist vor allem dann hilfreich, wenn das Pack leer ist. Sind im Pack args die Werte 3, 4 und 5 enthalten, lautet die expandierte Version des binären Links-Fold 0 + 3 + 4 + 5. Ohne Fold Expressions ist eine Rekursion zum Traversieren des Packs notwendig, was mehr Code erfordert (siehe auch ix.de/zd9w [1, 2]).

Strings mit Fold Expressions verknüpfen

Zur Veranschaulichung der Fold Expressions soll eine Funktion StrCat implementiert werden, die mehrere Strings miteinander verknüpft, dadurch einen neuen String erzeugt und ihn ausgibt. Eine einfache Variante mit C++11-Mitteln zeigt Listing 1.

Listing 1: Die Funktion StrCat zum Verknüpfen mehrerer Strings mit C++11-Mitteln

#include <iostream>
#include <string>

namespace details {
    void StrCat(std::string& buffer) {}
    template<typename T, typename... Ts>
    void StrCat(std::string& buffer, T&& t, Ts&&... ts)
    {
        buffer += t;
        StrCat(buffer, ts...);
    }
}  // namespace details

template<typename... Ts>
std::string StrCat(Ts&&... ts)
{
    std::string ret{};
    details::StrCat(ret, ts...);
    return ret;
}

int main()
{
    std::string a{"Hello,"};
    std::string b{" World"};
    std::string c{"!"};
    auto x = StrCat(a, b, c);
    std::cout << x;
}

Diese Variante hat zwei Schwächen. Erstens erzeugt sie viele Speicherallokationen. Bei jedem Anhängen eines std::string kommt es zu einer Allokation von mehr Speicher, wenn der bereits reservierte Speicher nicht ausreicht. Nicht nur die Allokation selbst ist teuer, auch das Kopieren des existierenden Strings in den neu allozierten Speicher vermindert die Performance.

Die Klasse std::string enthält die Methode reserve, die es erlaubt, eine bestimmte Anzahl an Bytes zu reservieren. Mit der Funktion TotalLen und wenigen Modifikationen lässt sich deshalb die initiale Implementierung verbessern, wie Listing 2 zeigt.

Listing 2: Die Funktion StrCat verbessert mit der Funktion TotalLen

#include <cstdio>
#include <iostream>

namespace details {
    size_t TotalLen() { return 0; }
    template<typename T, typename... Ts>
    size_t TotalLen(T&& t, Ts&&... ts)
    {
        return t.size() + TotalLen(ts...);
    }
    void StrCat(std::string& buffer) {}
    template<typename T, typename... Ts>
    void StrCat(std::string& buffer, T&& t, Ts&&... ts)
    {
        buffer += t;
        StrCat(buffer, ts...);
    }
}  // namespace details

template<typename... Ts>
std::string StrCat(Ts&&... ts)
{
    std::string ret{};
    ret.reserve(details::TotalLen(ts...));
    details::StrCat(ret, ts...);
    return ret;
}

int main()
{
    std::string a{"Hello,"};
    std::string b{" World"};
    std::string c{"!"};
    auto x = StrCat(a, b, c);
    std::cout << x;
}

Ob diese Verbesserung die Performance erhöht, hängt von der Anwendung und der verwendeten Standardbibliothek ab. Bei kurzen Strings ergibt sie wegen der Small String Optimization keinen Unterschied. Viele Implementierungen von std::string verwenden außerdem eine Allokationsstrategie, bei der sie bei jeder neuen Allokation den Speicher verdoppeln. Je nachdem, wie lange die einzelnen Strings sind, wirkt sich die Reservierung durch TotalLen nicht auf die Performance aus.

Die zweite Schwäche sind temporäre Objekte. In der Version von Listing 2 werden diese wie alle anderen Objekte kopiert. Ein std::forward bringt hier keine Performanceverbesserung, move und forward wären nur von Nutzen, wenn sich die Ressourcen tauschen lassen. Im vorliegenden Fall sind die Bytes aber in den Zielstring zu kopieren. Denn ein erfolgreicher std::move würde die zuvor getätigte Reservierung des Zielstrings zerstören. Der Zielstring würde danach die Menge der reservierten Bytes des Quellobjekts und nicht die des präparierten ret-Objekts enthalten. Das Vermeiden zusätzlicher Allokationen und Kopien wäre damit zunichtegemacht. Eine Optimierung temporärer Objekte ist also an dieser Stelle nicht hilfreich.

Die bisherige Implementierung basiert auf C++11, was zeigt, dass sich eine effiziente Stringverknüpfung bereits mit C++11-Mitteln durchführen lässt. Allerdings ist dazu einiges an Codezeilen notwendig. Eindampfen lässt sich der Code mit C++17 und Fold Expressions, wie Listing 3 veranschaulicht.