std :: function vs template

Gracias a C ++ 11 recibimos la std::functionfamilia de envoltorios de functor. Desafortunadamente, sigo escuchando solo cosas malas sobre estas nuevas incorporaciones. Lo más popular es que son horriblemente lentos. Lo probé y realmente apestan en comparación con las plantillas.

#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 frente a 1241 ms. Supongo que esto se debe a que las plantillas pueden estar bien alineadas, mientras que functionlas internas se cubren mediante llamadas virtuales.

Obviamente, las plantillas tienen sus problemas tal como los veo:

• deben proporcionarse como encabezados, lo cual no es algo que quizás no desee hacer al lanzar su biblioteca como código cerrado,
• pueden hacer que el tiempo de compilación sea mucho más largo a menos extern templateque se introduzca una política similar,
• no hay una forma limpia (al menos conocida por mí) de representar los requisitos (conceptos, ¿alguien?) de una plantilla, sin incluir un comentario que describa qué tipo de functor se espera.

¿Puedo suponer que functions se puede usar como estándar de facto de los pasadores, y en lugares donde se espera que se usen plantillas de alto rendimiento?

Editar:

Mi compilador es Visual Studio 2012 sin CTP.

En general, si se enfrenta a una situación de diseño que le permite elegir, utilice plantillas . Hice hincapié en la palabra diseño porque creo que lo que debe centrarse es la distinción entre los casos de uso std::functiony las plantillas, que son bastante diferentes.

En general, la elección de plantillas es solo una instancia de un principio más amplio: intente especificar tantas restricciones como sea posible en tiempo de compilación . La razón es simple: si puede detectar un error o una falta de coincidencia de tipos, incluso antes de que se genere su programa, no enviará un programa defectuoso a su cliente.

Además, como señaló correctamente, las llamadas a las funciones de plantilla se resuelven estáticamente (es decir, en tiempo de compilación), por lo que el compilador tiene toda la información necesaria para optimizar y posiblemente alinear el código (lo que no sería posible si la llamada se realizara a través de un vtable).

Sí, es cierto que el soporte de plantillas no es perfecto, y C ++ 11 todavía carece de soporte para conceptos; Sin embargo, no veo cómo std::functionpodría salvarte a ese respecto. std::functionno es una alternativa a las plantillas, sino más bien una herramienta para situaciones de diseño donde las plantillas no se pueden usar.

Uno de estos casos de uso surge cuando necesita resolver una llamada en tiempo de ejecución invocando un objeto invocable que se adhiere a una firma específica, pero cuyo tipo concreto es desconocido en tiempo de compilación. Este suele ser el caso cuando tiene una colección de devoluciones de llamada de tipos potencialmente diferentes , pero que necesita invocar de manera uniforme ; El tipo y el número de las devoluciones de llamada registradas se determinan en tiempo de ejecución en función del estado de su programa y la lógica de la aplicación. Algunas de esas devoluciones de llamada podrían ser functores, algunas podrían ser funciones simples, otras podrían ser el resultado de vincular otras funciones a ciertos argumentos.

std::functiony std::bindtambién ofrecen un lenguaje natural para habilitar la programación funcional en C ++, donde las funciones se tratan como objetos y se combinan y se combinan naturalmente para generar otras funciones. Aunque este tipo de combinación también se puede lograr con plantillas, una situación de diseño similar normalmente se combina con casos de uso que requieren determinar el tipo de los objetos invocables combinados en tiempo de ejecución.

Finalmente, hay otras situaciones en las que std::functiones inevitable, por ejemplo, si desea escribir lambdas recursivas ; sin embargo, estas restricciones están más dictadas por limitaciones tecnológicas que por distinciones conceptuales, creo.

En resumen, concéntrese en el diseño e intente comprender cuáles son los casos de uso conceptual para estos dos constructos. Si los comparas de la manera en que lo hiciste, los estás forzando a una arena a la que probablemente no pertenecen.

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 std::function.

En primer lugar, una observación rápida sobre la técnica de medición: los 11 ms obtenidos calc1no tienen ningún significado. De hecho, al observar el ensamblaje generado (o depurar el código de ensamblaje), se puede ver que el optimizador de VS2012 es lo suficientemente inteligente como para darse cuenta de que el resultado de la llamada calc1es independiente de la iteración y saca la llamada del bucle:

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

Además, se da cuenta de que las llamadas calc1no tienen un efecto visible y las abandona por completo. Por lo tanto, los 111 ms es el tiempo que tarda el ciclo 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 parece.

Como se ha señalado, el optimizador tiene más problemas para comprender std::functiony no mueve la llamada fuera del bucle. Entonces 1241ms es una medida justa para calc2.

Tenga en cuenta que std::functionpuede almacenar diferentes tipos de objetos invocables. Por lo tanto, debe realizar alguna magia de borrado de tipo para el almacenamiento. En general, 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) codifica implementaciones para evitar la asignación de memoria dinámica para objetos pequeños que, afortunadamente, VS2012 (en particular, para el código original).

Para tener una idea de cuánto más lento puede ser cuando la asignación de memoria está involucrada, he cambiado la expresión lambda para capturar tres floats. Esto hace que el objeto invocable 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 16000 ms (en comparación con 1241 ms para el código original).

Finalmente, observe que la vida útil de la lambda encierra la de la std::function. En este caso, en lugar de almacenar una copia de la lambda, std::functionpodría almacenar una "referencia" a ella. Por "referencia" me refiero a un std::reference_wrapperque se construye fácilmente por funciones std::refy 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 1860 ms.

Escribí sobre eso hace un tiempo:

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 escaso soporte para C ++ 11. En el momento de la redacción de este documento, solo estaba disponible una versión beta de VS2012, pero su compatibilidad con C ++ 11 ya era lo suficientemente buena 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 realmente idénticos .

-Vuelvo a sonar al final del post. Pero primero, gcc 4.7.2:

Ya hay mucha información en curso, pero quiero señalar que el resultado de los cálculos de calc1 y calc2 no es el mismo, debido al revestimiento, etc. Compare, por ejemplo, la suma de todos los resultados:

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

con calc2 que se convierte

1.71799e+10, time spent 0.14 sec

mientras que con calc1 se convierte

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. El primero es una diferencia mucho más grande que lo que OP publicó (usando Visual Studio). En realidad, imprimir el valor al final también es una buena idea para evitar que el compilador elimine el código sin un resultado visible (como regla if). Cassio Neri ya dijo esto en su respuesta. Tenga en cuenta cuán diferentes 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 debería estar en un bucle. (Es fácil que el optimizador lo note)

Si agrego un argumento de valor proporcionado 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 es cercana a un factor de 2, y con el sonido metálico no hay diferencia (ver más abajo).

Además, como las multiplicaciones son rápidas, hablar de factores de desaceleració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?

Sonido metálico:

Clang (usé 3.2) en realidad produjo binarios idénticos cuando cambio 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 tardan en absoluto (los bucles se eliminan por completo como se describe 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 archivos binarios son los mismos, y todas las pruebas se ejecutaron en la misma máquina. Sería interesante si alguien con un sonido más profundo de claxon o VS pudiera comentar qué optimizaciones pueden haberse realizado.

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

Actualizar:

Añadido vs2015. También noté que hay conversiones de flotación doble-> en calc1, calc2. Eliminarlos no cambia la conclusión para Visual Studio (ambos son mucho más rápidos pero la proporción es casi 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 mismo objeto de función fun, se pasa a ambas llamadas a eval. Tiene dos funciones diferentes .

Si no necesita hacer eso, entonces debería no utilizar std::function.

Ya tiene algunas buenas respuestas aquí, por lo que no voy a contradecirlas, en resumen, comparar std :: function con plantillas es como comparar funciones virtuales con funciones. Nunca debe "preferir" las funciones virtuales a las 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), utilice algo que le brinde al compilador una mejor oportunidad de optimizarlo. También ayuda a otros programadores, si usa una solución estándar.

Esta respuesta está destinada a 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 std :: function.

El mecanismo std :: function debe reconocerse por lo que proporciona: cualquier entidad invocable puede convertirse en una función std :: de firma apropiada. Suponga que tiene una biblioteca que ajusta una superficie a una función definida por z = f (x, y), puede escribirla para aceptar a std::function<double(double,double)>, y el usuario de la biblioteca puede convertir fácilmente cualquier entidad invocable; 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 volver a compilar 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 construir un adaptador alrededor de su función para que funcione. std :: function construye automáticamente cualquier adaptador que sea necesario para obtener una interfaz de llamada de tiempo de ejecución 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 std :: function muchas veces después de que se haya construido una vez, y necesita puede ser una situación en la que el compilador no puede optimizar la llamada al conocer la función que realmente se llama (es decir, debe ocultar la implementación en otro archivo fuente para obtener un punto de referencia adecuado).

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

1. Cada caso se repite mil millones de veces, pero los objetos std :: function se construyen solo una vez. Al observar el código de salida, descubrí que se llama 'operador nuevo' al construir llamadas std :: function reales (tal vez no cuando están optimizadas).
2. La prueba se divide en dos archivos para evitar la optimización no deseada
3. Mis casos son: (a) la función está en línea (b) la función pasa 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 compatible con std :: enlazar, envuelto como std :: function

Los resultados que obtengo son:

• caso (a) (en línea) 1.3 nseg

• todos los demás casos: 3,3 nseg.

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

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

Cuando ejecuto el código de johan-lundberg en la misma máquina, veo unos 39 nseg por ciclo, pero hay mucho más en el ciclo allí, incluido el constructor y destructor real de la función std ::, que probablemente sea bastante alto ya que implica un nuevo y eliminar.

-O2 gcc 4.8.1, a x86_64 objetivo (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 que está destinado).

----- primer archivo fuente --------------

#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 fuente -------------

#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' parezca un flotador (float): esto se 'llama' 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

(por lo que podría haber sido un poco más rápido si hubiera escrito 0.5f 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: ejecute 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)

Sus resultados me parecieron muy interesantes, así que investigué un poco para comprender lo que está sucediendo. En primer lugar, como muchos otros han dicho, sin tener los resultados del efecto de cálculo, el estado del programa, el compilador simplemente optimizará esto. En segundo lugar, teniendo un 3.3 constante dado como armamento para la devolución de llamada, sospecho que habrá otras optimizaciones en curso. Con eso en mente, cambié un poco su código de referencia.

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 330 ms para calc1 y 2702 para calc2. Entonces, usar la plantilla fue 8 veces más rápido, este número me pareció sospechoso, 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 las 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 std :: function no era. Esto tiene sentido para mí, ya que con la plantilla el compilador sabe con certeza que la función nunca cambiará a lo largo del ciclo, pero con la función std :: que se pasa podría cambiar, por lo tanto no se puede vectorizar.

Esto me llevó a probar algo más para ver si podía hacer 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 var global, y hago que se llame.

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 los mismos resultados de referencia.

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

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