Warum können Lambdas vom Compiler besser optimiert werden als einfache Funktionen?

171

In seinem Buch stellt The C++ Standard Library (Second Edition)Nicolai Josuttis fest, dass Lambdas vom Compiler besser optimiert werden können als einfache Funktionen.

Darüber hinaus optimieren C ++ - Compiler Lambdas besser als normale Funktionen. (Seite 213)

Warum ist das so?

Ich dachte, wenn es um Inlining geht, sollte es keinen Unterschied mehr geben. Der einzige Grund, an den ich denken könnte, ist, dass Compiler möglicherweise einen besseren lokalen Kontext mit Lambdas haben und so mehr Annahmen treffen und mehr Optimierungen durchführen können.

c++ optimization c++11 lambda compiler-optimization Stephan Dollberg
quelle
Verwandte .
Iammilind
Grundsätzlich gilt die Anweisung für alle Funktionsobjekte , nicht nur für Lambdas.
Newacct
4
Das wäre falsch, da Funktionszeiger auch Funktionsobjekte sind.
Johannes Schaub - litb
2
@litb: Ich glaube, ich bin damit nicht einverstanden. ^ W ^ W ^ W ^ W ^ W ^ W (nachdem ich mir den Standard angesehen habe) Ich war mir dieses C ++ - Ismus nicht bewusst, obwohl ich im allgemeinen Sprachgebrauch denke (und laut wikipedia), Leute meinen Instanz einer aufrufbaren Klasse, wenn sie Funktionsobjekt sagen.
Sebastian Mach
1
Einige Compiler können Lambdas besser optimieren als einfache Funktionen, aber nicht alle :-(
Cody Gray

Antworten:

175

Der Grund dafür ist, dass Lambdas Funktionsobjekte sind. Wenn Sie sie also an eine Funktionsvorlage übergeben, wird eine neue Funktion speziell für dieses Objekt instanziiert. Der Compiler kann somit den Lambda-Aufruf trivial inline.

Für Funktionen, andererseits gilt die alte Einschränkung: eine Funktion Zeiger auf die Funktionsvorlage übergeben wird, und Compiler haben traditionell eine Menge Probleme Anrufe über Funktionszeiger inlining. Sie können theoretisch inline sein, aber nur, wenn auch die umgebende Funktion inline ist.

Betrachten Sie als Beispiel die folgende Funktionsvorlage:

template <typename Iter, typename F>
void map(Iter begin, Iter end, F f) {
    for (; begin != end; ++begin)
        *begin = f(*begin);
}

Nennen wir es mit einem Lambda wie diesem:

int a[] = { 1, 2, 3, 4 };
map(begin(a), end(a), [](int n) { return n * 2; });

Ergebnisse in dieser Instanziierung (vom Compiler erstellt):

template <>
void map<int*, _some_lambda_type>(int* begin, int* end, _some_lambda_type f) {
    for (; begin != end; ++begin)
        *begin = f.operator()(*begin);
}

… Der Compiler weiß _some_lambda_type::operator ()und kann ihn trivial inline aufrufen. (Und das Aufrufen der Funktion mapmit einem anderen Lambda würde eine neue Instanziierung erzeugen, mapda jedes Lambda einen eigenen Typ hat.)

Beim Aufruf mit einem Funktionszeiger sieht die Instanziierung jedoch wie folgt aus:

template <>
void map<int*, int (*)(int)>(int* begin, int* end, int (*f)(int)) {
    for (; begin != end; ++begin)
        *begin = f(*begin);
}

… Und zeigt hier fauf eine andere Adresse für jeden Aufruf von mapund daher kann der Compiler keine Inline-Aufrufe an senden , es fsei denn, der umgebende Aufruf von mapwurde ebenfalls inline geschrieben, damit der Compiler fin eine bestimmte Funktion auflösen kann .

Konrad Rudolph
quelle
4
Vielleicht ist es erwähnenswert, dass das Instanziieren derselben Funktionsvorlage mit einem anderen Lambda-Ausdruck eine völlig neue Funktion mit einem eindeutigen Typ erzeugt, was durchaus ein Nachteil sein kann.
Chill
2
@greggo Auf jeden Fall. Das Problem ist, wenn Funktionen verarbeitet werden, die nicht inline sind (weil sie zu groß sind). Hier kann der Aufruf des Rückrufs bei einem Lambda noch eingefügt werden, bei einem Funktionszeiger jedoch nicht. std::sortist das klassische Beispiel dafür, dass die Verwendung von Lambdas anstelle eines Funktionszeigers hier eine bis zu siebenfache (wahrscheinlich mehr, aber ich habe keine Daten dazu!) Leistungssteigerung bewirkt.
Konrad Rudolph
1
@greggo Du verwechselst zwei Funktionen hier: das, was wir das Lambda sind vorbei an (zB std::sort, oder mapin meinem Beispiel) und das Lambda selbst. Das Lambda ist normalerweise klein. Die andere Funktion - nicht unbedingt. Wir befassen uns mit Inlining-Aufrufen des Lambda innerhalb der anderen Funktion.
Konrad Rudolph
2
@greggo Ich weiß. Dies ist jedoch buchstäblich das, was der letzte Satz meiner Antwort sagt.
Konrad Rudolph
1
Was ich merkwürdig finde (nachdem ich gerade darauf gestoßen bin), ist, dass eine einfache boolesche Funktion, predderen Definition sichtbar ist und die gcc v5.3 verwendet, std::find_if(b, e, pred)nicht inline ist pred, sondern std::find_if(b, e, [](int x){return pred(x);})funktioniert. Clang schafft es, beide zu inline, produziert aber mit dem Lambda nicht so schnell Code wie g ++.
Rici
26

Denn wenn Sie eine "Funktion" an einen Algorithmus übergeben, übergeben Sie tatsächlich einen Zeiger auf die Funktion, sodass dieser einen indirekten Aufruf über den Zeiger auf die Funktion ausführen muss. Wenn Sie ein Lambda verwenden, übergeben Sie ein Objekt an eine speziell für diesen Typ instanziierte Vorlageninstanz, und der Aufruf der Lambda-Funktion ist ein direkter Aufruf, kein Aufruf über einen Funktionszeiger, sodass die Wahrscheinlichkeit sehr viel höher ist.

jcoder
quelle
5
"Der Aufruf der Lambda-Funktion ist ein direkter Aufruf" - in der Tat. Und das Gleiche gilt für alle Funktionsobjekte, nicht nur für Lambdas. Es sind nur Funktionszeiger, die nicht so einfach, wenn überhaupt, eingefügt werden können.
Pete Becker