Dev Faq
12
votes

Pourquoi ce programme OCAML est-il plus rapide que mon programme C?

J'ai écrit une base Programme Hippity Hop en C, Python, et ocaml. Certes, ce n'est probablement pas une très bonne référence de ces trois langues. Mais les résultats que j'ai eu étaient quelque chose comme ça:

  • Python: .350 secondes li>
  • C: .050 secondes li>
  • interprété em> ocaml: .040 secondes li>
  • compilé OCAML: .010 LI> ul>

    La performance Python ne me surprend pas vraiment, mais je suis plutôt choqué de la rapidité avec laquelle l'OCAML est (surtout la version interprétée). Pour la comparaison, je posterai la version C et la version OCAML. P>

    C H1> 
    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;;

8 commentaires

Quels commutateurs compilateurs avez-vous utilisés pour la version C?

@Jonathan - Je viens de faire un gcc -o hoppity main.c . Je n'ai pas pensé à définir un niveau d'optimisation pour être honnête. :-)

Quel était le numéro dans le fichier lorsque le test a été exécuté? Et la sortie était-elle redirigée vers un fichier ou un tuyau de la même manière pour tous les tests? Et il serait intéressant de connaître les performances relatives avec «GCC» et «GCC -O».

En outre, FWIW, vous allumez un fichier ouvert en n'utilisant pas 'FCLose ()' dans la fonction où vous utilisez 'fopen ()'. La fixation qui ralentira les choses, bien sûr, mais ce que vous ouvrez, vous devriez fermer; Ce que vous allouez, vous devriez vous libérer.

C'est (probablement) pas vraiment lié à votre question, mais tandis que (! Feof (FilePtr)) { est à peu près un bug garantie.

Notez qu'il s'agit d'une variante mineure sur le problème de Fizzbuzz: Stackoverflow.com/Questtions/437/... . Cependant, ce n'est pas un duplicata - cette question pose des questions sur les timings; L'autre demande des implémentations.

@Jonathan - Je verrai combien de questions je peux répondre. La sortie vient d'être imprimée sur stdout. Je n'ai pas redirecté ça. Et la performance que j'ai obtenue lorsque vous allumez des optimisations était approximativement comparable à la performance OCAML. Et merci d'avoir souligné que j'ai oublié de fonger le fichier ouvert. Cela fait-il une différence depuis la fin du programme?

@Jerry - j'ai commencé une question distincte pour ce point: Stackoverflow.com/questions/1588336/whay-is-Chis-c-code-a-bug

5 Réponses :

9
votes

Le temps inférieur à 0,05 peut être un bruit simple. Répétez le programme principal suffisamment de temps pour obtenir ~ 1s d'heure d'exécution dans C. (Je veux dire le répéter dans une boucle dans le programme lui-même, pas en le gérant)

Avez-vous compilé votre code avec optimisations allumées? Avez-vous essayé de réduire le nombre de succursales? (et comparaisons) xxx

Avez-vous essayé de regarder la sortie de l'assembleur?

aussi printf est assez lent. Essayez met ("hop") à la place, puisque vous n'utilisez pas le formating de toute façon.

6 commentaires

C'est possible, mais vous devrez le tester. Le temps que vous économisez sur tous les 15'th essayer (vous faites seulement 1 chèque) peut ne pas équilibrer le temps que vous perdez sur les chiffres qui font 3 chèques. Seuls les tests peuvent dire que :) (a commenté une suggestion à vérifier I% 15, i% 3, i% 5 - Il a été supprimé plus tard)

Oui, je l'ai supprimé à cause d'une faute de frappe dans le code, puis de la réaliser qu'elle ne serait probablement pas plus efficace, alors je l'ai maintenue supprimée.

Jusqu'à présent, il semble être un lot plus rapide si je tourne le niveau d'optimisation vers le haut.

+1, sauf si l'utilisation d'un sous-système de printf () très basique () à partir d'une bibliothèque de régime, PrintF () ralentit vraiment les choses, en particulier avec le confort de la créature Glibc.

Vous n'avez pas besoin de «continuer» si vous utilisez un «autre» pour imprimer «Hoppity».

@Jonathan - Il est difficile de savoir ce qui serait plus "efficace" mais je pense que votre version est certainement plus lisible.

1
votes

Je serais intéressé de voir combien de temps est dépensé dans get_count ().

Je ne suis pas sûr de combien cela importerait, mais vous lisez dans une chaîne longue, ce qui signifie que la chaîne ne peut pas Soyez plus grand que 20 octets, ou 10 octets (2 ^ 64 = environ 20 caractères long-décimal long, ou 2 ^ 32 = environ 10 caractères long nombre décimal), de sorte que vous n'avez pas besoin de votre boucle de votre temps dans Get_Count. De plus, vous pourriez attribuer fichier_text sur la pile, plutôt que d'appeler calloc - mais je suppose que vous auriez toujours besoin de zéro de la moitié, ou de trouver la longueur et de définir le dernier octet sur NULL. P> 

file_length = lseek(fileptr, 0, SEEK_END);

2 commentaires

Point intéressant. Je suppose que la mémoire réaffectante encore et encore une fois serait assez inefficace. Je suppose que j'ai juste besoin de me familiariser avec le profileur C. :-)

Utilisation de la suggestion de FSCANF de Jonathan ci-dessus à une variable locale, cela ne ressemble pas à cela fait une énorme différence.

1
votes

Tout programme implique principalement d'ouvrir un fichier et de la lecture est limité par la vitesse d'ouverture d'un fichier et de la lire. Les calculs C que vous effectuez ici prendront entre 1 millionième et un millième du moment d'ouvrir le fichier et de le lire.

Je pensais que ce site était utile: http://norvig.com/21-days. HTML # répond

3 commentaires

Si cela était vrai, il n'y aurait pas une telle divergence entre C et OCAML (car les deux sont liés par le disque IO). L'OP a indiqué que le code C a été beaucoup plus rapide lorsqu'il a transformé le niveau d'optimisation, alors je soupçonne que cela peut être le problème.

Mais le temps nécessaire pour accéder à un fichier est complètement aléatoire. Si le fichier est toujours mis en cache, cela prendra beaucoup moins de temps que si le programme commence à froid. S'il dirige l'OCAML d'abord et le C secondé, le C va probablement gagner. S'il exécute le programme C sur et plus d'un million de fois, le temps moyen tombera de manière très significative.

@Kinopiko - Je les exécute en fait contre des doublons du même fichier.

9
votes

Votre code C n'est pas l'équivalent du code OCAML - vous avez utilisé «sinon si» dans l'OCAML pour éviter de devoir recalculer beaucoup de moduli.

Il y a un énorme de code dans ce que "lue la longue entier'. Pourquoi pas simplement utiliser fscanf () code>; Il saute des blancs et tout cela automatiquement, et vous évite de faire le Malloc () code> etc. Je ne recommande pas souvent d'utiliser FSCANF () code>, mais cela ressemble à une configuration pour C'est - une seule ligne, éventuellement avec des espaces de chaque côté, pas de choses drôles. p>

curiosité a tué le chat - mais dans ce cas, pas le léopard. P>

J'ai téléchargé OCAML 3.11.1 Pour MacOS X Intel et copié le code OCAML de la question dans xxx.ml (OCAML) et compilé cela dans un fichier d'objet xxx (utilisant "OCAMLC -O XXX.ML"); J'ai copié le code C code Verbatim en yyy.c et j'ai créé une variante ZZZ.co à l'aide de FSCANF () code> et FCLOSE () CODE> et les compilait à l'aide de "GCC -O -O yyy yyy.c "et" gcc -o -o zzz zzz.c ". J'ai créé un fichier 'File3' contenant: " 987654 code>" plus une nouvelle ligne. J'ai créé un script shell runthem.sh comme indiqué. Notez que «l'heure» est une commande pesky qui pense que sa sortie doit aller à StDerr même lorsque vous préférez que cela ne vous plaise pas - vous devez travailler assez fort pour obtenir la sortie où vous le souhaitez. (La commande de la plage génère des nombres dans la plage donnée, y compris - donc 11 valeurs par programme.) P> 

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

2 commentaires

FYI, aucun de ces ne semble avoir fait une énorme différence de performance. Bien que l'utilisation de FSCANF rend le code beaucoup plus lisible!

Intéressant: comme j'ai demandé dans les commentaires à la question principale - quelle était la taille du nombre que vous avez reçu? Et que se passe-t-il si vous iTERE N Times (où N est un nombre suffisant pour obtenir le programme le plus rapide de prendre un temps de l'ordre de secondes)? N'oubliez pas que vous aurez besoin de fermer le fichier si vous faites 10 000 itérations.

2
votes

Dans un petit programme comme celui-ci, il est souvent difficile de deviner pourquoi les choses fonctionnent comme elles le font. Je pense que si je le faisais, j'écrirais le code comme celui-ci (abandonner la vérification des erreurs pour le moment): xxx

à l'aide de freopen évite de créer un autre fichier Stream, et plutôt connecter simplement l'entrée standard dans le fichier spécifié. Aucune garantie que c'est plus rapide, mais il est peu probable d'être plus lent de toute façon.

De même, un bon compilateur peut noter que i est constant dans tout le corps de la boucle et factiperez les deux des opérations de reste pour que cela ne fait que chacun une fois. Ici, je l'ai fait à la main, ce qui pourrait ne pas être plus rapide, mais presque certainement ne sera certainement pas plus lent.

en utilisant met au lieu de printf est assez similaire - il pourrait ne pas être plus rapide, mais il ne sera presque certainement pas plus lent. En utilisant printf de la manière dont vous disposez, il doit analyser la chaîne entière à la recherche d'un "%", au cas où vous demandez une conversion, mais depuis met 't faire des conversions, il n'a pas à faire cela.

avec un tel programme tel que cela, il existe un autre facteur qui pourrait être considérablement plus important: met sera généralement être considérablement plus petit que printf . Vous n'avez pas dit comment vous faites le chronométrage, mais s'il inclut le temps nécessaire pour charger le code, un code vraiment petit peut bien faire plus de différence que l'heure d'exécution.

0 commentaires

Articles qui pourrait vous intéresser :

Que puis-je utiliser pour la conversion d'entrée au lieu de scanf?
Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde?
Comment vérifier si un pointeur void (void *) est l'un des deux types de données?
L'écran LCD affiche des caractères aléatoires (MPLAB)