std :: function vs template

Graças ao C ++ 11, recebemos a std::functionfamília de wrappers functor. Infelizmente, continuo ouvindo apenas coisas ruins sobre essas novas adições. O mais popular é que eles são terrivelmente lentos. Eu testei e eles realmente são ruins em comparação com os modelos.

#include <iostream>
#include <functional>
#include <string>
#include <chrono>

template <typename F>
float calc1(F f) { return -1.0f * f(3.3f) + 666.0f; }

float calc2(std::function<float(float)> f) { return -1.0f * f(3.3f) + 666.0f; }

int main() {
    using namespace std::chrono;

    const auto tp1 = system_clock::now();
    for (int i = 0; i < 1e8; ++i) {
        calc1([](float arg){ return arg * 0.5f; });
    }
    const auto tp2 = high_resolution_clock::now();

    const auto d = duration_cast<milliseconds>(tp2 - tp1);  
    std::cout << d.count() << std::endl;
    return 0;
}

111 ms vs 1241 ms. Suponho que isso ocorre porque os modelos podem ser bem alinhados, enquanto functions cobrem os internos por meio de chamadas virtuais.

Obviamente, os modelos têm seus problemas como eu os vejo:

• eles precisam ser fornecidos como cabeçalhos, o que não é algo que você não queira fazer ao liberar sua biblioteca como um código fechado,
• eles podem levar o tempo de compilação muito mais longo, a menos que uma extern templatepolítica semelhante seja introduzida,
• não existe (pelo menos para mim) uma maneira limpa de representar requisitos (conceitos, alguém?) de um modelo, exceto um comentário descrevendo que tipo de função é esperado.

Assim, posso assumir que functions pode ser usado como padrão de fato de passagem de functores e em locais onde se espera que modelos de alto desempenho sejam usados?

Editar:

Meu compilador é o Visual Studio 2012 sem CTP.

Em geral, se você estiver enfrentando uma situação de design que lhe permita uma escolha, use modelos . Eu enfatizei a palavra design porque acho que o que você precisa focar é a distinção entre os casos de uso std::functione os modelos, que são bem diferentes.

Em geral, a escolha de modelos é apenas uma instância de um princípio mais amplo: tente especificar o máximo de restrições possível em tempo de compilação . A lógica é simples: se você conseguir detectar um erro ou uma incompatibilidade de tipo, mesmo antes da geração do seu programa, não enviará um programa de buggy ao seu cliente.

Além disso, como você apontou corretamente, as chamadas para funções de modelo são resolvidas estaticamente (ou seja, em tempo de compilação), de modo que o compilador possui todas as informações necessárias para otimizar e possivelmente incorporar o código (o que não seria possível se a chamada fosse executada através de um tabela).

Sim, é verdade que o suporte ao modelo não é perfeito e o C ++ 11 ainda não possui suporte para conceitos; no entanto, não vejo como std::functionisso o salvaria a esse respeito. std::functionnão é uma alternativa aos modelos, mas uma ferramenta para situações de design em que os modelos não podem ser usados.

Um desses casos de uso surge quando você precisa resolver uma chamada em tempo de execução , invocando um objeto que pode ser chamado que adere a uma assinatura específica, mas cujo tipo concreto é desconhecido no momento da compilação. Normalmente, esse é o caso quando você tem uma coleção de retornos de chamada de tipos potencialmente diferentes , mas que você precisa chamar de maneira uniforme ; o tipo e o número dos retornos de chamada registrados são determinados em tempo de execução com base no estado do seu programa e na lógica do aplicativo. Alguns desses retornos de chamada podem ser functors, alguns podem ser funções simples, outros podem ser o resultado de vincular outras funções a determinados argumentos.

std::functione std::bindtambém oferecem um idioma natural para ativar a programação funcional em C ++, onde as funções são tratadas como objetos e são naturalmente curry e combinadas para gerar outras funções. Embora esse tipo de combinação também possa ser alcançado com os modelos, uma situação de design semelhante normalmente vem junto com casos de uso que exigem determinar o tipo de objetos que podem ser combinados em tempo de execução.

Finalmente, há outras situações em que std::functioné inevitável, por exemplo, se você deseja escrever lambdas recursivas ; no entanto, essas restrições são mais ditadas por limitações tecnológicas do que por distinções conceituais que acredito.

Para resumir, concentre-se no design e tente entender quais são os casos de uso conceitual para essas duas construções. Se você as compara da maneira que você fez, você as está forçando a uma arena à qual provavelmente não pertencem.

Andy Prowl cobriu bem questões de design. Isso é, obviamente, muito importante, mas acredito que a pergunta original se refere a mais problemas de desempenho relacionados a std::function.

Primeiro, uma observação rápida sobre a técnica de medição: os 11ms obtidos para calc1não têm nenhum significado. De fato, olhando para o assembly gerado (ou depurando o código do assembly), pode-se ver que o otimizador do VS2012 é inteligente o suficiente para perceber que o resultado da chamada calc1é independente da iteração e move a chamada para fora do loop:

for (int i = 0; i < 1e8; ++i) {
}
calc1([](float arg){ return arg * 0.5f; });

Além disso, percebe que a chamada calc1não tem efeito visível e descarta a chamada completamente. Portanto, os 111ms são o tempo que o loop vazio leva para executar. (Estou surpreso que o otimizador tenha mantido o loop.) Portanto, tenha cuidado com as medições de tempo em loops. Isso não é tão simples quanto parece.

Como foi apontado, o otimizador tem mais problemas para entender std::functione não move a chamada para fora do loop. Portanto, 1241ms é uma medida justa para calc2.

Observe que std::functioné capaz de armazenar diferentes tipos de objetos que podem ser chamados. Portanto, ele deve executar alguma mágica de apagamento de tipo para o armazenamento. Geralmente, isso implica em uma alocação dinâmica de memória (por padrão, através de uma chamada para new). É sabido que esta é uma operação bastante cara.

O padrão (20.8.11.2.1 / 5) incorpora implementações para evitar a alocação dinâmica de memória para objetos pequenos que, felizmente, o VS2012 faz (em particular, para o código original).

Para ter uma idéia de quanto pode ser mais lento quando a alocação de memória está envolvida, alterei a expressão lambda para capturar três floats. Isso torna o objeto que pode ser chamado muito grande para aplicar a otimização de objetos pequenos:

float a, b, c; // never mind the values
// ...
calc2([a,b,c](float arg){ return arg * 0.5f; });

Para esta versão, o tempo é de aproximadamente 16000ms (comparado a 1241ms para o código original).

Por fim, observe que o tempo de vida do lambda encerra o do std::function. Nesse caso, em vez de armazenar uma cópia do lambda, std::functionpoderia armazenar uma "referência" a ele. Por "referência" quero dizer um std::reference_wrapperque é facilmente construído por funções std::refe std::cref. Mais precisamente, usando:

auto func = [a,b,c](float arg){ return arg * 0.5f; };
calc2(std::cref(func));

o tempo diminui para aproximadamente 1860ms.

Eu escrevi sobre isso há um tempo atrás:

http://www.drdobbs.com/cpp/efficient-use-of-lambda-expressions-and/232500059

Como eu disse no artigo, os argumentos não se aplicam ao VS2010 devido ao seu fraco suporte ao C ++ 11. No momento da redação deste artigo, apenas uma versão beta do VS2012 estava disponível, mas seu suporte ao C ++ 11 já era bom o suficiente para esse assunto.

Com Clang, não há diferença de desempenho entre os dois

Usando clang (3.2, tronco 166872) (-O2 no Linux), os binários dos dois casos são realmente idênticos .

-Vou voltar a tocar no final do post. Mas primeiro, gcc 4.7.2:

Já existe muita percepção, mas quero ressaltar que o resultado dos cálculos de calc1 e calc2 não é o mesmo, devido ao alinhamento interno etc. Compare, por exemplo, a soma de todos os resultados:

float result=0;
for (int i = 0; i < 1e8; ++i) {
  result+=calc2([](float arg){ return arg * 0.5f; });
}

com calc2 que se torna

1.71799e+10, time spent 0.14 sec

enquanto com calc1, torna-se

6.6435e+10, time spent 5.772 sec

isso é um fator de ~ 40 na diferença de velocidade e um fator de ~ 4 nos valores. A primeira é uma diferença muito maior do que o OP postado (usando o visual studio). Na verdade, imprimir o valor no final também é uma boa idéia para impedir que o compilador remova o código sem resultado visível (regra como se). Cassio Neri já disse isso em sua resposta. Observe como os resultados são diferentes - Deve-se ter cuidado ao comparar fatores de velocidade de códigos que executam cálculos diferentes.

Além disso, para ser justo, comparar várias maneiras de calcular repetidamente f (3.3) talvez não seja tão interessante. Se a entrada for constante, ela não deve estar em loop. (É fácil para o otimizador perceber)

Se eu adicionar um argumento de valor fornecido pelo usuário a calc1 e 2, o fator de velocidade entre calc1 e calc2 se reduz a um fator de 5, a partir de 40! No visual studio, a diferença é próxima de um fator 2, e no clang, não há diferença (veja abaixo).

Além disso, como as multiplicações são rápidas, falar sobre fatores de desaceleração geralmente não é tão interessante. Uma pergunta mais interessante é: quão pequenas são suas funções e essas são chamadas de gargalo em um programa real?

Clang:

Clang (usei 3.2) produziu binários idênticos quando alterno entre calc1 e calc2 para o código de exemplo (publicado abaixo). Com o exemplo original publicado na pergunta, ambos também são idênticos, mas não demoram muito (os loops são completamente removidos conforme descrito acima). Com o meu exemplo modificado, com -O2:

Número de segundos para executar (melhor de 3):

clang:        calc1:           1.4 seconds
clang:        calc2:           1.4 seconds (identical binary)

gcc 4.7.2:    calc1:           1.1 seconds
gcc 4.7.2:    calc2:           6.0 seconds

VS2012 CTPNov calc1:           0.8 seconds 
VS2012 CTPNov calc2:           2.0 seconds 

VS2015 (14.0.23.107) calc1:    1.1 seconds 
VS2015 (14.0.23.107) calc2:    1.5 seconds 

MinGW (4.7.2) calc1:           0.9 seconds
MinGW (4.7.2) calc2:          20.5 seconds 

Os resultados calculados de todos os binários são os mesmos e todos os testes foram executados na mesma máquina. Seria interessante se alguém com um conhecimento mais profundo do clang ou do VS pudesse comentar sobre quais otimizações podem ter sido feitas.

Meu código de teste modificado:

#include <functional>
#include <chrono>
#include <iostream>

template <typename F>
float calc1(F f, float x) { 
  return 1.0f + 0.002*x+f(x*1.223) ; 
}

float calc2(std::function<float(float)> f,float x) { 
  return 1.0f + 0.002*x+f(x*1.223) ; 
}

int main() {
    using namespace std::chrono;

    const auto tp1 = high_resolution_clock::now();

    float result=0;
    for (int i = 0; i < 1e8; ++i) {
      result=calc1([](float arg){ 
          return arg * 0.5f; 
        },result);
    }
    const auto tp2 = high_resolution_clock::now();

    const auto d = duration_cast<milliseconds>(tp2 - tp1);  
    std::cout << d.count() << std::endl;
    std::cout << result<< std::endl;
    return 0;
}

Atualizar:

Adicionado vs2015. Notei também que existem conversões double-> float em calc1, calc2. Removê-los não altera a conclusão do visual studio (ambos são muito mais rápidos, mas a proporção é a mesma).

Diferente não é o mesmo.

É mais lento porque faz coisas que um modelo não pode fazer. Em particular, ele permite chamar qualquer função que possa ser chamada com os tipos de argumento fornecidos e cujo tipo de retorno seja conversível no mesmo tipo de retorno especificado .

void eval(const std::function<int(int)>& f) {
    std::cout << f(3);
}

int f1(int i) {
    return i;
}

float f2(double d) {
    return d;
}

int main() {
    std::function<int(int)> fun(f1);
    eval(fun);
    fun = f2;
    eval(fun);
    return 0;
}

Observe que o mesmo objeto de função,, funestá sendo passado para as duas chamadas para eval. Possui duas funções diferentes .

Se você não precisa fazer isso, não deve usar std::function.

Você já tem boas respostas aqui, então não vou contradizê-las. Em resumo, comparar std :: function com templates é como comparar funções virtuais com funções. Você nunca deve "preferir" funções virtuais a funções, mas usa funções virtuais quando isso se encaixa no problema, movendo decisões do tempo de compilação para o tempo de execução. A idéia é que, em vez de ter que resolver o problema usando uma solução sob medida (como uma tabela de salto), você use algo que dê ao compilador uma melhor chance de otimizar para você. Também ajuda outros programadores, se você usar uma solução padrão.

Esta resposta pretende contribuir, para o conjunto de respostas existentes, o que eu acredito ser uma referência mais significativa para o custo de tempo de execução das chamadas std :: function.

O mecanismo std :: function deve ser reconhecido pelo que fornece: Qualquer entidade que possa ser chamada pode ser convertida em uma função std :: de assinatura apropriada. Suponha que você tenha uma biblioteca que ajuste uma superfície a uma função definida por z = f (x, y), você pode escrevê-la para aceitar a std::function<double(double,double)>e o usuário da biblioteca pode converter facilmente qualquer entidade que possa ser chamada; seja uma função comum, um método de uma instância de classe ou um lambda, ou qualquer coisa suportada pelo std :: bind.

Diferentemente das abordagens de modelo, isso funciona sem a necessidade de recompilar a função de biblioteca para diferentes casos; consequentemente, pouco código compilado extra é necessário para cada caso adicional. Sempre foi possível fazer isso acontecer, mas costumava exigir alguns mecanismos estranhos, e o usuário da biblioteca provavelmente precisaria construir um adaptador em torno de sua função para fazê-la funcionar. A função std :: constrói automaticamente qualquer adaptador necessário para obter uma interface de chamada de tempo de execução comum para todos os casos, que é um recurso novo e muito poderoso.

Na minha opinião, este é o caso de uso mais importante para std :: function no que diz respeito ao desempenho: estou interessado no custo de chamar uma função std :: muitas vezes depois de ter sido construída uma vez e precisa pode ser uma situação em que o compilador não consegue otimizar a chamada conhecendo a função que está sendo chamada (ou seja, você precisa ocultar a implementação em outro arquivo de origem para obter uma referência adequada).

Fiz o teste abaixo, semelhante ao OP; mas as principais mudanças são:

1. Cada caso faz um loop de 1 bilhão de vezes, mas os objetos std :: function são construídos apenas uma vez. Descobri olhando para o código de saída que 'operador novo' é chamado ao construir chamadas std :: function reais (talvez não quando elas são otimizadas).
2. O teste é dividido em dois arquivos para evitar otimização indesejada
3. Meus casos são: (a) a função é inline (b) a função é passada por um ponteiro de função comum (c) a função é uma função compatível agrupada como std :: function (d) a função é uma função incompatível compatível com um std :: bind, envolvido como std :: function

Os resultados obtidos são:

• case (a) (inline) 1,3 nsec

• todos os outros casos: 3,3 nsec.

O caso (d) tende a ser um pouco mais lento, mas a diferença (cerca de 0,05 ns) é absorvida pelo ruído.

A conclusão é que a função std :: é uma sobrecarga comparável (no momento da chamada) ao uso de um ponteiro de função, mesmo quando há uma adaptação simples de 'ligação' à função real. O inline é 2 ns mais rápido que os outros, mas é uma troca esperada, pois o inline é o único caso que é 'conectado por fio' no tempo de execução.

Quando executo o código de johan-lundberg na mesma máquina, vejo cerca de 39 nsec por loop, mas há muito mais no loop, incluindo o construtor e destruidor da função std ::, que provavelmente é bastante alta uma vez que envolve um novo e excluir.

-O2 gcc 4.8.1, para o destino x86_64 (core i5).

Observe que o código é dividido em dois arquivos, para impedir que o compilador expanda as funções onde são chamadas (exceto no caso em que se destina).

----- primeiro arquivo de origem --------------

#include <functional>


// simple funct
float func_half( float x ) { return x * 0.5; }

// func we can bind
float mul_by( float x, float scale ) { return x * scale; }

//
// func to call another func a zillion times.
//
float test_stdfunc( std::function<float(float)> const & func, int nloops ) {
    float x = 1.0;
    float y = 0.0;
    for(int i =0; i < nloops; i++ ){
        y += x;
        x = func(x);
    }
    return y;
}

// same thing with a function pointer
float test_funcptr( float (*func)(float), int nloops ) {
    float x = 1.0;
    float y = 0.0;
    for(int i =0; i < nloops; i++ ){
        y += x;
        x = func(x);
    }
    return y;
}

// same thing with inline function
float test_inline(  int nloops ) {
    float x = 1.0;
    float y = 0.0;
    for(int i =0; i < nloops; i++ ){
        y += x;
        x = func_half(x);
    }
    return y;
}

----- segundo arquivo de origem -------------

#include <iostream>
#include <functional>
#include <chrono>

extern float func_half( float x );
extern float mul_by( float x, float scale );
extern float test_inline(  int nloops );
extern float test_stdfunc( std::function<float(float)> const & func, int nloops );
extern float test_funcptr( float (*func)(float), int nloops );

int main() {
    using namespace std::chrono;


    for(int icase = 0; icase < 4; icase ++ ){
        const auto tp1 = system_clock::now();

        float result;
        switch( icase ){
         case 0:
            result = test_inline( 1e9);
            break;
         case 1:
            result = test_funcptr( func_half, 1e9);
            break;
         case 2:
            result = test_stdfunc( func_half, 1e9);
            break;
         case 3:
            result = test_stdfunc( std::bind( mul_by, std::placeholders::_1, 0.5), 1e9);
            break;
        }
        const auto tp2 = high_resolution_clock::now();

        const auto d = duration_cast<milliseconds>(tp2 - tp1);  
        std::cout << d.count() << std::endl;
        std::cout << result<< std::endl;
    }
    return 0;
}

Para os interessados, aqui está o adaptador que o compilador construiu para fazer 'mul_by' parecer um float (float) - isso é 'chamado' quando a função criada como bind (mul_by, _1,0.5) é chamada:

movq    (%rdi), %rax                ; get the std::func data
movsd   8(%rax), %xmm1              ; get the bound value (0.5)
movq    (%rax), %rdx                ; get the function to call (mul_by)
cvtpd2ps    %xmm1, %xmm1        ; convert 0.5 to 0.5f
jmp *%rdx                       ; jump to the func

(portanto, poderia ter sido um pouco mais rápido se eu tivesse escrito 0,5f no bind ...) Observe que o parâmetro 'x' chega em% xmm0 e permanece lá.

Aqui está o código na área em que a função é construída, antes de chamar test_stdfunc - execute o c ++ filt:

movl    $16, %edi
movq    $0, 32(%rsp)
call    operator new(unsigned long)      ; get 16 bytes for std::function
movsd   .LC0(%rip), %xmm1                ; get 0.5
leaq    16(%rsp), %rdi                   ; (1st parm to test_stdfunc) 
movq    mul_by(float, float), (%rax)     ; store &mul_by  in std::function
movl    $1000000000, %esi                ; (2nd parm to test_stdfunc)
movsd   %xmm1, 8(%rax)                   ; store 0.5 in std::function
movq    %rax, 16(%rsp)                   ; save ptr to allocated mem

   ;; the next two ops store pointers to generated code related to the std::function.
   ;; the first one points to the adaptor I showed above.

movq    std::_Function_handler<float (float), std::_Bind<float (*(std::_Placeholder<1>, double))(float, float)> >::_M_invoke(std::_Any_data const&, float), 40(%rsp)
movq    std::_Function_base::_Base_manager<std::_Bind<float (*(std::_Placeholder<1>, double))(float, float)> >::_M_manager(std::_Any_data&, std::_Any_data const&, std::_Manager_operation), 32(%rsp)


call    test_stdfunc(std::function<float (float)> const&, int)

Achei seus resultados muito interessantes, então eu procurei um pouco para entender o que está acontecendo. Primeiro, como muitos outros disseram, sem ter os resultados do efeito computacional do estado do programa, o compilador apenas otimizará isso. Em segundo lugar, tendo um 3.3 constante como armamento para o retorno de chamada, suspeito que haverá outras otimizações em andamento. Com isso em mente, alterei um pouco o código de referência.

template <typename F>
float calc1(F f, float i) { return -1.0f * f(i) + 666.0f; }
float calc2(std::function<float(float)> f, float i) { return -1.0f * f(i) + 666.0f; }
int main() {
    const auto tp1 = system_clock::now();
    for (int i = 0; i < 1e8; ++i) {
        t += calc2([&](float arg){ return arg * 0.5f + t; }, i);
    }
    const auto tp2 = high_resolution_clock::now();
}

Dada essa alteração no código, compilei com o gcc 4.8 -O3 e obtive um tempo de 330ms para o calc1 e 2702 para o calc2. Portanto, o uso do modelo foi 8 vezes mais rápido, esse número pareceu suspeito, a velocidade de uma potência de 8 geralmente indica que o compilador vetorizou algo. quando olhei o código gerado para a versão dos modelos, ele estava claramente vectoreizado

.L34:
cvtsi2ss        %edx, %xmm0
addl    $1, %edx
movaps  %xmm3, %xmm5
mulss   %xmm4, %xmm0
addss   %xmm1, %xmm0
subss   %xmm0, %xmm5
movaps  %xmm5, %xmm0
addss   %xmm1, %xmm0
cvtsi2sd        %edx, %xmm1
ucomisd %xmm1, %xmm2
ja      .L37
movss   %xmm0, 16(%rsp)

Onde, como a versão std :: function não estava. Isso faz sentido para mim, uma vez que, com o modelo, o compilador sabe com certeza que a função nunca será alterada ao longo do loop, mas com a função std :: passada, ela poderá mudar, portanto, não poderá ser vetorizada.

Isso me levou a tentar outra coisa para ver se eu poderia fazer o compilador executar a mesma otimização na versão std :: function. Em vez de passar uma função, eu criei uma função std :: como uma var global e chamei isso.

float calc3(float i) {  return -1.0f * f2(i) + 666.0f; }
std::function<float(float)> f2 = [](float arg){ return arg * 0.5f; };

int main() {
    const auto tp1 = system_clock::now();
    for (int i = 0; i < 1e8; ++i) {
        t += calc3([&](float arg){ return arg * 0.5f + t; }, i);
    }
    const auto tp2 = high_resolution_clock::now();
}

Com esta versão, vemos que o compilador agora vetorizou o código da mesma maneira e obtive os mesmos resultados de benchmark.

• modelo: 330ms
• std :: function: 2702ms
• global std :: function: 330ms

Portanto, minha conclusão é que a velocidade bruta de uma função std :: vs uma função de template é praticamente a mesma. No entanto, torna o trabalho do otimizador muito mais difícil.