Exercises

Tracing Function Application

1. Activate tracing of the function List.fold_left and evaluate the following expression:

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

   What does the trace show you?

   
   # #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.
   
   
2. Define the function fold_left_int, identical to List.fold_left, but with type:
   
   (int -> int -> int) -> int -> int list -> int.
   Trace this function. Why is the output of the trace different?

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

Performance Analysis

1. Compile the two programs erart and eranrt with profiling options using the bytecode compiler and the native code compiler respectively.

   $ 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
   

   
   
   
2. Execute the programs passing them the numbers 3000 4000 5000 6000 on the command line.

   $ 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
   

   
   
   
3. Visualize the results with the ocamlprof and gprof commands. What can you say about the results? 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