Por que as lambdas podem ser melhor otimizadas pelo compilador do que as funções simples?

171

Em seu livro, The C++ Standard Library (Second Edition)Nicolai Josuttis afirma que as lambdas podem ser melhor otimizadas pelo compilador do que as funções simples.

Além disso, os compiladores C ++ otimizam melhor as lambdas do que as funções comuns. (Página 213)

Por que é que?

Eu pensei que quando se trata de inline não deveria haver mais nenhuma diferença. A única razão pela qual pude pensar é que os compiladores podem ter um melhor contexto local com lambdas e isso pode fazer mais suposições e realizar mais otimizações.

c++ optimization c++11 lambda compiler-optimization Stephan Dollberg
fonte
Relacionado .
Iammilind
Basicamente, a instrução se aplica a todos os objetos de função , não apenas às lambdas.
New121
4
Isso seria incorreto porque os ponteiros de função também são objetos de função.
Johannes Schaub - litb
2
@litb: Eu acho que discordo disso. ^ W ^ W ^ W ^ W ^ W ^ W (depois de analisar o padrão) Eu não estava ciente desse ismo em C ++, embora eu pense em linguagem comum (e de acordo com wikipedia), as pessoas querem dizer instância de alguma classe exigível quando dizem função de objeto.
Sebastian Mach
1
Alguns compiladores podem melhorar lambdas otimizar de funções simples, mas não todos :-(
Cody Grey

Respostas:

175

O motivo é que lambdas são objetos de função, portanto, passá-los para um modelo de função instancia uma nova função especificamente para esse objeto. O compilador pode, assim, alinhar trivialmente a chamada lambda.

Por outro lado, para funções, aplica-se a antiga advertência: um ponteiro de função é passado para o modelo de função, e os compiladores tradicionalmente têm muitos problemas em incluir chamadas por meio de ponteiros de função. Teoricamente, eles podem ser embutidos, mas apenas se a função circundante também estiver embutida.

Como exemplo, considere o seguinte modelo de função:

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

Chamando-o com um lambda como este:

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

Resultados nesta instanciação (criada pelo compilador):

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

… O compilador sabe _some_lambda_type::operator ()e pode fazer chamadas em linha para ele trivialmente. (E invocar a função mapcom qualquer outro lambda criaria uma nova instanciação, mappois cada lambda tem um tipo distinto.)

Mas quando chamada com um ponteiro de função, a instanciação é a seguinte:

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

... e aqui faponta para um endereço diferente para cada chamada mape, portanto, o compilador não pode incorporar chamadas para f, a menos que a chamada ao redor maptambém tenha sido incorporada para que o compilador possa resolver fuma função específica.

Konrad Rudolph
fonte
4
Talvez valha a pena mencionar que a instanciação do mesmo modelo de função com uma expressão lambda diferente criará uma função totalmente nova com um tipo exclusivo, o que pode ser uma desvantagem.
Chill5 /
2
@greggo Absolutamente. O problema é ao lidar com funções que não podem ser incorporadas (porque são muito grandes). Aqui, a chamada para o retorno de chamada ainda pode ser incorporada no caso de um lambda, mas não no caso de um ponteiro de função. std::sorté o exemplo clássico disso usando lambdas, em vez de um ponteiro de função, que aumenta em sete vezes (provavelmente mais, mas não tenho dados sobre isso!) o desempenho aumenta.
Konrad Rudolph
1
@greggo Você está confundindo duas funções aqui: o que estamos passando o lambda para (por exemplo std::sort, ou mapno meu exemplo) eo próprio lambda. A lambda é geralmente pequena. A outra função - não necessariamente. Estamos preocupados em incluir chamadas para o lambda dentro da outra função.
Konrad Rudolph
2
@greggo eu sei. Isso é literalmente o que diz a última frase da minha resposta.
Konrad Rudolph
1
O que eu acho curioso (tendo acabado de descobrir isso) é que, dada uma função booleana simples predcuja definição é visível e o uso do gcc v5.3, std::find_if(b, e, pred)não está alinhado pred, mas std::find_if(b, e, [](int x){return pred(x);})sim. Clang consegue alinhar ambos, mas não produz código tão rápido quanto g ++ com o lambda.
rici
26

Porque quando você passa uma "função" para um algoritmo, na verdade você está passando um ponteiro para funcionar, de modo que ele precisa fazer uma chamada indireta via ponteiro para a função. Quando você usa um lambda, você está passando um objeto para uma instância de modelo especialmente instanciada para esse tipo e a chamada para a função lambda é uma chamada direta, não uma chamada por meio de um ponteiro de função, portanto, é muito provável que seja embutida.

jcoder
fonte
5
"a chamada para a função lambda é uma chamada direta" - de fato. E o mesmo se aplica a todos os objetos de função, não apenas aos lambdas. São apenas indicadores de função que não podem ser incorporados tão facilmente, se é que existem.
Pete Becker