Performance vs. Abstraktion bei Vergleichsfunktionen

von Hubert Schmid vom 2012-05-13

In der letzten Woche habe ich einen Artikel über die Implementierung von Comparator-Funktionen in Java geschrieben. Der Fokus lag dabei auf der Vereinfachung handgeschriebener Implementierungen, um den Aufwand für Entwicklung und Wartung sowie die Fehleranfälligkeit signifikant zu reduzieren.

Als Reaktion habe ich einige kritische und berechtigte Fragen zur Performance der verschiedenen Implementierungen erhalten. Daher werde ich diesen Aspekt nun genauer betrachten, und allgemein auf den Laufzeit-Overhead eingehen, der durch Indirektion und Abstraktion entsteht. Ich werde zunächst die Beispielklasse und vier Implementierungen der Vergleichsfunktion vorstellen. Anschließend gehe ich auf die Laufzeit-Unterschiede und deren Ursachen ein. Schließlich reiche ich noch die Implementierung einer Hilfsfunktion nach und ziehe ein allgemeines Fazit zu Performance und Abstraktion.

Das Beispiel

Im Gegensatz zum vorherigen Artikel verwende ich dieses Mal die Programmiersprache C++ (2011). Das schafft ein wenig Abwechslung – vereinfacht aber insbesondere die Argumentation über die Laufzeit. Denn Performance-Messungen in Java sind aufgrund der JIT-Übersetzung schwierig und sehr umstritten.

Die folgende Klasse foobar enthält zwei Member-Variablen, wobei die Ordnung anhand _name erfolgt, und bei gleichem Wert nach _id unterschieden wird. Die Funktion ist freistehend deklariert, wodurch in den Implementierungen die Symmetrie hervorgehoben wird. Damit die Funktion aber auch direkt auf die privaten Member-Variablen zugreifen kann, ist sie als friend der Klasse deklariert.

// forward declaration
class foobar;
bool operator<(const foobar& lhs, const foobar& rhs);

// class definition
class foobar
{
private: // --- fields ---
    int _id;
    string _name;
private: // --- friends ---
    friend bool operator<(const foobar& lhs, const foobar& rhs);
};

Zur Vereinfachung soll in diesem Beispiel string eine benutzerdefinierte Klasse sein, deren Vergleichsfunktion nicht inline ist – also nicht offen an der Aufrufstelle eingebaut werden kann. Andernfalls wäre die Argumentation über das Laufzeitverhalten aufgrund der Komplexität von std::string wesentlich schwieriger.

Die Implementierungen

Die erste Implementierung ist einfach ausprogrammiert. Die einzige Besonderheit besteht darin, dass die Member-Variable _name zweimal mit der gleichen Funktion – aber vertauschten Argumenten – verglichen wird. An dieser Stelle hätte ich zwar auch den entsprechenden operator> verwenden können. Der verwendete Stil hat allerdings keine Performance-Nachteile und vereinfacht die generische Programmierung.

bool operator<(const foobar& lhs, const foobar& rhs)
{
    if (lhs._name < rhs._name) {
        return true;
    } else if (rhs._name < lhs._name) {
        return false;
    } else {
        return lhs._id < rhs._id;
    }
}

Die zweite Implementierung erzeugt aus den Member-Variablen ein std::tuple und delegiert den Vergleich. Der Code wirkt dadurch wesentlich aufgeräumter, und die Korrektheit kann einfacher überprüft werden. Für die Konstruktion eines std::tuple gibt es drei verwandte Funktionen: std::make_tuple, std::forward_as_tuple und std::tie. Die Funktionen unterscheiden sich hauptsächlich in den für die Elemente deduzierten Typen. Ich verwende Letztere, weil dabei die Elemente nur per Referenz gespeichert und damit potentiell teure Kopien vermieden werden.

bool operator<(const foobar& lhs, const foobar& rhs)
{
    return std::tie(lhs._name, lhs._id) < std::tie(rhs._name, rhs._id);
}

Bei der dritten Implementierung handelt es sich um eine Variante der vorherigen Version. Die Funktion wurde refaktorisiert und Redundanz beseitigt, indem der gemeinsame Code in eine Lambda-Funktion verschoben wurde. Leider ist deren Syntax zu gesprächig, um den Code dadurch verkürzen zu können. Die Vorteile dieser Variante werden wohl erst bei deutlich mehr Attributen sichtbar.

bool operator<(const foobar& lhs, const foobar& rhs)
{
    auto&& key_fn = [](const foobar& v) {
        return std::tie(v._name, v._id);
    };
    return key_fn(lhs) < key_fn(rhs);
}

Meine vierte und letzte Variante geht in gewisser Weise umgekehrt vor: Anstatt eine Key-Funktion für alle Member-Variablen zu verwenden, wird für jede Member-Variable eine eigene Key-Funktion benutzt. Die einzelnen Funktionen werden von meiner generischen Hilfsfunktion less_with_key_fns der Reihe nach für die beiden zu vergleichenden Objekte aufgerufen und ihre Ergebnisse verglichen. Dieses Vorgehen ist allgemeiner anwendbar, da es sich auch für die Verwendung mit Zugriffsfunktionen eignet, die nur aufgerufen werden sollen, wenn es für den Vergleich erforderlich ist.

bool operator<(const foobar& lhs, const foobar& rhs)
{
    return less_with_key_fns(lhs, rhs, &foobar::_name, &foobar::_id);
}

Um den Schreibaufwand zu reduzieren übergebe ich an Stelle der Funktionen lediglich Zeiger auf Member-Variablen. Diese sind vergleichbar mit Key-Funktionen, denn zusammen mit einer Klasseninstanz ergibt sich jeweils ein Wert. Die Hilfsfunktion less_with_key_fns unterstützt diesen Spezialfall genauso wie Zeiger auf Member-Funktionen. Mehr dazu weiter unten, denn zunächst wende ich mich der Performance zu.

Die Performance

Die Frage zur Performance lässt sich für diese vier Funktionen erstaunlich einfach beantworten: Denn GCC‑4.7 erzeugt mit Release-Optionen auf meinem Rechner für alle vier Funktionen identischen Maschinencode – abgesehen von vertauschter Reihenfolge der Operationen ohne Auswirkung auf die Performance. Die Messung der Laufzeiten kann ich mir damit sparen, denn offensichtlich sind alle vier Funktionen gleich schnell.

Der Optimierer von GCC‑4.7 hat in diesem Fall gute Arbeit geleistet und sämtliche Indirektionen aufgelöst. Oder anders formuliert: Die Indirektionen haben die Lesbarkeit verbessert ohne der Performance zu schaden.

Das Problem ist nur, dass viele Entwickler keine klare Vorstellung davon haben, was ein Übersetzer heutzutage typischerweise leistet – und was nicht. Ich sehe immer wieder große Abweichungen der Erwartungen in beide Richtungen: Auf der einen Seite stehen die Kernel-Entwickler, die Programmiersprachen für bessere Assembler halten und glauben, jeder Befehl würde direkt transformiert werden. Und auf der anderen Seite stehen Anwendungsentwickler, die glauben, der Optimierer könnte auch komplexe Datenstrukturen und Algorithmen durch effiziente Implementierungen ersetzen.

In allen vier Implementierungen ist die Situation aber relativ einfach: Die Funktionen führen nur Operationen aus, die dem Übersetzer bekannt und relativ einfach sind, und die keine Auswirkungen auf andere Programmteile haben. Solche lokalen Optimierungen beherschen Übersetzer üblicherweise sehr gut.

Die Hilfsfunktion

Die Implementierung der Funktion less_with_key_fns ist relativ einfach. Sie verwendet Variadic Templates um eine beliebige Anzahl an Key-Funktionen zu unterstützen, und ist wie üblich rekursiv definiert.

template <typename Lhs, typename Rhs>
bool less_with_key_fns(Lhs&&, Rhs&&)
{
    return false;
}

template <typename Lhs, typename Rhs, typename Head, typename ...Tail>
bool less_with_key_fns(Lhs&& lhs, Rhs&& rhs, Head&& head, Tail&&... tail)
{
    auto&& key_fn = std::ref(head);
    auto&& lk = key_fn(lhs);
    auto&& rk = key_fn(rhs);
    if (lk < rk) {
        return true;
    } else if (rk < lk) {
        return false;
    } else {
        return less_with_key_fns(lhs, rhs, tail...);
    }
}

Bemerkenswert an dieser Funktion finde ich lediglich die Art und Weise, wie die Key-Funktionen ausgeführt werden. Leider gibt es in der Standard-Bibliothek keine generische invoke-Funktion, mit der sich verschiedene, aufrufbare Dinge ausführen lassen. Stattdessen greife ich auf die Funktion std::ref zurück, die Instanzen des Klassen-Templates std::reference_wrapper erzeugt. Diese unterstützen interessanterweise die Ausführung von Zeiger auf Member-Variablen, Zeiger auf Member-Funktionen sowie freistehenden Funktionen. Der Code enthält dadurch zwar eine weitere Indirektion, aber wie oben beschrieben hindert das den Übersetzer nicht an seiner Aufgabe effizienten Code zu erzeugen.

Das Fazit

Höhere Programmiersprachen bieten dem Entwickler Abstraktionsmöglichkeiten, um den Aufwand für Entwicklung und Wartung von Software sowie die Fehleranfälligkeit zu reduzieren. Dabei stellt sich generell die Frage, welche Auswirkungen diese Abstraktionen und Indirektionen auf die Laufzeit-Performance des ausgeführten Codes haben. Verschiedene Programmiersprachen setzen dabei unterschiedliche Prioritäten. Zumindest für C++ lässt sich allerdings sagen, dass es stets ein Ziel war, unnötigen Overhead zu vermeiden und unvermeidbaren Overhead kontrollierbar zu machen. Wie man am Beispiel der Vergleichsfunktionen sieht, funktioniert das in der Praxis ganz gut. Und es bleibt die Hoffnung, dass auch andere Programmiersprachen und Laufzeitumgebungen diese Erwartung erfüllen.