std:: función vs plantilla

Andy Prowl ha cubierto muy bien los problemas de diseño. Esto es, por supuesto, muy importante, pero creo que la pregunta original se refiere a más problemas de rendimiento relacionados con std::function.

En primer lugar, un comentario rápido sobre la técnica de medición: Los 11ms obtenidos para calc1 no tienen ningún significado. De hecho, mirando el ensamblado generado (o depurando el código del ensamblado), uno puede ver que el optimizador de VS2012 es lo suficientemente inteligente como para darse cuenta de que el resultado de llamar calc1 es independiente del iteración y mueve la llamada fuera del bucle:

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

Además, se da cuenta de que llamar a calc1 no tiene ningún efecto visible y elimina la llamada por completo. Por lo tanto, el 111ms es el tiempo que tarda el bucle vacío en ejecutarse. (Me sorprende que el optimizador haya mantenido el bucle.) Por lo tanto, tenga cuidado con las mediciones de tiempo en bucles. Esto no es tan simple como podría parecer.

Como se ha señalado, el optimizador tiene más problemas para entender std::function y no mueve la llamada de bucle. Así que 1241ms es una medida justa para calc2.

Observe que, std::function es capaz de almacenar diferentes tipos de callable objetos. Por lo tanto, debe realizar alguna magia de borrado de tipo para el almacenamiento. Generalmente, esto implica una asignación de memoria dinámica (por defecto a través de una llamada a new). Es bien sabido que esta es una operación bastante costosa.

El estándar (20.8.11.2.1 / 5) encorages implementaciones para evitar la asignación de memoria dinámica para objetos pequeños que, afortunadamente, VS2012 lo hace (en particular, para el código original).

Para tener una idea de cuánto más lento puede ser cuando está involucrada la asignación de memoria, he cambiado la expresión lambda para capturar tres float s. Esto hace que el objeto llamable sea demasiado grande para aplicar la optimización de objetos pequeños:

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

Para esta versión, el tiempo es de aproximadamente 16000ms (en comparación con 1241ms para el código original).

Finalmente, observe que la vida de la lambda encierra la de la std::function. En este case, en lugar de almacenar una copia de la lambda, std::function podría almacenar una "referencia" a ella. Por "referencia" me refiero a un std::reference_wrapper que es fácilmente construido por las funciones std::ref y std::cref. Más precisamente, usando:

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

El tiempo disminuye a aproximadamente 1860ms.

Escribí sobre eso hace un tiempo:{[18]]}

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

Como dije en el artículo, los argumentos no se aplican para VS2010 debido a su pobre soporte para C++11. En el momento de la escritura, solo una versión beta de VS2012 estaba disponible, pero su soporte para C++11 ya era lo suficientemente bueno para este asunto.

Con Clang no hay diferencia de rendimiento entre los dos

Usando clang (3.2, trunk 166872) (-O2 en Linux), los binarios de los dos casos son en realidad idénticos.

-Volveré a clang al final del post. Pero primero, gcc 4.7.2:

Ya hay un montón de insight pasando, pero quiero señalar que el resultado de los cálculos de calc1 y calc2 no son los mismos, debido a in-lining etc. Comparar por ejemplo la suma de todos resultados:

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

Con calc2 que se convierte en

1.71799e+10, time spent 0.14 sec

Mientras que con calc1 se convierte en

6.6435e+10, time spent 5.772 sec

Eso es un factor de ~40 en la diferencia de velocidad, y un factor de ~4 en los valores. La primera es una diferencia mucho mayor que lo que OP publicó (usando visual studio). En realidad, imprimir el valor a the end también es una buena idea para evitar que el compilador elimine código sin resultado visible (como si fuera una regla). Cassio Neri ya lo dijo en su respuesta. Tenga en cuenta lo diferentes que son los resultados -- Se debe tener cuidado al comparar los factores de velocidad de los códigos que realizan diferentes cálculos.

Además, para ser justos, comparar varias formas de calcular repetidamente f(3.3) quizás no sea tan interesante. Si la entrada es constante no debe estar en un bucle. (Es fácil para el optimizador darse cuenta)

Si añado un argumento de valor suministrado por el usuario a calc1 y 2 el factor de velocidad entre calc1 y calc2 se reduce a un factor de 5, de 40! Con visual studio la diferencia está cerca de un factor de 2, y con clang no hay diferencia (ver más abajo).

Además, como las multiplicaciones son rápidas, hablar de factores de ralentización a menudo no es tan interesante. Una pregunta más interesante es, ¿qué tan pequeñas son sus funciones, y son estas llamadas el cuello de botella en un programa real?

Clang:

Clang (usé 3.2) realmente produjo binarios idénticos cuando volteo entre calc1 y calc2 para el código de ejemplo (publicado a continuación). Con el ejemplo original publicado en la pregunta ambos también son idénticos pero no toman tiempo en absoluto (los bucles se eliminan por completo como se describió anteriormente). Con mi ejemplo modificado, con-O2:

Número de segundos para ejecutar (mejor 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 

Los resultados calculados de todos los binarios son los mismos, y todas las pruebas se ejecutaron en la misma máquina. Sería interesante si alguien con un conocimiento más profundo de clang o VS pudiera comentar qué optimizaciones se pueden haber hecho.

Mi código de ensayo 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;
}

Actualización:

Añadido vs2015. También noté que hay conversiones de doble - > float en calc1, calc2. Eliminarlos no cambia la conclusión de visual studio (ambos son mucho más rápidos, pero la relación es aproximadamente la misma).

Diferente no es lo mismo.

Es más lento porque hace cosas que una plantilla no puede hacer. En particular, le permite llamar a cualquier función que se pueda llamar con los tipos de argumento dados y cuyo tipo de retorno es convertible al tipo de retorno dado desde el mismo código.

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;
}

Tenga en cuenta que el objeto de función same, fun, se pasa a ambas llamadas a eval. Tiene dos diferentes funciones.

Si no necesitas hacer eso, entonces deberías no usar std::function.

Ya tienes algunas buenas respuestas aquí, así que no voy a contradecirlas, en resumen comparar std::function con plantillas es como comparar funciones virtuales con funciones. Nunca debe "preferir" funciones virtuales a funciones, sino que usa funciones virtuales cuando se ajusta al problema, moviendo las decisiones del tiempo de compilación al tiempo de ejecución. La idea es que en lugar de tener que resolver el problema utilizando una solución a medida (como una tabla de salto) se utiliza algo que le da al compilador un mejor oportunidad de optimizar para usted. También ayuda a otros programadores, si utiliza una solución estándar.

Esta respuesta tiene la intención de contribuir, al conjunto de respuestas existentes, lo que creo que es un punto de referencia más significativo para el costo de tiempo de ejecución de las llamadas a funciones std::.

El mecanismo std::function debe ser reconocido por lo que proporciona: Cualquier entidad llamable puede ser convertida a una función std::de firma apropiada. Supongamos que tiene una biblioteca que ajusta una superficie a una función definida por z = f (x,y), puede escribirla para aceptar un std::function<double(double,double)>, y el usuario de la biblioteca puede fácilmente convierta cualquier entidad llamable a eso; ya sea una función ordinaria, un método de una instancia de clase, o una lambda, o cualquier cosa que sea compatible con std::bind.

A diferencia de los enfoques de plantilla, esto funciona sin tener que recompilar la función de biblioteca para diferentes casos; en consecuencia, se necesita poco código compilado adicional para cada caso adicional. Siempre ha sido posible hacer que esto suceda, pero solía requerir algunos mecanismos incómodos, y el usuario de la biblioteca probablemente necesitaría construya un adaptador alrededor de su función para que funcione. std:: function construye automáticamente cualquier adaptador necesario para obtener una interfaz de llamada runtime común para todos los casos, que es una característica nueva y muy poderosa.

En mi opinión, este es el caso de uso más importante para std:: function en lo que respecta al rendimiento: Estoy interesado en el costo de llamar a una std::function muchas veces después de que se ha construido una vez, y debe ser una situación en la que el compilador no puede optimizar la llamada sabiendo la función que realmente se llama (es decir, necesita ocultar la implementación en otro archivo fuente para obtener un punto de referencia adecuado).

Hice la prueba a continuación, similar a la de los OP; pero los principales cambios son:

1. Cada caso se repite 1 mil millones de veces, pero los objetos std::function se construyen solo una vez. He encontrado al mirar el código de salida que 'operator new' se llama al construir llamadas reales a std::function (tal vez no cuando se optimizan).
2. La prueba se divide en dos archivos para evitar la optimización no deseada
3. Mis casos son: (a) la función está inlineada (b) la función es pasada por un puntero de función ordinario (c) la función es una función compatible envuelta como std:: function (d) la función es una función incompatible hecha compatible con un std::bind, envuelta como std:: function{[19]]}

Los resultados que obtengo son:

• Caso a) (en línea) 1.3 nsec

• Todos los demás casos: 3,3 nsec.

El caso (d) tiende a ser ligeramente más lento, pero la diferencia (aproximadamente 0.05 nsec) se absorbe en el ruido.

La conclusión es que la función std::es comparable a la sobrecarga (en el momento de la llamada) al uso de un puntero de función, incluso cuando hay una simple adaptación 'bind' a la función real. El inline es 2 ns más rápido que los otros, pero eso es una compensación esperada ya que el inline es el único caso que está 'cableado' en tiempo de ejecución.

Cuando corro código de johan-lundberg en la misma máquina, estoy viendo alrededor de 39 nsec por bucle, pero hay mucho más en el bucle allí, incluyendo el constructor real y destructor de la función std::, que es probablemente bastante alto ya que implica un nuevo y eliminar.

- O2 gcc 4.8.1, al objetivo x86_64 (core i5).

Tenga en cuenta que el código se divide en dos archivos, para evitar que el compilador expanda las funciones donde se llaman (excepto en el caso en el que se pretende a).

----- primer archivo de origen --------------

#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 archivo de origen -------------

#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 aquellos interesados, aquí está el adaptador que el compilador construyó para hacer que 'mul_by' se vea como un float (float) - esto es 'llamado' cuando se llama a la función creada como bind(mul_by,_1,0.5):

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

(así que podría haber sido un poco más rápido si hubiera escrito 0.5 f en el enlace...) Tenga en cuenta que el parámetro 'x' llega en %xmm0 y simplemente permanece allí.

Aquí está el código en el área donde se construye la función, antes de llamar a test_stdfunc-run a través de 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)

Encontré sus resultados muy interesantes, así que hice un poco de investigación para entender lo que está pasando. En primer lugar, como muchos otros han dicho sin tener los resultados del efecto de cómputo el estado del programa el compilador solo optimizará esto. En segundo lugar, teniendo un constante 3.3 dado como armamento a la devolución de llamada, sospecho que habrá otras optimizaciones en curso. Con eso en mente he cambiado un poco tu código de benchmark.

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();
}

Dado este cambio en el código Compilé con gcc 4.8-O3 y obtuve un tiempo de 330ms para calc1 y 2702 para calc2. Así que el uso de la plantilla fue 8 veces más rápido, este número parecía sospechosos para mí, la velocidad de una potencia de 8 a menudo indica que el compilador ha vectorizado algo. cuando miré el código generado para la versión de plantillas, estaba claramente vectorizado

.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)

Donde como la versión de la función std::no lo era. Esto tiene sentido para mí, ya que con la plantilla el compilador sabe con seguridad que la función nunca cambiar a lo largo del bucle, pero con la función std::pasando en él podría cambiar, por lo tanto no puede ser vectorizado.

Esto me llevó a intentar otra cosa para ver si podía conseguir que el compilador realizara la misma optimización en la versión std::function. En lugar de pasar una función hago una función std::como una var global, y la llamo.

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();
}

Con esta versión vemos que el compilador ahora ha vectorizado el código de la misma manera y obtengo el mismo benchmark resultado.

• plantilla: 330ms
• std:: función: 2702ms
• std global:: función: 330ms

Así que mi conclusión es que la velocidad bruta de una función std::vs un funtor de plantilla es más o menos la misma. Sin embargo, hace que el trabajo del optimizador sea mucho más difícil.