Почему лямбды могут быть лучше оптимизированы компилятором, чем обычные функции?

171

В своей книге The C++ Standard Library (Second Edition)Николай Йосуттис утверждает, что компилятор может оптимизировать лямбды лучше, чем простые функции.

Кроме того, компиляторы C ++ оптимизируют лямбда-выражения лучше, чем обычные функции. (Стр. 213)

Это почему?

Я думал, что когда дело доходит до встраивания, не должно быть никакой разницы. Единственная причина, о которой я мог подумать, заключается в том, что компиляторы могут иметь лучший локальный контекст с лямбдами, и это может сделать больше предположений и выполнить больше оптимизаций.

c++ optimization c++11 lambda compiler-optimization Стефан Доллберг
источник
Относящиеся .
iammilind
По сути, это утверждение относится ко всем функциональным объектам , а не только к лямбдам.
newacct
4
Это было бы неправильно, потому что указатели на функции также являются функциональными объектами.
Йоханнес Шауб - Lit
2
@litb: я думаю, что я не согласен с этим. ^ W ^ W ^ W ^ W ^ W ^ W (после изучения стандарта) я не знал об этом C ++ ism, хотя я думаю на обычном языке (и в соответствии с Википедия), люди имеют в виду экземпляр некоторого вызываемого класса, когда они говорят, что объект функции.
Себастьян Мах
1
Некоторые компиляторы могут лучше оптимизировать лямбды, чем обычные функции, но не все :-(
Коди Грей

Ответы:

175

Причина в том, что лямбды являются объектами функций, поэтому передача их в шаблон функции создаст новую функцию специально для этого объекта. Таким образом, компилятор может тривиально включить лямбда-вызов.

С другой стороны, к функциям применяется старое предостережение: указатель на функцию передается в шаблон функции, и у компиляторов традиционно возникает много проблем с встраиванием вызовов через указатели на функции. Теоретически они могут быть встроенными, но только если встроенная функция также встроена.

В качестве примера рассмотрим следующий шаблон функции:

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

Называя это с лямбда как это:

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

Результаты в этом экземпляре (создан компилятором):

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

… Компилятор знает _some_lambda_type::operator ()и может тривиально вызывать его. (И вызов функции mapс любой другой лямбдой создаст новый экземпляр, mapпоскольку каждая лямбда имеет отдельный тип.)

Но когда вызывается с указателем на функцию, создание экземпляра выглядит следующим образом:

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

… И здесь fуказывает на разные адреса для каждого вызова, mapи, таким образом, компилятор не может встроить вызовы, fесли окружающий вызов mapтакже не был встроен, так что компилятор может разрешить fодну конкретную функцию.

Конрад Рудольф
источник
4
Возможно, стоит упомянуть, что создание экземпляра одного и того же шаблона функции с другим лямбда-выражением создаст совершенно новую функцию с уникальным типом, что вполне может быть недостатком.
холод
2
@greggo Абсолютно. Проблема заключается в обработке функций, которые не могут быть встроены (потому что они слишком велики). Здесь вызов обратного вызова все еще может быть встроенным в случае лямбды, но не в случае указателя на функцию. std::sortклассический пример этого - использование лямбды вместо указателя на функцию приводит к увеличению производительности в семь раз (возможно, больше, но у меня нет данных!)
Конрад Рудольф
1
@greggo Вы путаете две функции здесь: тот , который мы передаем лямбда к (например std::sort, или mapв моем примере) , а сам лямбда. Лямбда обычно маленькая. Другая функция - не обязательно. Мы занимаемся встраиванием вызовов лямбды внутри другой функции.
Конрад Рудольф
2
@greggo, я знаю. Это буквально то, что говорит последнее предложение моего ответа.
Конрад Рудольф
1
Что я нахожу любопытным (только что наткнулся на это), так это то, что данная простая булева функция pred, определение которой видно, и использующая gcc v5.3, std::find_if(b, e, pred)не встроена pred, но std::find_if(b, e, [](int x){return pred(x);})делает это. Clang удается встроить оба, но не производит код так же быстро, как g ++ с лямбда-выражением.
Ричи
26

Потому что, когда вы передаете «функцию» алгоритму, вы фактически передаете указатель на функцию, поэтому он должен выполнять косвенный вызов через указатель на функцию. Когда вы используете лямбду, вы передаете объект в экземпляр шаблона, специально созданный для этого типа, и вызов лямбда-функции является прямым вызовом, а не вызовом через указатель на функцию, поэтому он может быть встроен.

jcoder
источник
5
«вызов лямбда-функции - это прямой вызов» - действительно. И то же самое относится ко всем функциональным объектам, а не только к лямбдам. Это просто указатели на функции, которые не могут быть вставлены так легко, если вообще.
Пит Беккер