rendimiento de la pila en lenguajes de programación

Question

Sólo por diversión, me trató de comparar el rendimiento de la pila un par de lenguajes de programación cálculo de la serie de Fibonacci utilizando el algoritmo recursivo ingenuo. El código es fundamentalmente el mismo en todos los idiomas, voy a publicar una versión de Java:

public class Fib { 
public static int fib(int n) { 
    if (n < 2) return 1; 
    return fib(n-1) + fib(n-2); 
} 

public static void main(String[] args) { 
    System.out.println(fib(Integer.valueOf(args[0]))); 
} 
} 

Ok por lo que el punto es que el uso de este algoritmo con la entrada 40 Tengo estos tiempos:

C: 2.796s 
Ocaml: 2.372s 
Python: 106.407s 
Java: 1.336s 
C#(mono): 2.956s 

Ellos se toman en una caja de Ubuntu 10.04 usando las versiones de cada idioma disponible en los repositorios oficiales, en una máquina Intel de doble núcleo.

Sé que los lenguajes funcionales como ocaml tienen la desaceleración que proviene de tratar las funciones como ciudadanos de primer orden y no tienen ningún problema para explicar el tiempo de ejecución de CPython porque es el único lenguaje interpretado en esta prueba, pero quedé impresionado por el tiempo de ejecución de Java, que es la mitad de la c para el mismo algoritmo! ¿Lo atribuirías a la compilación de JIT?

¿Cómo explicarías estos resultados?

EDIT: gracias por las respuestas interesantes! Reconozco que este no es un punto de referencia adecuado (nunca dije que fuera: P) y tal vez puedo hacer uno mejor y postearlo la próxima vez, a la luz de lo que hemos discutido :)

EDITAR 2 : Actualicé el tiempo de ejecución de la implementación de ocaml, utilizando el optimizador compilador ocamlopt. También publiqué el banco de pruebas en https://github.com/hoheinzollern/fib-test. Siéntase libre de hacer adiciones si lo desea :)

Answer 1

Una posibilidad es que el compilador de C se está optimizando en la suposición de que la primera rama (n < 2) es la más frecuente. Tiene que hacer eso puramente en tiempo de compilación: adivinar y aferrarse a él.

El punto de acceso público ejecuta el código, vea qué realmente ocurre con más frecuencia, y vuelve a optimizar según esos datos.

Usted puede podrá ver una diferencia invirtiendo la lógica de la if:

public static int fib(int n) { 
if (n >= 2) return fib(n-1) + fib(n-2); 
return 1; 
} 

Vale la pena intentarlo, de todos modos :)

Como siempre, compruebe los ajustes de optimización para todos plataformas, también. Obviamente, la configuración del compilador para C - y en Java, intente utilizar la versión cliente de Hotspot vs la versión del servidor. (Tenga en cuenta que necesita para funcionar durante más de un segundo o más para conseguir realmente el beneficio completo de hotspot ... que podría ser interesante para poner la llamada externa en un bucle para obtener carreras de un minuto o así.)

Answer 2

Usted dice muy poco acerca de la configuración (en la evaluación comparativa, los detalles lo son todo: líneas de comando, equipo utilizado, ...)

cuando trato de reproducir para OCaml me sale:

let rec f n = if n < 2 then 1 else (f (n-1)) + (f (n-2)) 

let() = Format.printf "%d@." (f 40) 


$ ocamlopt fib.ml 
$ time ./a.out 
165580141 

real 0m1.643s 

Esto está en una Intel Xeon 5150 (Core 2) a 2,66 GHz. Si utilizo el compilador bytecode OCaml ocamlc por otro lado, obtengo un tiempo similar al resultado (11s).Pero, por supuesto, para ejecutar una comparación de velocidad, no hay ninguna razón para usar el compilador de códigos de bytes, a menos que desee comparar la velocidad de la compilación en sí (ocamlc es increíble para la velocidad de compilación).

Answer 3

Es posible que desee aumentar el nivel de optimización de su compilador de C. Con gcc -O3, eso hace una gran diferencia, una caída de 2.015 segundos a 0.766 segundos, una reducción de aproximadamente el 62%.

Más allá de eso, debe asegurarse de haber probado correctamente. Debe ejecutar cada programa diez veces, eliminar los valores atípicos (más rápido y más lento) y luego promediar los otros ocho.

Además, asegúrese de estar midiendo el tiempo de CPU en lugar de la hora del reloj.

Cualquier cosa menos que eso, no consideraría un análisis estadístico decente y podría estar sujeto a ruido, haciendo que sus resultados sean inútiles.

Por lo que vale la pena, esos tiempos de C anteriores fueron para siete carreras con los valores atípicos que se tomaron antes de promediar.

---

De hecho, esta pregunta muestra la importancia de la selección de algoritmos cuando se busca un alto rendimiento. Aunque las soluciones recursivas suelen ser elegantes, esta falla por la duplicación de un lote de cálculos. La versión iterativo:

int fib(unsigned int n) { 
    int t, a, b; 
    if (n < 2) return 1; 
    a = b = 1; 
    while (n-- >= 2) { 
     t = a + b; 
     a = b; 
     b = t; 
    } 
    return b; 
} 

cae aún más el tiempo tomado, de 0,766 segundos a 0.078 segundos, una reducción adicional del 89% y una reducción friolera de 96% a partir del código original.

---

Y, como un último intento, usted debe probar lo siguiente, que combina una tabla de consulta con los cálculos más allá de un cierto punto:

static int fib(unsigned int n) { 
    static int lookup[] = { 
     1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 
     610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 
     46368, 75025, 121393, 196418, 317811, 514229, 832040, 
     1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 
     24157817, 39088169, 63245986, 102334155, 165580141 }; 
    int t, a, b; 

    if (n < sizeof(lookup)/sizeof(*lookup)) 
     return lookup[n]; 
    a = lookup[sizeof(lookup)/sizeof(*lookup)-2]; 
    b = lookup[sizeof(lookup)/sizeof(*lookup)-1]; 
    while (n-- >= sizeof(lookup)/sizeof(*lookup)) { 
     t = a + b; 
     a = b; 
     b = t; 
    } 

    return b; 
} 

que reduce el tiempo una vez más, pero sospecho que Estamos llegando al punto de rendimientos decrecientes aquí.

Answer 4

Tenga en cuenta que si la máquina virtual Java Hotspot es lo suficientemente inteligente como para memorizar llamadas fib(), puede reducir el costo exponencional del algoritmo a algo más cercano al costo lineal.

Answer 5

Puedo explicar el rendimiento de Python. El rendimiento de Python para la recursión es pésimo en el mejor de los casos, y se debe evitar como la peste cuando se codifica. Especialmente dado que el desbordamiento de pila ocurre por defecto a una profundidad de recursión de solo 1000 ...

En cuanto al rendimiento de Java, eso es increíble. Es raro que Java supere a C (incluso con muy poca optimización del compilador en el lado C) ... lo que el JIT podría estar haciendo es la memoria o la recursión de cola ...

Answer 6

Con C, debe declarar la función de fibonacci " en línea ", o, usando gcc, agregue el argumento -finline-functions a las opciones de compilación. Eso permitirá que el compilador realice recursivas en línea. Esa es también la razón por la que con -O3 obtienes un mejor rendimiento, activa -finline-functions.

Editar Debe especificar al menos -O/-O1 para tener recursivo enlining, también si la función se declara en línea.En realidad, al ponerme a prueba descubrí que al declarar la función en línea y usando -O como indicador de compilación, o simplemente usando -O -finline-functions, mi código recursivo de Fibonacci era más rápido que con -O2 o -O2 -finline-functions.

Answer 7

Escribí una versión C de la función ingenua de Fibonacci y la compilé para ensamblar en gcc (4.3.2 Linux). Luego lo compilé con gcc -O3.

La versión no optimizada tenía 34 líneas de largo y parecía una traducción directa del código C.

La versión optimizada fue de 190 líneas de largo y (era difícil decir pero) apareció a inline al menos las llamadas para valores de hasta aproximadamente 5.

Answer 8

Uno C truco que se puede probar es desactivar el comprobación de pila (es decir, código incorporado que asegura que la pila sea lo suficientemente grande como para permitir la asignación adicional de las variables locales de la función actual). Esto podría ser arriesgado para una función recursiva y de hecho podría ser la razón detrás de los tiempos C lentos: el programa de ejecución podría haberse quedado sin espacio de pila que obliga a la comprobación de la pila a reasignar la pila entera varias veces durante la ejecución real.

Intente aproximar el tamaño de pila que necesita y fuerce al vinculador a asignar ese espacio de pila. Luego deshabilite la verificación de pila y vuelva a hacer el programa.