Dlaczego lambdy mogą być lepiej zoptymalizowane przez kompilator niż zwykłe funkcje?

171

W swojej książce The C++ Standard Library (Second Edition)Nicolai Josuttis stwierdza, że ​​kompilator może lepiej zoptymalizować lambdy niż zwykłe funkcje.

Ponadto kompilatory C ++ optymalizują lambdy lepiej niż zwykłe funkcje. (Strona 213)

Dlaczego?

Pomyślałem, że jeśli chodzi o inlining, nie powinno już być żadnej różnicy. Jedynym powodem, dla którego mogłem wymyślić, jest to, że kompilatory mogą mieć lepszy kontekst lokalny z lambdami, a takie mogą przyjmować więcej założeń i wykonywać więcej optymalizacji.

Stephan Dollberg
źródło
Powiązane .
iammilind,
Zasadniczo instrukcja odnosi się do wszystkich obiektów funkcji , a nie tylko do wyrażeń lambd.
newacct
4
Byłoby to niepoprawne, ponieważ wskaźniki funkcji są również obiektami funkcji.
Johannes Schaub - litb
2
@litb: Myślę, że się z tym nie zgadzam. ^ W ^ W ^ W ^ W ^ W ^ W (po przejrzeniu standardu) Nie byłem świadomy tego C ++, choć myślę w potocznym języku (i zgodnie z wikipedia), ludzie mają na myśli wystąpienie jakiejś-wywoływalnej-klasy, kiedy mówią obiekt funkcji.
Sebastian Mach,
1
Niektóre kompilatory potrafią lepiej optymalizować lambdy niż zwykłe funkcje, ale nie wszystkie :-(
Cody Gray

Odpowiedzi:

175

Powodem jest to, że lambdy są obiektami funkcyjnymi, więc przekazanie ich do szablonu funkcji utworzy wystąpienie nowej funkcji specjalnie dla tego obiektu. Kompilator może więc w trywialny sposób wbudować wywołanie lambda.

Z drugiej strony, w przypadku funkcji obowiązuje stare zastrzeżenie: wskaźnik funkcji jest przekazywany do szablonu funkcji, a kompilatory tradycyjnie mają wiele problemów z wbudowywaniem wywołań za pomocą wskaźników funkcji. Oni mogą być teoretycznie inlined, ale tylko wtedy, gdy funkcja jest otaczająca inlined również.

Jako przykład rozważ następujący szablon funkcji:

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

Nazywając to lambdą w ten sposób:

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

Wyniki w tej instancji (utworzone przez kompilator):

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

… Kompilator zna _some_lambda_type::operator ()i może wbudowane wywołania do niego w trywialny sposób. (I wywołanie funkcji mapz dowolnego innego lambda by utworzyć nowy instancji z mapponieważ każdy lambda ma inny typ).

Ale gdy jest wywoływana ze wskaźnikiem funkcji, instancja wygląda następująco:

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

... i tu fwskazuje na inny adres dla każdego wywołania map, a więc kompilator nie może inline wywołania fchyba otaczający wywołanie mapzostało również inlined tak, że kompilator może rozwiązać fdo jednej konkretnej funkcji.

Konrad Rudolph
źródło
4
Być może warto wspomnieć, że utworzenie instancji tego samego szablonu funkcji z innym wyrażeniem lambda utworzy zupełnie nową funkcję o unikalnym typie, co może być wadą.
wyluzuj
2
@greggo Absolutely. Problem występuje podczas obsługi funkcji, których nie można wstawić (ponieważ są zbyt duże). Tutaj wywołanie funkcji zwrotnej może być nadal wbudowane w przypadku lambda, ale nie w przypadku wskaźnika do funkcji. std::sortto klasyczny przykład tego, że użycie lambd zamiast wskaźnika do funkcji daje tutaj siedmiokrotny (prawdopodobnie więcej, ale nie mam na ten temat danych!) wzrost wydajności.
Konrad Rudolph
1
@greggo pan myli tu dwie funkcje: z jednej mijamy lambda do (na przykład std::sort, czy mapw moim przykładzie), a sama lambda. Lambda jest zwykle mała. Druga funkcja - niekoniecznie. Zajmujemy się wbudowywaniem wywołań lambda wewnątrz innej funkcji.
Konrad Rudolph
2
@greggo Wiem. Tak jest jednak dosłownie w ostatnim zdaniu mojej odpowiedzi.
Konrad Rudolph
1
To, co uważam za ciekawe (właśnie się na to natknąłem), to fakt, że biorąc pod uwagę prostą funkcję boolowską, predktórej definicja jest widoczna, i używając gcc v5.3, std::find_if(b, e, pred)nie jest wbudowywana pred, ale std::find_if(b, e, [](int x){return pred(x);})tak. Clangowi udaje się wstawić oba, ale nie tworzy kodu tak szybko jak g ++ z lambda.
rici
26

Ponieważ kiedy przekazujesz „funkcję” do algorytmu, w rzeczywistości przekazujesz wskaźnik do funkcji, więc musi on wykonać pośrednie wywołanie przez wskaźnik do funkcji. Kiedy używasz lambdy, przekazujesz obiekt do instancji szablonu specjalnie utworzonej dla tego typu, a wywołanie funkcji lambda jest bezpośrednim wywołaniem, a nie wywołaniem przez wskaźnik funkcji, więc jest bardziej prawdopodobne, że może być wbudowane.

jcoder
źródło
5
„wywołanie funkcji lambda jest wywołaniem bezpośrednim” - rzeczywiście. To samo dotyczy wszystkich obiektów funkcji, a nie tylko wyrażeń lambd. To tylko wskaźniki funkcji, których nie można wstawić tak łatwo, jeśli w ogóle.
Pete Becker,