Discussion :

[SpiceGuid]

Il est fréquent que la récursion terminale soit imbriquée dans un if.
Le compilateur OCaml est-il capable de compiler ces deux fonctions:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
let rec list_max init l =
  match l with
  | []   -> init
  | a::l ->
    if a > init then
      list_max a l
    else
      list_max init l;;
 
let rev_append_map_filter p f l1 l2 =
  let rec loop l acc =
    match l with
    | [] -> acc
    | h::t ->
        if p h then loop t (f h::acc)
        else loop t acc
  in loop l1 l2;;

D'une façon qui ne consomme pas plus de pile que ces deux fonctions:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
let rec list_max init l =
  match l with
  | []   -> init
  | a::l ->
      list_max (if a > init then a else init) l;;
 
let rev_append_map_filter p f l1 l2 =
  let rec loop l acc =
    match l with
    | [] -> acc
    | h::t ->
        loop t (if p h then f h::acc else acc)
  in loop l1 l2;;

[Jedai]

Bien sûr, de son point de vue il n'y a aucune différence dans la détection de l'optimisation : dans un cas comme dans l'autre la valeur renvoyée dans certaines branches de l'exécution de la fonction est simplement un appel récursif à la fonction, ce qui déclenche l'optimisation.

--
Jedaï

[InOCamlWeTrust]

Oui, mais curieusement, il me semble qu'optimiser ce genre de construction serait plus simple dans un langage comme le C qui fait une vraie distinction entre le flux et l'expression. C'est d'ailleurs tout l'intérêt de disposer, en C, des deux if : le if(){ }else{ } et le ( )? : . Dans l'esprit, l'exemple donné avec le premier list_max est un if de contrôle de flux, alors que le deuxième serait un if d'expression.

Ca serait bien d'avoir l'avis d'un expert en compilation.

[gorgonite]

perso, j'ai un doute quant à la différence d'optimisations possibles à partir de ces deux formes... puisqu'elle implique la même "forme" de l'arbre SSA


faudrait comparer les asm générés...

[SpiceGuid]

Voilà le code asm généré (ocamlopt 3.09.3 MinGW) pour list_max1 et list_max2 où list_max2 est la version trivialement récursive terminale:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
_list_max1:
	subl	$12, %esp
L102:
	cmpl	$1, %ebx
	je	L100
	movl	%eax, 0(%esp)
	movl	4(%ebx), %ecx
	movl	%ecx, 8(%esp)
	movl	(%ebx), %ebx
	movl	%ebx, 4(%esp)
	pushl	%eax
	pushl	%ebx
	movl	$_caml_greaterthan, %eax
	call	_caml_c_call
L103:
	addl	$8, %esp
	cmpl	$1, %eax
	je	L101
	movl	4(%esp), %eax
	movl	8(%esp), %ebx
	jmp	L102
L101:
	movl	0(%esp), %eax
	movl	8(%esp), %ebx
	jmp	L102
L100:
	addl	$12, %esp
	ret

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
_list_max2:
	subl	$12, %esp
L107:
	cmpl	$1, %ebx
	je	L104
	movl	%ebx, 0(%esp)
	movl	%eax, 4(%esp)
	movl	(%ebx), %ebx
	movl	%ebx, 8(%esp)
	pushl	%eax
	pushl	%ebx
	movl	$_caml_greaterthan, %eax
	call	_caml_c_call
L108:
	addl	$8, %esp
	cmpl	$1, %eax
	je	L106
	movl	8(%esp), %eax
	jmp	L105
L106:
	movl	4(%esp), %eax
L105:
	movl	0(%esp), %ebx
	movl	4(%ebx), %ebx
	jmp	L107
L104:
	addl	$12, %esp
	ret

Apparemment:

• les deux versions font un JMP au lieu d'un CALL, elles sont toutes deux récursives terminales
• les deux versions sont assez semblables mais pas totalement identiques, en particulier la 1ière version fait bien deux JMP terminaux là où la 2nd ne fait qu'un JMP terminal
• la première version me semble très légèrement plus rapide (elle JMP au plus tôt), la seconde version me semble très légèrement plus courte (mais elle JMP au plus tard), il s'agit donc d'un léger compromis vitesse/espace plutôt que d'une véritable optimisation, list_max1 est une version "inlinée" de list_max2

[InOCamlWeTrust]

perso, j'ai un doute quant à la différence d'optimisations possibles à partir de ces deux formes... puisqu'elle implique la même "forme" de l'arbre SSA

Les arbres utilisés par les compilateurs Caml sont très personnels : je ne sais pas ce que tu appelles SSA, mais il n'y a rien, à ma connaissance, de dénominé de la sorte dans le compilateur.

[gorgonite]

Les arbres utilisés par les compilateurs Caml sont très personnels : je ne sais pas ce que tu appelles SSA, mais il n'y a rien, à ma connaissance, de dénominé de la sorte dans le compilateur.

euh, je parlais seulement du C avec (() ? () : ()) et if { } else { }

http://en.wikipedia.org/wiki/Static_...ssignment_form

[InOCamlWeTrust]

Oui, effectivement, les arbres SSA (je sais maintenant ce à quoi ça correspond !) des () ? : et du if(){}else{} peuvent être identiques, cependant, leur utilisation ne l'est pas et il ne faut pas oublier que, dans le cas de GCC par exemple, il s'opère plusieurs transformations avant d'arriver à la décomposition d'un programme sous forme SSA... donc, à la fin de la compilation, il se peut que les deux constructions soient compilées de façon très différente.

[gorgonite]

il s'opère plusieurs transformations avant d'arriver à la décomposition d'un programme sous forme SSA... donc, à la fin de la compilation, il se peut que les deux constructions soient compilées de façon très différente.

ben justement, il n'y en a plus tellement... j'ai entendu dire que les compilateurs ont un frontend pour le langage et un middle-end et backend communs désormais

[InOCamlWeTrust]

Oui, je confirme, les compilateurs partagent beaucoup.

J'étudie actuellement dans le détail GCC et ses front-end : les front-end sont spécifiques ; seul le back-end est commun... cependant, dans le back-end, le programme est transformé dans trois représentations différentes : il y a tout d'abord l'arbre GENERIC, dont la structure est très proche de celle du C, puis cet arbre est transformé en GIMPLE, lui-même traduit en représentation RTL. Ces trois représentations sont génériques. La production du code assembleur vient plus tard, et se fait de façon assez élégante. En clair, le code de GCC est assez propre, il ne comporte pas de bouts de code dépendant de machines ou architectures différentes.

Mais il ne faut pas se tromper : dans le cas d'un langage donné, il faut que le front-end traduise le programme dans l'une des trois représentations génériques décrites ci-dessus (la plupart du temps, c'est GENERIC qui est choisi)... et cette étape peut recquérir elle-même plusieur représentations. Dans le cas d'un hypothétique front-end pour OCaml, entre autres, tout le typage, c'est-à-dire la partie chiante et difficile, devrait être faite par le front-end... sans compter l'étape de traduction en GENERIC...