¿Por qué este programa OCaml es más rápido que mi programa C?

Question

Escribí un programa básico Hippity Hop en C, Python y OCaml. De acuerdo, probablemente este no sea un punto de referencia muy bueno de estos tres idiomas. Pero los resultados que obtuve fueron algo como esto:

• Python: .350 segundos
• C: .050 segundos
• interpretados OCaml: .040 segundos
• OCaml compilado: 0.010

El rendimiento de Python en realidad no me sorprende, pero estoy bastante sorprendido de lo rápido que es el OCaml (especialmente la versión interpretada). Para comparar, publicaré la versión C y la versión OCaml.

C

#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 

long get_count(char *name); 

int main(int argc, char *argv[]) 
{ 
    if (argc != 2){ 
    printf("Filename must be specified as a positional argument.\n"); 
    exit(EXIT_FAILURE); 
    } 

    long count_no = get_count(argv[1]); 

    int i; 
    for (i = 1; i <= count_no; i++){ 
    if (((i % 3) == 0) && ((i % 5) == 0)){ 
     printf("Hop\n"); 
     continue; 
    } 
    if ((i % 3) == 0){ 
     printf("Hoppity\n"); 
    } 
    if ((i % 5) == 0){ 
     printf("Hophop\n"); 
    } 
    } 
    return 0; 
} 

long get_count(char *name){ 
    FILE *fileptr = fopen(name, "r"); 
    if (!fileptr){ 
    printf("Unable to open file %s.\n", name); 
    exit(EXIT_FAILURE); 
    } 
    size_t text_len = 20; 
    char *file_text = calloc(text_len, sizeof(char)); 
    while (!feof(fileptr)){ 
    fread(file_text, sizeof(char), text_len, fileptr); 
    assert(!ferror(fileptr)); 
    text_len += 20; 
    file_text = realloc(file_text, text_len * sizeof(char)); 
    } 
    long file_as_int = strtol(file_text, NULL, 10); 

    free(file_text); 
    return file_as_int; 
} 

OCaml

open String;; 

let trim str = 
    if str = "" then "" else 
    let search_pos init p next = 
    let rec search i = 
     if p i then raise(Failure "empty") else 
     match str.[i] with 
     | ' ' | '\n' | '\r' | '\t' -> search (next i) 
     | _ -> i 
    in 
    search init 
    in 
    let len = String.length str in 
    try 
    let left = search_pos 0 (fun i -> i >= len) (succ) 
    and right = search_pos (len - 1) (fun i -> i < 0) (pred) 
    in 
    String.sub str left (right - left + 1) 
    with 
    | Failure "empty" -> "" 
;; 

let rec iterate_over_numbers curr_num max_num = 
    (
    if curr_num <= max_num then (
    if ((curr_num mod 3) == 0) && ((curr_num mod 5) == 0) then 
     print_endline "Hop" 
    else if (curr_num mod 3) == 0 then 
     print_endline "Hoppity" 
    else if (curr_num mod 5) == 0 then 
     print_endline "Hophop"; 
    iterate_over_numbers (curr_num + 1) max_num 
    )) 
;; 


let fname = Sys.argv.(1);; 
let infile = open_in fname;; 
let file_text = trim (input_line infile);; 
close_in infile;; 
let input_number = int_of_string file_text;; 
iterate_over_numbers 1 input_number;; 

pero tengo curiosidad de saber por qué estoy recibiendo estos resultados. ¿Estoy haciendo algo estúpido en mi programa C, o es solo algo en lo que OCaml es más rápido? Me parece un poco extraño que un programa interpretado se ejecute un poco más rápido que la versión C, y el programa compilado se ejecuta 5 veces más rápido.

Answer 1

Su código C no es el equivalente del código OCaml - que utilizó 'else if' en el OCaml para evitar tener que volver a calcular los módulos tanto.

Hay un montón de código en 'leer el entero largo'. ¿Por qué no usar fscanf(); salta espacios en blanco y todo eso automáticamente, y evita que hagas el malloc() etc. No suelo recomendar el uso de fscanf(), pero parece una configuración para él, una sola línea, posiblemente con espacios en cada lado, nada gracioso.

---

La curiosidad mató al gato, pero en este caso, no al Leopard.

He descargado OCaml 3.11.1 para MacOS X Intel y copié el código OCaml de la pregunta en xxx.ml (OCaml), y compilé eso en un archivo de objeto xxx (usando "ocamlc -o xxx xxx.ml") ; Copié el código C textualmente en yyy.c y creé una variante zzz.c usando fscanf() y fclose(), y los compilé usando "gcc -O -o yyy yyy.c" y "gcc -O -o zzz zzz.c". Creé un archivo 'file3' que contiene: "987654" más una nueva línea. Creé un script de shell runthem.sh como se muestra. Tenga en cuenta que el 'tiempo' es un comando molesto que cree que su salida debe ir a stderr incluso cuando prefiera que no lo haga, tiene que trabajar bastante duro para obtener la salida donde quiere que vaya. (El comando gama genera números en el rango dado, inclusive -. Por lo tanto 11 valores por programa)

Osiris JL: cat runthem.sh 
for prog in "ocaml xxx.ml" ./xxx ./yyy ./zzz 
do 
    for iter in $(range 0 10) 
    do 
     r=$(sh -c "time $prog file3 >/dev/null" 2>&1) 
     echo $prog: $r 
    done 
done 
Osiris JL: 

me encontré con todo esto en un moderno MacBook Pro (3 GHz Core 2 Duo, etc, 4 GB de RAM) con Leopard (10.5.8). Los tiempos que obtuve se muestran por:

Osiris JL: sh runthem.sh 
ocaml xxx.ml: real 0m0.961s user 0m0.524s sys 0m0.432s 
ocaml xxx.ml: real 0m0.953s user 0m0.516s sys 0m0.430s 
ocaml xxx.ml: real 0m0.959s user 0m0.517s sys 0m0.431s 
ocaml xxx.ml: real 0m0.951s user 0m0.517s sys 0m0.430s 
ocaml xxx.ml: real 0m0.952s user 0m0.516s sys 0m0.431s 
ocaml xxx.ml: real 0m0.952s user 0m0.514s sys 0m0.431s 
ocaml xxx.ml: real 0m0.951s user 0m0.515s sys 0m0.431s 
ocaml xxx.ml: real 0m0.959s user 0m0.515s sys 0m0.431s 
ocaml xxx.ml: real 0m0.950s user 0m0.515s sys 0m0.431s 
ocaml xxx.ml: real 0m0.956s user 0m0.516s sys 0m0.431s 
ocaml xxx.ml: real 0m0.952s user 0m0.514s sys 0m0.432s 
./xxx: real 0m0.928s user 0m0.494s sys 0m0.430s 
./xxx: real 0m0.938s user 0m0.494s sys 0m0.430s 
./xxx: real 0m0.927s user 0m0.494s sys 0m0.430s 
./xxx: real 0m0.928s user 0m0.492s sys 0m0.430s 
./xxx: real 0m0.928s user 0m0.493s sys 0m0.430s 
./xxx: real 0m0.927s user 0m0.493s sys 0m0.430s 
./xxx: real 0m0.928s user 0m0.492s sys 0m0.430s 
./xxx: real 0m0.933s user 0m0.497s sys 0m0.428s 
./xxx: real 0m0.926s user 0m0.494s sys 0m0.429s 
./xxx: real 0m0.921s user 0m0.492s sys 0m0.428s 
./xxx: real 0m0.925s user 0m0.494s sys 0m0.428s 
./yyy: real 0m0.027s user 0m0.026s sys 0m0.001s 
./yyy: real 0m0.031s user 0m0.026s sys 0m0.002s 
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s 
./yyy: real 0m0.029s user 0m0.026s sys 0m0.002s 
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s 
./yyy: real 0m0.029s user 0m0.026s sys 0m0.002s 
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s 
./yyy: real 0m0.031s user 0m0.026s sys 0m0.002s 
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s 
./yyy: real 0m0.030s user 0m0.026s sys 0m0.002s 
./yyy: real 0m0.028s user 0m0.026s sys 0m0.001s 
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s 
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s 
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s 
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s 
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s 
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s 
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s 
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s 
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s 
./zzz: real 0m0.029s user 0m0.027s sys 0m0.001s 
./zzz: real 0m0.030s user 0m0.027s sys 0m0.002s 
Osiris JL: 

No veo el código OCaml ejecutándose más rápido que el código C. Corrí las pruebas con un número menor en el archivo que se leen, y los resultados fueron de manera similar a favor del código C:

número Stop: 345

ocaml xxx.ml: real 0m0.027s user 0m0.020s sys 0m0.005s 
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.005s 
ocaml xxx.ml: real 0m0.025s user 0m0.016s sys 0m0.004s 
ocaml xxx.ml: real 0m0.020s user 0m0.015s sys 0m0.003s 
ocaml xxx.ml: real 0m0.022s user 0m0.016s sys 0m0.004s 
ocaml xxx.ml: real 0m0.019s user 0m0.015s sys 0m0.003s 
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.004s 
ocaml xxx.ml: real 0m0.020s user 0m0.015s sys 0m0.004s 
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.004s 
ocaml xxx.ml: real 0m0.020s user 0m0.015s sys 0m0.004s 
ocaml xxx.ml: real 0m0.021s user 0m0.016s sys 0m0.004s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.002s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s 
./xxx: real 0m0.002s user 0m0.001s sys 0m0.001s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s 
./xxx: real 0m0.005s user 0m0.001s sys 0m0.002s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.002s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s 
./xxx: real 0m0.003s user 0m0.001s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.003s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.001s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.002s user 0m0.000s sys 0m0.001s 
./yyy: real 0m0.003s user 0m0.000s sys 0m0.002s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.001s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.003s user 0m0.000s sys 0m0.002s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 
./zzz: real 0m0.002s user 0m0.000s sys 0m0.001s 

número de parada: 87654

ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.041s 
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.040s 
ocaml xxx.ml: real 0m0.101s user 0m0.060s sys 0m0.040s 
ocaml xxx.ml: real 0m0.103s user 0m0.059s sys 0m0.041s 
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.041s 
ocaml xxx.ml: real 0m0.101s user 0m0.059s sys 0m0.041s 
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.040s 
ocaml xxx.ml: real 0m0.103s user 0m0.059s sys 0m0.040s 
ocaml xxx.ml: real 0m0.101s user 0m0.059s sys 0m0.040s 
ocaml xxx.ml: real 0m0.102s user 0m0.059s sys 0m0.040s 
ocaml xxx.ml: real 0m0.105s user 0m0.059s sys 0m0.041s 
./xxx: real 0m0.092s user 0m0.044s sys 0m0.038s 
./xxx: real 0m0.087s user 0m0.044s sys 0m0.039s 
./xxx: real 0m0.085s user 0m0.044s sys 0m0.038s 
./xxx: real 0m0.084s user 0m0.044s sys 0m0.038s 
./xxx: real 0m0.085s user 0m0.044s sys 0m0.039s 
./xxx: real 0m0.086s user 0m0.045s sys 0m0.039s 
./xxx: real 0m0.085s user 0m0.044s sys 0m0.039s 
./xxx: real 0m0.085s user 0m0.044s sys 0m0.038s 
./xxx: real 0m0.084s user 0m0.044s sys 0m0.038s 
./xxx: real 0m0.084s user 0m0.044s sys 0m0.039s 
./xxx: real 0m0.083s user 0m0.044s sys 0m0.038s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.005s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.005s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.004s user 0m0.003s sys 0m0.001s 
./yyy: real 0m0.006s user 0m0.003s sys 0m0.002s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.005s user 0m0.003s sys 0m0.002s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.004s user 0m0.003s sys 0m0.001s 
./zzz: real 0m0.005s user 0m0.003s sys 0m0.001s 

Obviamente, YMMV - pero parece que OCaml es más lento que C por un margen considerable, pero que si el número en el archivo dado es lo suficientemente pequeño, entonces el inicio y la lectura del archivo dominan el tiempo del proceso.

Las temporizaciones C, especialmente en los números más pequeños, son tan rápidas que no son tan confiables.

Answer 2

El tiempo por debajo de 0.05 puede ser un ruido simple. Repita el programa principal suficientes veces para obtener ~ 1s de tiempo de ejecución en C. (Me refiero a repetirlo en un bucle en el programa mismo, no volviéndolo a ejecutar)

¿Compiló su código con las optimizaciones activadas? ¿Intentó reducir el número de ramas? (y comparaciones)

if (i % 3 == 0) { 
    if (i % 5 == 0) { 
    printf("Hop\n"); 
    continue; 
    } 
    printf("Hoppity\n"); 
} else if (i % 5 == 0){ 
    printf("Hophop\n"); 
} 

¿Intentabas mirar la salida del ensamblador?

También printf es bastante lento. Pruebe puts("Hop"), ya que no usa el formateo de todos modos.

Answer 3

Me gustaría ver cuánto tiempo se gasta en get_count().

No estoy seguro de cuánto importaría, pero está leyendo en un largo como una cadena, lo que significa que la cadena no puede ser mayor de 20 bytes, o 10 bytes (2^64 = unos 20 caracteres de largo número decimal, o 2^32 = un número decimal largo de 10 caracteres), por lo que no necesita su ciclo while en get_count. Además, podría asignar file_text a la pila, en lugar de llamar a calloc, pero supongo que aún tendría que ponerlo a cero o, de lo contrario, encontrar la longitud y establecer el último byte en nulo.

file_length = lseek(fileptr, 0, SEEK_END); 

Answer 4

Cualquier programa que principalmente implique abrir un archivo y leerlo está limitado por la velocidad de abrir un archivo y leerlo. Los cálculos C que está haciendo aquí tomarán entre 1 millonésima y una milésima del tiempo de apertura del archivo y su lectura.

pensé que este sitio fue útil: http://norvig.com/21-days.html#answers

Answer 5

En un pequeño programa como este, a menudo es difícil adivinar por qué las cosas funcionan de la manera en que lo hacen. Creo que si lo hacía, me gustaría escribir el código como este (dejando de lado la comprobación de errores por el momento):

#include <stdio.h> 
#include <stdlib.h> 

int main(int argc, char **argv) { 
    static char buffer[20]; 
    int limit, i; 

    freopen(argv[1], "r", stdin); 
fgets(buffer, sizeof(buffer), stdin); 
    limit = atoi(buffer); 

    for (i=1; i<=limit; i++) { 
     int div3=i%3==0; 
     int div5=i%5==0; 
     if (div3 && div5) 
      puts("Hop"); 
     else if (div3) 
      puts("Hoppity"); 
     else if (div5) 
      puts("HopHop"); 
    } 
    return 0; 
} 

Usando freopen evita la creación de otra secuencia de archivo, y en su lugar sólo se conecta la entrada estándar a la especificada archivo. No hay garantía de que sea más rápido, pero es poco probable que sea más lento de todos modos.

Del mismo modo, un buen compilador puede observar que i es constante en todo el cuerpo del bucle, y restar importancia a las dos operaciones restantes por lo que solo hace una vez. Aquí lo he hecho a mano, lo que podría no ser más rápido, pero casi seguro que no será más lento.

El uso de puts en lugar de printf es bastante similar, puede que no sea más rápido, pero con certeza no será más lento.Usando printf de la manera que usted tiene, tiene que escanear toda la cadena buscando un '%', en caso de que esté pidiendo una conversión, pero dado que puts no realiza ninguna conversión, no tiene que hacer eso .

Con un programa tan pequeño como este, hay otro factor que podría ser considerablemente más significativo: puts generalmente será considerablemente más pequeño que printf. No ha dicho cómo está haciendo el cronometraje, pero si incluye el tiempo para cargar el código, un código realmente pequeño puede hacer más diferencia que el tiempo de ejecución.