Discussion :

[TropMDR]

Sur ma machine, on obtient le même gain en performance (en fait légèrement supérieur) en écrivant:

Code :

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

1
2
3
4
5
6
7
8
let rec ntr_pow x = function
| 0 -> 1
| y ->
  let xy2 = ntr_pow x (y / 2) in
  if y mod 2 = 1 then
    xy2 * xy2 * x
  else
    xy2 * xy2

Bien sûr, ce sont deux optimisations indépendantes qui se combinent, et on peut obtenir un code encore plus de la mort en ayant une version récursive terminale avec ça, ou même en écrivant la fonction en C pour éviter les décalages de bits.

Euh, je pense que si tu modifies la fonction qui va le plus lentement et que tu obtiens une plus grosse différence de performance, c'est que tu n'as pas fait une optimisation, mais au contraire que tu as agravé la situation hein.

Maintenant, est-ce que c'est ce qu'on a envie d'apprendre aux gens ?

Est ce qu'on a envie d'apprendre aux gens comment écrire du code efficace, et quelles sont les sources potentielles de lenteur dans un programme ? Je pense que oui. Pour qu'ils comprennent par exemple que transformer un programme avec des appels de fonction en un programme avec des sauts, ce n'est pas

Il n'empêche que pour moi il s'agit ici de différences de performances fragiles, peu justifiées (ok, il y a quelques spills de plus dans la version non-tail-rec)

Ce ne sont pas "quelques spills en plus", ce sont des appels de fonction. Et un appel de fonction (avec son incrément de la pile, son saut, son décrément, son retour), ça coute cher, surtout face à une multiplication ! Encore une fois, 25% de gain de performance, ce n'est pas une "différence de performance fragile peu justifiée"...

Je persiste à penser que pour cette fonction, demander une version tail-récursive n'a aucun intérêt.

J'aimerai bien savoir comment tu justifies qu'un gain de 25% sur un code numérique n'a aucune intéret...

La tail-récursivité ce n'est pas une idole à satisfaire dans chaque fonction

Bien sur que non. Par exemple quand on construit des listes, puisqu'à chaque tour de boucle/appel de fonction, on alloue sur le tas, on passe dans le GC, on suit des pointeurs non contigües en mémoire, il est clair que dans ces cas là, le seul intéret d'être tail rec est de ne pas faire exploser la pile, pas de gagner en terme de performance. Pour du code numérique, encore une fois, c'est différent.

et son utilisation dans un cadre d'enseignement doit se baser sur des raisons rationnelles, justifiées, à un niveau sémantique compréhensible par les élèves.

Du genre "le corps de la boucle est vraiment pas cher, donc l'appel de fonction a un cout loin d'être négligeable" ?

PS: sur ma machine, avec le même code en faisant des calculs de nombres flottants, la version non tail-rec est systématiquement plus rapide, j'observe un gain de 10% environ. Je suppose que c'est parce que le compilateur optimise mieux le boxing dans `xy2 *. xy2 *. x`. Mais ça me semble une illustration assez caractéristique de la fragilité de ces considérations.

Alors là, j'aimerais vraiment bien savoir comment tu as fait tes tests...

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
let rec ntr_pow x y =
  if y = 0 then 1. else
  let xy2 = ntr_pow x (y / 2) in
  if y mod 2 = 1 then
    xy2 *. xy2 *. x
  else
    xy2 *. xy2
 
 
let tr_pow x y =
  let rec aux xpow res y =
    if y = 0 then res else
    aux (xpow *. xpow) (if y mod 2 = 1 then res *. xpow else res) (y / 2) in
  aux x 1. y
 
let nothing x y = x
 
let f = tr_pow
 
let _ = 
  for i = 1 to 10000000 do
    for j = 1 to 32 do
      let _ = f 42. j in
      ()
    done
  done

J'ai pour non tail rec
Real: 19.50s User: 19.44s System: 0.03s Percent: 99% Cmd: ./ntr_pow
et pour tail rec
Real: 16.56s User: 16.49s System: 0.02s Percent: 99% Cmd: ./tr_pow

La différence est moins grosse, mais quand même toujours dans le bon sens

[gasche]

Euh, je pense que si tu modifies la fonction qui va le plus lentement et que tu obtiens une plus grosse différence de performance, c'est que tu n'as pas fait une optimisation, mais au contraire que tu as agravé la situation hein.

J'ai bien dit qu'on obtenait le même *gain* en performance. Sous-entendu, "... en passant à cette version" par rapport à "... en passant à la version tail-rec". Désolé si c'était ambigu. Concrètement, sur ma machine le code donné ci-dessous avec un pattern matching au lieu d'un test d'égalité va légèrement plus vite que ta version tail-rec (environ 7.2s au lieu de 7.7, pour 8.8s avec la version de base, le tout sur des entiers et pas des flottants).

Ce n'est pas une remarque très intéressante en soi, mais c'est un signe à mon avis que les gains dont on parle sont relativement vains : bien sûr, pour du code numérique tout ça, c'est intéressant, mais à ce moment là autant tout recoder en C directement. En pratique demander aux étudiants "évitez les tests d'égalité sur des constantes, le pattern-matching c'est plus rapide" aurait ici été un meilleur conseil (et moins nuisible à la lisibilité) que "faites une version tail-récursive". Avec des raisonnements comme ça on en arrive à écrire "if .. else if .. else if ..." en PHP plutôt que switch, parce que ça va plus vite.

Ce ne sont pas "quelques spills en plus", ce sont des appels de fonction. Et un appel de fonction (avec son incrément de la pile, son saut, son décrément, son retour), ça coute cher, surtout face à une multiplication ! Encore une fois, 25% de gain de performance, ce n'est pas une "différence de performance fragile peu justifiée"...

Les appels de fonction coûtent effectivement toujours plus cher qu'une multiplication. Par contre, une fonction tail-rec n'est pas toujours plus rapide qu'une fonction équivalente non-tail-rec (parce que pour obtenir la tail-rec tu vas potentiellement devoir garder des structures de données dans tes accumulateurs, et en fait reproduire sur la pile le pattern d'allocation qui se fait sur le tas dans la version directe). Si tu fais comprendre aux étudiants que "(nontail -> tail) = performance win", c'est du cargo-cult programming. Il faut une méthode raisonnable pour leur permettre d'évaluer l'intérêt de la transformation. Ton idée de connaît-bien-tout-ça c'est que comme tu connais bien la façon dont c'est compilé (et que tu testes pour vérifier), tu vas savoir faire la différence aux cas par cas. Mais les élèves ne savent pas. Ce que je propose à la place (et ce que j'appliquais dans mon message initial) c'est de penser aux appels non-tail en terme de consommation mémoire; les étudiants savent raisonner sur la complexité mémoire du code et peuvent avoir une idée justifiée (bien sûr à la louche et négligeant les facteurs constants dont on parle ici) de l'intérêt de la transformation.

Je dis que cette optimisation est "fragile" parce qu'elle est équivalente, en gain, à des optimisations stupides comme celle citée plus haut, et mise en danger par des facteurs magiques difficiles à comprendre (cf. mon exemple sur les nombres flottants).

Alors là, j'aimerais vraiment bien savoir comment tu as fait tes tests...

J'ai re-testé, chez moi la version non-tail bien est systématiquement plus rapide sur les opérations de flottant (11.9s contre 12.6s pour la tail-rec). Je n'ai pas pu reproduire ce comportement ailleurs (sur des 3.11.2 et 3.10.2 elle est plus lente comme chez toi), mais je n'ai pas eu accès à une autre machine ayant 3.12.0. Je suis sur une architecture i686.

[TropMDR]

En pratique demander aux étudiants "évitez les tests d'égalité sur des constantes, le pattern-matching c'est plus rapide" aurait ici été un meilleur conseil (et moins nuisible à la lisibilité) que "faites une version tail-récursive". Avec des raisonnements comme ça on en arrive à écrire "if .. else if .. else if ..." en PHP plutôt que switch, parce que ça va plus vite.

Le pattern-matching plus rapide ???? Le pattern-matching comme tu viens de l'écrire, ce n'est rien de plus qu'un test d'égalité. La preuve :

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
30
31
32
33
34
35
36
37
38
TropMDR % ocaml -dlambda
        Objective Caml version 3.12.1
 
# let rec ntr_pow x = function
| 0 -> 1
| y ->
  let xy2 = ntr_pow x (y / 2) in
  if y mod 2 = 1 then
    xy2 * xy2 * x
  else
    xy2 * xy2              ;;
(letrec
  (ntr_pow/1038
     (function x/1039 y/1040
       (if (!= y/1040 0)
         (let (xy2/1041 (apply ntr_pow/1038 x/1039 (/ y/1040 2)))
           (if (== (mod y/1040 2) 1) (* (* xy2/1041 xy2/1041) x/1039)
             (* xy2/1041 xy2/1041)))
         1)))
  (apply (field 1 (global Toploop!)) "ntr_pow" ntr_pow/1038))
val ntr_pow : int -> int -> int = <fun>
# let rec ntr_pow x y =
  if y = 0 then 1 else
  let xy2 = ntr_pow x (y / 2) in
  if y mod 2 = 1 then
    xy2 * xy2 * x
  else
    xy2 * xy2            ;;
(letrec
  (ntr_pow/1042
     (function x/1043 y/1044
       (if (== y/1044 0) 1
         (let (xy2/1045 (apply ntr_pow/1042 x/1043 (/ y/1044 2)))
           (if (== (mod y/1044 2) 1) (* (* xy2/1045 xy2/1045) x/1043)
             (* xy2/1045 xy2/1045))))))
  (apply (field 1 (global Toploop!)) "ntr_pow" ntr_pow/1042))
val ntr_pow : int -> int -> int = <fun>
#

Tu remarqueras que les deux versions sont rigoureusement pareil, à ceci près que deux branches d'un test sont inversés (et que c'est un tests différent au lieu de égal). En gros, si ta version est plus vraiment plus rapide (que ce n'est pas dans le bruit, j'avoue ne pas avoir testé), c'est parce qu'un test en avant est prédit comme n'étant pas suivit par un prédicteur de branchement sur les archis "normales". Donc effectivement, il "vaut mieux" dans une boucle serrée mettre la branche la plus souvent prise dans le then plutôt que dans le else, et c'est sans doute pour ça que le pattern matching est compilé dans ce sens.

Donc nan, je te déconseille assez fortement de dire aux élèves que le pattern-matching est plus rapide que la comparaison à des constantes...

[Cacophrene]

Bonsoir le forum,

Je me permets d'ajouter mon grain de sel. Pour un problème donné, un programmeur expérimenté adopte généralement une démarche en trois étapes. Tout d'abord, il se familiarise avec le problème, essaie lui-même quelques cas simples pour bien cerner la nature du problème et les difficultés qu'il aura à surmonter, et surtout, se documente pour choisir d'emblée l'algorithme le plus efficace (inutile de réinventer la roue... et on n'est pas pointu dans tous les domaines !). C'est généralement cette démarche que l'on essaie tant bien que mal de faire appliquer aux étudiants de licence, en info comme dans d'autres disciplines, avec le succès que l'on sait...

Vient ensuite la deuxième étape, au cours de laquelle le programmeur implémente l'algorithme dans le langage de son choix. Il utilise alors généralement toutes les ressources à sa disposition, ou plus exactement toutes celles qu'il maîtrise. S'il est sage, il évite les optimisations a priori qui ont de bonnes chances d'être inutiles ou inadaptées, d'obscurcir son code, d'entraver le débogage et donc en définitive de réduire sa productivité. Si c'est un bon programmeur, son code source est propre et ne contient rien de plus que le strict nécessaire (avec, si c'est important, ce qu'il faut pour permettre au code d'évoluer). À ce stade, on pourrait presque recopier le code et le donner comme « solution type » aux étudiants dont je parlais plus haut.

C'est souvent là que l'on s'arrête dans le cadre d'un enseignement. Vient cependant, dans la vraie vie, la troisième et dernière étape, qui n'est autre que la confrontation avec le réel. C'est là que le code est confronté aux données en taille réelle, et c'est généralement à cette occasion que l'on identifie des goulots d'étranglement. Les portions de code incriminées sont alors inspectées et réécrites sous une forme plus efficace, mais hélas souvent moins naturelle, moins intuitive et moins élégante. Le code gagne en efficacité d'exécution et perd en clarté, ce qui oblige le programmeur à le commenter abondamment. Quelquefois même, le programmeur choisit d'adopter un langage comme le C ou même l'assembleur pour maximiser les performances. Tout ceci a un prix sur la maintenabilité du code, sa portabilité, etc.

Tout ça, vous le savez mieux que moi et l'avez déjà plus ou moins dit dans ce fil et dans d'autres. Je reste malgré tout étonné de voir si souvent associées les notions de récursivité terminale et d'optimisation. Certes, l'écriture de fonctions tail-rec permet d'optimiser un code source (notamment votre exemple d'exponentiation rapide). Mais quelquefois, c'est encore pire que ça : la version tail-rec est tout simplement la seule à donner un résultat ! Et ce n'est pas tout, comme le souligne Gasche, à l'autre extrémité, l'abus du tail-rec peut facilement devenir un vice et conduire à des codes quasi pathologiques. L'auteur de l'exercice aurait été mieux inspiré s'il avait pris un exemple qui sature rapidement la pile... le tail-rec aurait été non seulement plus efficace, mais aussi immédiatement légitime.

Bref, je reste convaincu qu'il faut avant tout enseigner aux étudiants et raconter sur ce forum ce qu'il convient de faire pour obtenir un code clair, lisible et correct. Ensuite, tenant compte de l'âge du capitaine et de ses aspirations, nous pourrons aussi lui indiquer comment écrire un code plus rapide, même s'il faut pour cela lui présenter quelques lignes pas très sexy. En cela je rejoins l'avis de TropMDR. Quoi qu'il en soit, il reste tout de même légitime de questionner la pertinence des optimisations demandées.

Pour le code lui-même, vous avez essayé de réécrire avec Num et des opérations bit à bit, en plus du tail rec, ça change quelque chose ? Pour le pattern matching il me semble qu'OCaml le transforme en if... then... else donc pas de gain à espérer ? Je ne sais pas. Le gain c'est aussi peut-être le gain en temps de vie du programmeur.

En tout cas merci d'avoir lu mon message laborieux jusqu'à son terme.

Cordialement,
Cacophrène

[TropMDR]

Je suis globalement d'accord avec ce qu'avance Cacophrene. Je tiens néanmoins à souligner un ou deux petites choses:

Effectivement, dans la "vraie vie", c'est une bonne chose de ne pas tenter de réinventer la roue. Cela ne signifie pas que c'est forcément une bonne chose pour l'enseignement ! Je pense qu'un élève doit avoir un jour écris une dichotomie, un trie rapide, un tri fusion, etc, etc, etc, même si ça existe évidement dans plein de bibliothèques.

Ensuite pour la pertinence de l'exercice, et le fait qu'il aurait été "plus judicieux de prendre un exemple explosant la pile", peut être que justement le but de l'exercice était, après avoir épuisé 42 exemples de "oh, sans tail rec ça marche pas, avec ça marche", de montre que c'est aussi utile pour autre chose (écrire une boucle serrée vs. un pile d'appels de fonctions), puis peut être même de présenter les raisons matérielles qui font que c'est mieux (on peut rêver). N'allons pas trop critiquer sans savoir

Et pour fini, si on veut un jour que les élèves puissent aborder la troisième phrase, celle de l'optimisation, il va bien falloir un jour leur faire optimiser des choses Histoire de leur apprendre les différentes techniques, quels sont les paramètres qui entrent en jeu, etc etc.

Après hein, je vous rassure, si un jour j'ai une exponentiation rapide à écrire, vu que ce ne sera pas sur des entiers ou des flottants (les fonctions existent déjà), mais par exemple sur des matrices, je n'irais pas m'embêter à faire une version tail-rec puisque la multiplication elle même sera *beaucoup* plus chère que les appels de fonctions, et donc effacera tout intérêt, alors que le code est nettement moins clair avec un accu !