Может ли lambdas перевести на функции?

Ответ 1

TL;DR: если вы используете только lambda, чтобы преобразовать его в указатель на функцию (и только вызывать его с помощью этого указателя функции), всегда бывает выгодно опустить объект закрытия. Оптимизация, которая позволяет это, - это встраивание и удаление мертвого кода. Если вы используете сам лямбда, по-прежнему можно оптимизировать закрытие, но требует несколько более агрессивной межпроцедурной оптимизации.

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

Рассмотрим этот код:

#include <stdio.h>

typedef int (* fnptr_t)(int);
void use_fnptr(fnptr_t fn)
{
    printf("fn=%p, fn(1)=%d\n", fn, fn(1));
}

int main()
{
    auto lam = [] (int x) { return x + 1; };
    use_fnptr((fnptr_t)lam);
}

Теперь я скомпилирую его и выдаю промежуточное представление (для версий до 6, вы должны добавить -std=c++11):

g++ test.cc -fdump-tree-ssa

Немного очищенный и отредактированный (для краткости) дамп выглядит следующим образом:

// _ZZ4mainENKUliE_clEi
main()::<lambda(int)> (const struct __lambda0 * const __closure, int x)
{
    return x_1(D) + 1;
}

// _ZZ4mainENUliE_4_FUNEi
static int main()::<lambda(int)>::_FUN(int) (int D.2780)
{
    return main()::<lambda(int)>::operator() (0B, _2(D));
}

// _ZZ4mainENKUliE_cvPFiiEEv
main()::<lambda(int)>::operator int (*)(int)() const (const struct __lambda0 * const this)
{
    return _FUN;
}

int main() ()
{
    struct __lambda0 lam;
    int (*<T5c1>) (int) _3;
    _3 = main()::<lambda(int)>::operator int (*)(int) (&lam);
    use_fnptr (_3);
}

То есть, lambda имеет 2 функции-члена: оператор вызова функции и оператор преобразования и одну статическую функцию-член _FUN, которая просто вызывает lambda с this, установленным на ноль. main вызывает оператор преобразования и передает результат use_fnptr - точно так же, как он написан в исходном коде.

Я могу написать:

extern "C" int _ZZ4mainENKUliE_clEi(void *, int);

int main()
{
    auto lam = [] (int x) { return x + 1; };
    use_fnptr((fnptr_t)lam);
    printf("%d %d %d\n", lam(10), _ZZ4mainENKUliE_clEi(&lam, 11), __lambda0::_FUN(12));
    printf("%p %p\n", &__lambda0::_FUN, (fnptr_t)lam);
   return 0;
}

Эта программа выводит:

fn=0x4005fc, fn(1)=2
11 12 13
0x4005fc 0x4005fc

Теперь, я думаю, это довольно очевидно, что компилятор должен включить lambda (_ZZ4mainENKUliE_clEi) в _FUN (_ZZ4mainENUliE_4_FUNEi), потому что _FUN является единственным вызывающим. И inline operator int (*)(int) в main (потому что этот оператор просто возвращает константу). GCC делает именно это при компиляции с оптимизацией (-O). Вы можете проверить это как:

g++ test.cc -O -fdump-tree-einline

Файл дампа:

// Considering inline candidate main()::<lambda(int)>.
//   Inlining main()::<lambda(int)> into static int main():<lambda(int)>::_FUN(int).

static int main()::<lambda(int)>::_FUN(int) (int D.2822)
{
    return _2(D) + 1;
}

Объект закрытия исчез. Теперь, более сложный случай, когда используется сама лямбда (не указатель функции). Рассмотрим:

#include <stdio.h>

#define PRINT(x)    printf("%d", (x))
#define PRINT1(x)   PRINT(x); PRINT(x); PRINT(x); PRINT(x);
#define PRINT2(x)   do { PRINT1(x) PRINT1(x) PRINT1(x) PRINT1(x) } while(0)

__attribute__((noinline)) void use_lambda(auto t)
{
    t(1);
}

int main()
{
    auto lam = [] (int x) { PRINT2(x); };
    use_lambda(lam);
    return 0;
}

GCC не будет встраивать lambda, потому что он довольно большой (для этого я использовал printf):

g++ test2.cc -O2 -fdump-ipa-inline -fdump-tree-einline -fdump-tree-esra

Сброс раннего клина:

Considering inline candidate main()::<lambda(int)>
  will not early inline: void use_lambda(auto:1) [with auto:1 = main()::<lambda(int)>]/16->main()::<lambda(int)>/19, growth 46 exceeds --param early-inlining-insns

Но пропуск "ранней межпроцедурной скалярной замены агрегатов" будет делать то, что мы хотим:

;; Function main()::<lambda(int)> (_ZZ4mainENKUliE_clEi, funcdef_no=14, decl_uid=2815, cgraph_uid=12, symbol_order=12)
IPA param adjustments: 0. base_index: 0 - __closure, base: __closure, remove_param
  1. base_index: 1 - x, base: x, copy_param

Первый параметр (т.е. замыкание) не используется, и он удаляется. К сожалению, межпроцедурная SRA не может оптимизировать просадку, которая вводится для захваченных значений (хотя бывают случаи, когда это было бы очевидно выгодно), поэтому есть еще место для улучшений.

Ответ 2

Из лямбда-выражений §5.1.2 p6 (черновик N4140)

Тип замыкания для не-общего лямбда-выражения без лямбда-захвата имеет публичную не виртуальную не- явная функция преобразования const в указатель на функцию с языковой связью языка С++ с одинаковым параметром и возвращаемыми типами в качестве оператора вызова функции закрытия.

Ответ 3

Стандартная цитата уже опубликована, я хочу добавить несколько примеров. Вы можете назначить lambdas для работы указателей, пока нет захваченных переменных:

Допустимо:

int (*f)(int) = [] (int x) { return x + 1; };  // assign lambda to function pointer
int z = f(3);  // use the function pointer

Illegal:

int y = 5;
int (*g)(int) = [y] (int x) { return x + y; };  // error

Допустимо:

int y = 5;
int z = ([y] (int x) { return x + y; })(2);  // use lambda directly

(Edit)
Поскольку мы не можем спросить Бьярне, что он имел в виду, я хочу попробовать несколько интерпретаций.

"translate" означает "convert"
Это то, что я понял изначально, но теперь ясно, что вопрос заключается не в этом возможном значении.

"переводить", как используется в стандарте С++, что означает "скомпилировать" (более или менее)
Как уже отмечал Себастьян Редл, на двоичном уровне нет функциональных объектов. Есть только коды операций и данных, и стандарт не говорит о каких-либо двоичных форматах и ​​не указывает их.

"translate" означает "быть семантически эквивалентным"
Это означало бы, что если A и B семантически эквивалентны, полученный двоичный код для A и B может быть одним и тем же. Остальная часть моего ответа использует эту интерпретацию.

A закрытие состоит из двух частей:

• утверждения в лямбда-теле, "код"
• захваченные значения переменных или ссылки, "данные"

Это эквивалентно функтору, как уже указывалось в вопросе.

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

A функция, с другой стороны, не имеет связанных с ней данных. Конечно, есть аргументы, но они должны предоставляться вызывающим и могут меняться от одного вызова к другому. Это семантическая разница с закрытием, где связанные переменные не могут быть изменены и не предоставляются вызывающим абонентом.

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

Так что нет, лямбда вообще не семантически эквивалентна функции.

Существует очевидный частный случай лямбда без захваченных переменных, где функтор состоит только из кода, и это эквивалентно функции.

Но, можно сказать, что лямбда семантически эквивалентна функции set. Каждое возможное закрытие (отличная комбинация значений/ссылок для связанных переменных) будет эквивалентно одной функции в этом наборе. Конечно, это может быть полезно только тогда, когда связанные переменные могут иметь только очень ограниченный набор значений /, являются ссылками только на несколько разных переменных, если вообще. Например, я не вижу причин, по которым компилятор не мог рассматривать следующие два фрагмента как эквивалент (почти *):

void Test(bool cond, int x)
{
    int y;
    if(cond) y = 5;
    else y = 3;
    auto f = [y](int x) { return x + y; };
    // more code that
    // uses f
}

Умный компилятор мог видеть, что y может иметь только значения 5 или 3 и компилировать, как если бы он был написан следующим образом:

int F1(int x)
{
    return x + 5;
}

int F2(int x)
{
    return x + 3;
}

void Test(bool cond, int x)
{
    int (*f)(int);
    if(cond) f = F1;
    else f = F2;
    // more code that
    // uses f
}

(*) Конечно, это зависит от того, что именно делает more code that uses f.

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

Другим замечанием, которое может быть полезно, является запрос

может ли этот объект [замыкание] быть пропущенным и иметь обычную функцию? Если да, то когда и как?

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

Ответ 4

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

int (*f) = []() { return 0; }

Если вы скомпилируете это с помощью:

clang++ -std=c++11 -S -o- -emit-llvm a.cc

Для определения лямбда вы получаете следующий байт-код LLVM:

define internal i32 @"_ZNK3$_0clEv"(%class.anon* %this) #0 align 2 {
  %1 = alloca %class.anon*, align 8
  store %class.anon* %this, %class.anon** %1, align 8
  %2 = load %class.anon** %1
  ret i32 0
}

define internal i32 @"_ZN3$_08__invokeEv"() #1 align 2 {
  %1 = call i32 @"_ZNK3$_0clEv"(%class.anon* undef)
  ret i32 %1
}

Первая функция принимает экземпляр %class.anon* и возвращает 0: этот оператор вызова. Второй создает экземпляр этого класса (undef), а затем вызывает его оператор вызова и возвращает значение.

Когда скомпилировано с -O2, вся лямбда превращается в:

define internal i32 @"_ZN3$_08__invokeEv"() #0 align 2 {
  ret i32 0
}

Итак, для одной функции, которая возвращает 0.

Я упомянул, что лямбда преобразуется в объект функции или в функцию, если удобная

То, что делает clang! Он преобразует лямбда в объект функции и, если возможно, оптимизирует его для функции.

Ответ 5

Нет, это невозможно. Lambdas определены как функторы, и я не вижу здесь правила as-if.

[C++14: 5.1.2/6]: Тип замыкания для не-общего лямбда-выражения без лямбда-захвата имеет публичную не виртуальную неявную функцию преобразования const в указатель на функцию с С++ языковой связью (7.5) с тем же параметром и возвращаемые типы, как оператор вызова функции закрытия. [..]

& hellip, за которым следуют аналогичные формулировки для родовых лямбдов.