Exercices

Exercices

Traces d'applications

Cet exercice montre l'évaluation des arguments au moment de l'application.

Activer la trace de la fonction List.fold_left et évaluer l'expression suivante :


List.fold_left (-) 1 [2; 3; 4; 5];;

Que vous indique la trace?


# #trace List.fold_left ;;
List.fold_left is now traced.


# List.fold_left (-) 1 [2; 3; 4; 5] ;;
List.fold_left <-- <fun>
List.fold_left --> <fun>
List.fold_left* <-- <poly>
List.fold_left* --> <fun>
List.fold_left** <-- [<poly>; <poly>; <poly>; <poly>]
List.fold_left <-- <fun>
List.fold_left --> <fun>
List.fold_left* <-- <poly>
List.fold_left* --> <fun>
List.fold_left** <-- [<poly>; <poly>; <poly>]
List.fold_left <-- <fun>
List.fold_left --> <fun>
List.fold_left* <-- <poly>
List.fold_left* --> <fun>
List.fold_left** <-- [<poly>; <poly>]
List.fold_left <-- <fun>
List.fold_left --> <fun>
List.fold_left* <-- <poly>
List.fold_left* --> <fun>
List.fold_left** <-- [<poly>]
List.fold_left <-- <fun>
List.fold_left --> <fun>
List.fold_left* <-- <poly>
List.fold_left* --> <fun>
List.fold_left** <-- []
List.fold_left** --> <poly>
List.fold_left** --> <poly>
List.fold_left** --> <poly>
List.fold_left** --> <poly>
List.fold_left** --> <poly>
- : int = -13

La trace indique seulement le passage des arguments à la fonction List.fold_left, mais n'affiche pas les valeurs des arguments. La nature polymorphe des paramètres de List.fold_left empèche la trace de pouvoir afficher les valeurs des arguments passés.

Définir la fonction fold_left_int, identique à List.fold_left, mais dont le type est : (int -> int -> int) -> int -> int list -> int.
Tracer cette fonction. Pourquoi l'affichage de la trace est-il différent?


# let rec fold_left_int f (r : int)  (l : int list)  = 
 match l with 
   [] -> r
 | t::q -> fold_left_int f (f r t) q ;;
val fold_left_int : (int -> int -> int) -> int -> int list -> int = <fun>


# #trace fold_left_int ;;
fold_left_int is now traced.
# fold_left_int (-) 1 [2; 3; 4; 5] ;;
fold_left_int <-- <fun>
fold_left_int --> <fun>
fold_left_int* <-- 1
fold_left_int* --> <fun>
fold_left_int** <-- [2; 3; 4; 5]
fold_left_int <-- <fun>
fold_left_int --> <fun>
fold_left_int* <-- -1
fold_left_int* --> <fun>
fold_left_int** <-- [3; 4; 5]
fold_left_int <-- <fun>
fold_left_int --> <fun>
fold_left_int* <-- -4
fold_left_int* --> <fun>
fold_left_int** <-- [4; 5]
fold_left_int <-- <fun>
fold_left_int --> <fun>
fold_left_int* <-- -8
fold_left_int* --> <fun>
fold_left_int** <-- [5]
fold_left_int <-- <fun>
fold_left_int --> <fun>
fold_left_int* <-- -13
fold_left_int* --> <fun>
fold_left_int** <-- []
fold_left_int** --> -13
fold_left_int** --> -13
fold_left_int** --> -13
fold_left_int** --> -13
fold_left_int** --> -13
- : int = -13
# #untrace_all ;;
fold_left_int is no longer traced.
List.fold_left is no longer traced.

La fonction fold_left_int est monomorphe. Le mécanisme de trace connaît le type des arguments et peut alors les afficher lors de leur passage.

Évaluation des performances

On reprend l'exercice proposé au chapitre 9, page ??, où l'on comparait l'évolution du tas pour deux programmes (l'un récursif terminal et l'autre non) de calcul de nombres premiers. On compare maintenant les temps passés dans chaque fonction en utilisant les outils de profiling et de temps d'exécution. Cet exercice permet d'illustrer l'intérêt de l'expansion en ligne (voir chapitre 7).

Compiler avec l'option de profiling les deux programmes erart et eranrt en utilisant le compilateur de code-octet et le compilateur natif.

$ ocamlcp -custom -o era_rt_bc unix.cma interval.ml trgc.ml eras2.ml era2_main.ml main_rt.ml -cclib -lunix
$ ocamlcp -custom -o era_nrt unix.cma interval.ml trgc.ml eras.ml era2_main.ml main_nrt.ml -cclib -lunix
$ ocamlopt -p -o era_rt_nat unix.cmxa interval.ml trgc.ml eras2.ml era2_main.ml main_rt.ml -cclib -lunix
$  ocamlopt -p -o era_nrt_nat unix.cmxa interval.ml trgc.ml eras.ml era2_main.ml main_nrt.ml -cclib -lunix

Exécuter ces programmes en leur passant les nombres 3000 4000 5000 6000 sur la ligne de commande.
```
$ era_rt_bc traceRT-BC 3000 4000 5000 6000
$ era_nrt_bc traceNRT-BC 3000 4000 5000 6000
$ era_rt_nat traceRT-NAT 3000 4000 5000 6000
$ era_nrt_nat traceNRT-NAT 3000 4000 5000 6000
```

Visualiser les résultats par les commandes ocamlprof et grpof. Que pouvez-vous dire au vu des résultats ? Compilateur de code-octet :

La commande ocamlprof lit les informations du fichier camlprof.dump. Si plusieurs exécutions différentes ont été lancées, seule l'information de cette dernière est accessible.

Voici les informations ressorties pour la version récursive terminale :

$ ocamlprof eras2.ml
(* fichier eras2.ml *)

let erart l  = 
  (* 4 *) let rec erart_aux l r = (* 2436 *) match l with 
    [] -> (* 4 *) List.rev r
  | p::q -> (* 2432 *) erart_aux  (List.filter ( fun x -> (* 808410 *) x mod p <> 0) q) (p::r) 
  in 
    erart_aux l [] ;;

let erart_go n = 
  (* 4 *) erart (Interval.interval (<)  (fun x -> (* 17992 *) x + 1) 2 n) ;;

et pour la version récursive terminale :

$ ocamlprof eras.ml
(* fichier eras.ml *)

let rec eras l  = (* 2436 *) match l with 
  [] -> (* 4 *) []
| p::q -> (* 2432 *) p:: (eras (List.filter ( fun x -> (* 808410 *) x mod p <> 0) q)) ;;

let era_go n = 
  (* 4 *) eras (Interval.interval (<)  (fun x -> (* 17992 *) x + 1) 2 n) ;;

On s'aperçoit que dans les deux cas, il y a 2436 appels à la fonction principale, dont 4 avec une liste vide et 2432 dans l'autre cas.

Attention le profilage rend invalide de nombreuses optimisations du compilateur.

Compilateur natif :

L'exécution d'un exécutable autonome natif compilé en mode -p produit un fichier gmon.out.

$ gprof era_rt_nat

affiche tout d'abord le temps passé dans chaque fonction :

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 44.44      0.12     0.12   808410     0.15     0.15  Eras2_fun_112
 18.52      0.17     0.05     2436    20.53    32.67  List_rev_append_57
 11.11      0.20     0.03     2432    12.34    73.68  List_find_213
  7.41      0.22     0.02      114   175.44   175.44  sweep_slice
  7.41      0.24     0.02       34   588.24   588.24  mark_slice
  3.70      0.25     0.01    76203     0.13     0.13  allocate_block
  3.70      0.26     0.01    64466     0.16     0.31  oldify
...

puis le graphe d'appel.

$ gprof era_nrt_nat

affiche tout d'abord le temps passé dans chaque fonction :

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 42.42      0.14     0.14   808410     0.17     0.17  Eras_code_begin
 15.15      0.19     0.05     2432    20.56    95.63  List_find_213
 15.15      0.24     0.05     2432    20.56    39.31  List_rev_append_57
  6.06      0.26     0.02    93936     0.21     0.53  oldify
  6.06      0.28     0.02    74519     0.27     0.27  allocate_block
  6.06      0.30     0.02       37   540.54   540.54  mark_slice
  3.03      0.31     0.01    74519     0.13     0.40  alloc_shr
...

L'outil ocamlprof compte le nombre d'appels ou de passage dans certaines parties d'une fonction sans indication de temps.

Par contre , l'outil gprof est plus précis car il indique les temps passés dans chaque fonction.

Attention les versions compilées avec l'option -p effectuent un travail supplémentaire qui est perceptible lors de mesures de temps. Les versions .exe sont compilées sans cette option.

$ time era_rt.exe a1 3000 4000 5000 6000
0.230u 0.010s 0:00.25 96.0%     0+0k 0+0io 129pf+0w
$ time era_rt_nat a2 3000 4000 5000 6000
0.510u 0.010s 0:00.52 100.0%    0+0k 0+0io 134pf+0w
$ time era_nrt.exe a3 3000 4000 5000 6000
0.220u 0.020s 0:00.24 100.0%    0+0k 0+0io 130pf+0w
$ time era_nrt_nat a4 3000 4000 5000 6000
0.520u 0.010s 0:00.53 100.0%    0+0k 0+0io 134pf+0w
$ visu a1
Nombre de Gc: mineur = 131, majeur = 20
$ visu a2
Nombre de Gc: mineur = 131, majeur = 20
$ visu a3
Nombre de Gc: mineur = 131, majeur = 23
$ visu a4
Nombre de Gc: mineur = 131, majeur = 23

$ gprof era_rt_nat