Discussion :

[Blustuff]

Bonjour,

Supposer une capacité d'optimisation du compilateur permet généralement d'écrire du code plus efficace. Ainsi, je souhaites avoir une implémentation assez spécifique d'une structure de graphe qui soit efficace pour l'usage que j'en ai. Si je choisis d'indexer les sommets de ce graphe par des entiers, et que j'utilise des map de la librairie standard, je peux renvoyer ces entiers dans les fonctions successeurs, ou iter. Ensuite, l'utilisateur donnera ces index pour appeler d'autres fonctions. Le soucis, c'est qu'on refera alors un parcours de la structure de donnée pour trouver le sommet indexé.

Une solution à ce problème est de renvoyer à l'utilisateur un type abstrait représentant les sommets mais contenant toutes les informations associées à ce sommet, de sorte que lorsque l'on appelle une fonction avec ce sommet, la fonction n'ait plus qu'à extraire l'information du tas.

C'est là que le compilateur intervient. Après inlining, il doit remarquer qu'en fait, une seule information du tas était nécessaire, et que donc la construction du tas était inutile. De cette manière, l'abstraction de l'objet "sommet" ne créée aucune perte de performances.

Seulement j'ai un doute sur l'utilisation de ce genre d'optimisation. J'ai construit le programme simple suivant :

Code :

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

1
2
3
4
5
6
7
8
let f x y = (x,y) ;;
let g (x,y) = x ;;
 
let _ =
  let x = f 1 2 in
  let y = g x in
  Format.printf "%d\n" y
;;

La fonction f embarque dans un couple deux informations. La fonction g extrait l'une de ces deux informations. Dans le code en dessous, on se rend compte qu'embarquer 2 dans le couple était en fait inutile. On obtient donc un programme trivialement équivalent à celui-ci :

Code :

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

1
2
3
let _ =
  Format.printf "%d\n" 1
;;

Oui mais voilà, ce qu'ocamlopt produit :

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
29
camlTest__entry:
	subl	$4, %esp
.L105:
	movl	$camlTest__3, %eax
	movl	%eax, camlTest
	movl	$camlTest__2, %eax
	movl	%eax, camlTest + 4
	call	caml_alloc2
.L106:
	leal	4(%eax), %eax
	movl	$2048, -4(%eax)
	movl	$3, (%eax)
	movl	$5, 4(%eax)
	movl	camlTest + 4, %ebx
	movl	(%ebx), %ecx
	call	*%ecx
.L107:
	movl	%eax, 0(%esp)
	movl	$camlTest__1, %eax
	call	camlFormat__printf_1770
.L108:
	movl	%eax, %ebx
	movl	(%ebx), %ecx
	movl	0(%esp), %eax
	call	*%ecx
.L109:
	movl	$1, %eax
	addl	$4, %esp
	ret

qui semble un peu plus complexe que l'idéal. Faut il renoncer à l'idée initiale ?

[gasche]

Le compilateur OCaml n'est pas un compilateur optimisant. Il ne fait essentiellement aucune optimisation, et ce n'est pas la peine de compter pour lui pour rendre magiquement ton programme plus rapide.

Si tu veux vraiment de hautes performances, il faut que tu évites d'allouer inutilement. Est-ce qu'il serait possible par exemple de renvoyer exactement le contenu du noeud ? Comme ça, tu renverrais un pointeur vers le noeud (au lieu de construire un tuple spécialement pour l'occasion).

Je pense qu'on peut difficilement aller plus loin sans plus d'information sur :
- tes besoins de perfs
- ton graphe
- les informations que tu veux rendre disponible avec chaque noeud


Digression : en dehors du cadre strict (no pun intended) de OCaml, il est intéressant de remarquer que le cas de figure dont tu parles est un cas où l'évaluation paresseuse se révèle très intéressante. En effet, si tu renvoies une structure de donnée paresseuse contenant ces différentes informations, ce n'est pas (comme avec une structure stricte) le *producteur* qui décide de quelle quantité de calcul sera effectuée, mais le *consommateur*. Typiquement, en Haskell par exemple, on enverrait ici un gros tuple paresseux sans soucis, sachant que les informations que tu ne demanderas pas ne seront jamais évaluées.

On peut utiliser cette approche en Caml. Le plus simple dans ce cas (où tu n'as pas besoin de mémoïsation) est de représenter tes informations sous un type (unit -> t) au lieu de (t) : c'est à l'appelant d'appliquer explicitement () pour les obtenir. Cependant, même si ça permet effectivement d'économiser le temps de calcul pour les informations non demandées, ça reste couteux en mémoire : construction du tuple, et surtout construction de chacune des fermetures (donc en mémoire par contre, tu paies même pour ce que tu n'utiliseras pas). C'est un problème de l'évaluation paresseuse : c'est un mode d'évaluation tellement peu efficace en général que, pour que ce soit vraiment utilisable, il faut *déjà* avoir un compilateur optimisant.

Le papier "Why Functional Programming Matters" est célèbre pour citer des "avantages de modularité" de la programmation fonctionnelle de ce genre, qui sont en fait dues à la paresse. (Disclaimer : je ne l'ai pas lu, honte à moi).

[Blustuff]

Merci pour ta réponse.

Le compilateur OCaml n'est pas un compilateur optimisant. Il ne fait essentiellement aucune optimisation, et ce n'est pas la peine de compter pour lui pour rendre magiquement ton programme plus rapide.

Ok, enfin les optimisations dont je parle sont quand même les plus basiques qui soient. Je trouve ça un peu choquant : la programmation modulaire et la programmation fonctionnnelle induisent un coût supplémentaire qui est quasiment totalement annulé par l'inlining suivi d'optimisation de base comme la factorisation d'expressions communes, l'extraction d'invariant, la propagation des constantes et la suppression de code inutile. C'est une sorte de synergie ou l'inlining sans les autres ou les autres sans l'inlining perdent quand même beaucoup en efficacité.

Si tu veux vraiment de hautes performances, il faut que tu évites d'allouer inutilement. Est-ce qu'il serait possible par exemple de renvoyer exactement le contenu du noeud ? Comme ça, tu renverrais un pointeur vers le noeud (au lieu de construire un tuple spécialement pour l'occasion).

Au prix d'un espace mémoire plus important et d'un coût de construction des noeuds d'autant plus élevé. Il ne s'agit que d'une poignée de cycles, qui sont donc perdus au décuple d'après ce que tu me dis à propos de l'absence d'optimisation.

Je pense qu'on peut difficilement aller plus loin sans plus d'information sur :
- tes besoins de perfs
- ton graphe
- les informations que tu veux rendre disponible avec chaque noeud

Difficile à dire. J'ai pas encore réussi à faire marcher ocamlprof avec OMake. Le besoin en perf, c'est surtout de pouvoir publier des temps d'exécution qui sont suffisement bas pour ne pas effrayer les gens qui travaillent sur les compilateurs. Jusqu'à présent, j'utilise des structures de données assez inadaptées, par défaut. Je reprogramme une structure de graphe plus adéquat pour l'utilisation que j'en fait dans un soucis de lecture du code et j'avoue que la question que je pose ici est plus par curiosité qu'un véritable problème.

Par ordre de priorité, du plus fréquent au moins fréquent. Le premier besoin sur le graphe, ce sont des parcours en tout genre et donc la nécessité de pouvoir passer vite d'un sommet à ses prédécesseurs/successeurs ainsi que l'accès aux etiquettes associées aux noeuds/ aux arcs. Le second besoin est la possibilité de facilement ajouter / retirer des sommets et des arcs tout en conservant un graphe transitivement réduit. Enfin, le troisième besoin est la copie du graphe. Je pense qu'il est raisonnble de faire l'hypothèse que le nombre d'arcs est proportionnel au nombre de sommets.

Digression : en dehors du cadre strict (no pun intended) de OCaml, il est intéressant de remarquer que le cas de figure dont tu parles est un cas où l'évaluation paresseuse se révèle très intéressante. En effet, si tu renvoies une structure de donnée paresseuse contenant ces différentes informations, ce n'est pas (comme avec une structure stricte) le *producteur* qui décide de quelle quantité de calcul sera effectuée, mais le *consommateur*. Typiquement, en Haskell par exemple, on enverrait ici un gros tuple paresseux sans soucis, sachant que les informations que tu ne demanderas pas ne seront jamais évaluées.

L'évaluation paresseuse rajoute un coût faible mais existant à l'exécution. Du coup, il y a probablement des meilleurs compromis dans mon cas.

On peut utiliser cette approche en Caml. Le plus simple dans ce cas (où tu n'as pas besoin de mémoïsation) est de représenter tes informations sous un type (unit -> t) au lieu de (t)

L'évaluation paresseuse est aussi une extension de ocaml avec le mot clé lazy et le module Lazy. Cela étant dit, si je vois pour moi des applications où c'est utile (genre de cas où il est assez compliqué algorithmiquement de savoir si on va ou non avoir besoin de calculer une expression qui risque d'être un peu chère) c'est quand même pas partout.

[gasche]

La façon dont tu abordes le problème ressemble à de l'optimisation prématurée. Tu devrais coder quelque chose d'algorithmiquement efficace sans te poser trop de questions, et ensuite faire du profiling avant d'améliorer les parties sensibles seulement.

L'évaluation paresseuse est aussi une extension de ocaml avec le mot clé lazy et le module Lazy.

Oui mais, par rapport au simple (unit -> t), (lazy t) fait de la mémoization : une fois la valeur calculée, il la stocke pour ne pas avoir à recalculer la valeur plusieurs fois. Dans les cas où tu sais que tu ne demanderas la valeur qu'au plus une fois (ou que tu peux laisser à l'utilisateur la responsabilité de ne pas rappeler bêtement la fonction plusieurs fois), cela induit un surcoût qui n'est pas nécessaire.

[Cacophrene]

Bonjour,

On peut aussi faire une partie de l'inlining à la main. C'est une (mauvaise) habitude que j'ai prise mais qui peut être profitable. Quelques autres astuces pêle-mêle :

• Préférer les fonctions tail-rec chaque fois que c'est possible.
• Comme l'a écrit bluestorm, éviter d'allouer inutilement (au besoin, modifier les paramètres du GC selon le comportement du programme).
• Ne pas abuser des fonctions d'ordre supérieur et des fermetures.
• Pas de manipulation massive du type string (préférer Buffer.t).
• Si ça ne va toujours pas, abaisser le niveau d'abstraction des types utilisés (je suis déjà beaucoup moins fan, mais sur des applis critiques ça peut payer).

Bien sûr tout ceci vient en dernier, quand tout marche et que le profilage a été soigneusement fait.

Cordialement,
Cacophrène

[Blustuff]

La façon dont tu abordes le problème ressemble à de l'optimisation prématurée.

La question est importante parce qu'elle décide de quelle interface adopter pour la structure de donnée en question. Si le langage est bien fait, on n'a pas à se poser la question : on définit une interface et quand on optimisera, le compilateur supprimera après inlining les paramètres inutiles de l'interface et leur calcul. Là, je suis obligé de passer un certain nombre de paramètres à mes fonctions, parce que je ne sais pas si l'implémentation actuelle et l'implémentation optimisée que j'aurai plus tard auront besoin des mêmes paramètres pour fournir la même chose.

[gasche]

Je n'y crois pas. À ma connaissance, optimiser vraiment demande quasi-systématiquement une cassure de l'abstraction. L'idée qu'on peut définir une fois pour toute les différentes fonctions et ensuite se contenter, pour l'optimisation, de changer leur *code* sans toucher à un poil de leur interface me paraît plus utopique que réelle.

La façon dont je conçois le problème est le suivant : je commence par choisir une interface simple et claire, adaptée au problème à résoudre mais la plus générale possible. Je l'utilise dans tout mon programme. Après avoir isolé les parties critiques du point de vue des performances, j'étudie leurs réels besoins, et :
- Si possible, je change la représentation des mes données et l'implémentation de mes routines pour améliorer les performances.
- Si une nouvelle interface, plus complexe, permet plus d'optimisations, je rajoute en parallèle cette nouvelle interface, que j'utilise seulement dans la partie critique de mon code. En général cette interface casse partiellement l'encapsulation de mes données, alors j'essaie de ne l'utiliser que dans les parties internes qui en ont vraiment besoin.
- S'il n'est pas réaliste de présenter deux interfaces aussi différentes avec une même représentation, je n'hésite pas à changer localement mes données pour passer d'une représentation "simple" à une représentation optimisée. Si par exemple j'ai dans l'absolu une interface style liste pour une structure, mais j'ai localement besoin d'accès arbitraire, je peux construire un tableau localement pour la section critique de mon code. Bien sûr, ça ne marche bien que si les transferts de la partie critique à la partie non critique sont suffisamment peu nombreux (si on veut interlacer des appels de l'interface générale et l'interface critique, ça ne va pas).


Tant que tu ne sais pas quelle implémentation optimisée tu auras plus tard, à mon avis ce n'est pas la peine d'essayer de la prendre en compte dans ton design. C'est la meilleure façon d'obtenir un monstre over-engineeré qui n'est en fait pas du tout flexible et modulaire. C'est comme les gens qui font de la POO et qui veulent concevoir leurs classes de base de façon à être extensible par héritage, alors qu'ils ne savent pas encore de quelles façons les classes dérivées vont vouloir enrichir le comportement : ça donne des monstre fragiles.

[Blustuff]

À ma connaissance, optimiser vraiment demande quasi-systématiquement une cassure de l'abstraction.

C'est comme je l'ai dit de moins en moins vrai grâce aux capacités d'optimisation des compilateurs. Là où on abstrait pour diverses raisons, le compilateur optimisant peut être capable de faire l'opération inverse. S'il y a vingt ans on a écrit des monstres d'optimisation en C, cette nécessité ne disparaît pas parce qu'on a de la puissance de calcul ou quoi, mais parce que les compilateurs C/C++ nous permettent de faire certaines abstractions sans pertes de performance. Je me suis suffisamment battu contre les optimisations à la main dans les codes sources qui peuvent être fait par les compilateurs.

Là où peut se dire qu'un compilateur optimisant a pour objectif de produire un code plus rapide, moi je lui donne un autre objectif : permettre des abstractions sans contrepartie de temps d'exécution.

L'idée qu'on peut définir une fois pour toute les différentes fonctions et ensuite se contenter, pour l'optimisation, de changer leur *code* sans toucher à un poil de leur interface me paraît plus utopique que réelle.

Une fois pour toute non. Mais si tu as une idée des modification que tu es prêt à faire, tu peux les anticiper. Tu n'anticiperas pas toutes les modifications, et tenter de le faire peut être, comme tu le soulignes à la fin sur la POO, catastrophique. Néanmoins, il n'est pas plus efficace de tout programmer et de se rendre compte à la fin que la nécessité d'optimiser nous fait perdre des dizaines d'heures de travail parce qu'on avait pas anticipé. C'est un pari : il faut parier sur ce que l'on peut anticiper et ce que l'on ne peut pas.

Concrètement ici, je pourrais me dire : "Je pense faire au plus deux implémentation : une première très simple, et si nécessaire dans l'avenir, une optimisée. Je dois donc prévoir une interface compatible à ces deux implémentations." A ces deux implémentations seulement. Il ne s'agit pas d'avoir une interface universelle, mais une interface qui anticipe des changements possibles, incertains.

Dans mon cas, je n'ai pas encore fait ce pari. Comme je l'ai dit, je pose la question par curiosité. Changer l'interface des graphes plus tard me demandera une ou deux heures, beaucoup moins que le temps nécessaire à d'éventuelles optimisations.