J'avoue ne pas bien voir comment tu veux optimiser ça, sachant que tu as besoin d'attendre la valeur de retour pour construire ta structure. Tu aurais un lien expliquant de quoi tu parles ?Envoyé par gorgonite
J'avoue ne pas bien voir comment tu veux optimiser ça, sachant que tu as besoin d'attendre la valeur de retour pour construire ta structure. Tu aurais un lien expliquant de quoi tu parles ?Envoyé par gorgonite
Je me range du coté de gorgonite: le problème du Caml, c'est qu'on ne peut pas donner "un peu" d'aide.Envoyé par Dark3
Si on apporte "un peu" d'aide, c'est qu'on a résolu le problème et donc ça n'a plus d'intérêt. Ce qu'il est important de comprendre, ce sont les principes de la programmation fonctionnelle (ce que gorgonite a essayé de faire). Le problème, c'est que quand on essaye d'inculquer ces principes, les gens se sentent agressés, ont l'impression qu'on se moque d'eux, ce qui est faux (en réalité, on essaye juste de savoir s'ils ont compris et non s'ils ont l'impression d'avoir compris, ce qui est totalement différent).
Ce que gorgonite a voulu dire (je pense), c'est que le compilateur est théoriquement en mesure d'optimiser ce genre de fonction (il existe un algo pour ce cas là), mais que l'optimisation n'a pas été implémentée en Caml (peut-être dans d'autres langages fonctionnels).Envoyé par alex_pi
"On en a vu poser les armes avant de se tirer une balle dans le pied..."
-- pydévelop
Derniers articles:
(SQL Server) Introduction à la gestion des droits
(UML) Souplesse et modularité grâce aux Design Patterns
(UML) Le Pattern Etat
Autres articles...
Je pense aussi, et justement, j'aimerais savoir de quel algo il parle, parce que comme ça, je ne vois pas dutout ce que l'on peut optimiser dans ce cas, et que ça m'intéresse donc !Envoyé par pcaboche
Pour information, ocamlopt n'optimise presque rien. Les seules "optimisations" faites concernent la récursivité terminale ainsi que l'ordonnancement des calculs entiers et flottants dans certains cas très précis, pour éviter à avoir à allouer sur le tas via le GC et optimiser le temps de calcul en exploitant les possibilités des processeurs et en réordonnant les instructions machines (mais seulement sur certains processeurs, pas sur les x86...). Il y a un document sur internet écrit par Xavier Leroy, mais je ne me souviens plus du lien... et sinon, il y a les sources !
Une autre optimisation désirable concernerait la chasse aux valeurs dans les fonctions pouvant être allouées de façon sûre sur la pile, comme en C, et non sur le tas.
When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.
pour l'algo je pensais à un truc du style
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 fact n = match n with 0 -> 1 |_ -> n * fact (n-1) ;; let fact2 n = let rec aux a b = match a with 0 -> b |_ -> aux (a-1) (a*b) in fact n 1 ;;
le but de cette méthode est de réussir à construire aux "automatiquement", ce qui est simple pour les cas d'appels "récursifs simples" avec des types de données connues (liste, entier) car on sait quoi faire dans l'accumulateur
pour l'algo je pensais à un truc du style
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 fact n = match n with 0 -> 1 |_ -> n * fact (n-1) ;; let fact2 n = let rec aux a b = match a with 0 -> b |_ -> aux (a-1) (a*b) in aux n 1 ;;
le but de cette méthode est de réussir à construire aux "automatiquement", ce qui est simple pour les cas d'appels "récursifs simples" avec des types de données connues (liste, entier) car on sait quoi faire dans l'accumulateur
Ca va pour des types scalaires pour lesquels les opérations sont commutatives, mais qu'en est-il pour des manipulations sur des listes, quand l'ordre des éléments doit être conservé ?
Quand je faisais de la géométrie algorithmique en OCaml, je devais manipuler de très grands jeux de données, des listes énormes pour lesquelles toute fonction récursive non terminale échouait lamentablement en Stack Overflow. Heureusement, l'ordre des éléments dans les listes que je manipulais n'avait pas vraiment d'importance, et donc je pouvais utiliser ce genre de méthodes ; je concaténais aussi en utilisant List.rev_append, extrêmement utile. Aujourd'hui, je travaille dans le domaine des maillages en C, donc le problème ne se pose plus.
Tout ça pour dire que je ne suis pas certain qu'il existe un algorithme pouvant transformer ce genre de problèmes de façon générale... mais je ne suis pas un expert en compilation non plus.
Oui, on est d'accord.Envoyé par gorgonite
When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.
Envoyé par InOCamlWeTrust
ça doit exister... mais l'algo serait NP-difficile
je parlais de la transformation d'une fonction primitive ne faisant qu'un appel récursif, et utilisant des types simples
pour ce qui est des listes, l'accumulateur est effectivement une solution qui inverse le résultat... il faut alors inverser en temps linéaire à la fin, si besoin il y a
Euh... Je me permets d'émettre un doute :-) Parce qu'un compilo qui n'optimise "presque rien" et qui arrive à des performance aussi proche du C en partant d'un langage fonctionnel, c'est de la magie noir :-) J'espère que Xavier Leroy ne va pas lire ton post, il risque de se faire une petite crise cardiaque ! Après, c'est vrai que le compilo n'a pas beaucoup évolué depuis 4 ans, donc il n'est sans doute pas à la pointe de la pointe en matière d'optimisation de derière les fagots, mais tout de même !Envoyé par InOCamlWeTrust
Recherche faite, ça s'appelle "récursion terminale modulo cons". Il y a eu un papier là dessus dans POPL (Principle of programming language) en 98, mais je n'ai pas encore eu le temps de jeter un oeil. Il semble que ça ait été discuté plusieurs fois sur la mailing list Caml, mais a priori sans jamais mener à quelque chose de concret. Si j'ai bien compris, le principe est de faire passer à la fonction appelée l'endroit où elle doit mettre son résultat ainsi que la valeur de retour. En gros dans le cas d'une liste, le premier appel connait la valeur de retour (le premier élément de la liste) et fait passer à l'appel suivant sa propre adresse, pour qu'il puisse modifier la référence, et ainsi de suite. Ca a l'air amusant :-) Et C'est émulable via la module Obj (beurk) de CamlEnvoyé par InOCamlWeTrust
Vali valou !
Envoyé par alex_pi
ça doit être là que je l'ai lu effectivement... où quelqu'un a parlé de ce papier pendant un de mes cours
Envoyé par alex_pi
il est clair qu'ocamlopt optimise plus que ghc par défaut...
mais il est vrai aussi que -ccopt est parfois bien utile
C'est Xavier Leroy lui-même qui le dit.Envoyé par alex_pi
http://caml.inria.fr/pub/old_caml_si...numerical.html
Si OCaml est si performant, c'est entre autres grâce à son Garbage Collector, plus efficace en moyenne que de lamentables appels à malloc(), et ses routines internes sur-optimisées.Envoyé par Document
Par contre, -ccopt n'a aucun sens si tu ne compiles pas des fichiers .c avec ocamlopt (avec GHC, je ne sais pas) : aucun code C n'est engendré par ocamlopt.
When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.
Envoyé par InOCamlWeTrust
d'expérience, je peux affirmer que c'est faux... pas plus tard que cette semaine, j'ai compilé avec ocamlopt -ccopt -02, et sur une moyenne pour 1000 exécutions, j'ai gagné 1s (l'exécution durant en tout 10s) sur le temps de calcul par rapport à ocamlopt tout court. et pourtant je ne passais pas par du code c...
ocamlopt ne crache pas du code C : pour m'être plongé dans les sources du compilateur (version 3.09.3) je peux l'affirmer ; tu as de plus le manuel qui l'explique très bien. Les temps d'exécution dépendent de plus de beaucoup de choses, et surtout du système ; si tu as des accès à des périphériques, tu ne peux déjà plus rien comparer, à cause du cache essentiellement (la première exécution peut être très lente mais la deuxième très rapide), et si ça swap, idem.
Si tu ne me crois pas, demande directement à la Caml Team, à moins qu'entre temps ils aient changé, mais ça m'étonnerait... ou qu'il y ait une subtilité dans le code, un passage qui m'ait échappé.
When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.
Envoyé par InOCamlWeTrust
merci, mais je sais relativement bien comment calculer un temps d'exécution réaliste pour un programme donné...
mon programme ne travaillait qu'en mémoire, sans aucun accès à un périphérique, et les données tenaient également en mémoire (100mo de données et 2Go de Ram sous un linux en ligne de commande en éteignant la plupart des démons non indispensables)... pour ce qui est de la mise en cache, sur une moyenne de 1000 exécutions consécutives, le phénomène a quand même du avoir lieu pour les deux programmes, donc cela ne compte pas vraiment
C'était exactement le même code, la même commande d'exécution, les mêmes commandes de compilation ?
Si je revois les mecs de Caml je leur poserai la question, mais ça m'a l'air très louche ton truc.
When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.
Je viens de poser la question ce matin dans le car à un mec du projet Gallium.
La seule explication plausible selon lui serait que l'option -O2 ait été passée en argument à l'assembleur et au linker, qui se seraient chargé d'effectuer de petites optimisations (certains assembleurs sont capables d'optimiser un peu le code).
Selon la personne, sur la mailing list de Caml des personnes auraient déjà constaté ce phénomène.
Sinon, si tu veux voir si le code engendré avec -ccopt -O2 est le même que celui engendré sans, tu peux prendre deux fichiers .ml, compiler avec -S, récupérer les deux codes assembleur et faire un diff dessus.
When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.
Ouais mais diff il s'en fout, lui, que le code assembleur soit moche !
Sérieusement : il faudrait faire un diff sur le code assembleur, puis sur les fichiers binaires pour voir si ils sont égaux au non.
Si les codes assembleur sont les mêmes mais que les fichiers objets ou exécutables sont différents, alors c'est que l'assembleur et/ou le linker ont pris en compte l'option -O2.
On m'a aussi un peu parlé des orientations futures concernant Caml et autres.
When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.
Ton algorithme est assez lent, puisqu'il s'exécute en O(n²).
Voici un algorithme linéaire :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 let _HASH_TABLE_SIZE = 997 (* taille de la table de hachage *) let delete_doublons l = let h = Hashtbl.create _HASH_TABLE_SIZE in let rec delete_rec = function | (a, _) :: l when Hashtbl.mem h a -> delete_rec l (* si a est déjà marqué, on le supprime *) | (a, _) as e :: l -> Hashtbl.add h a (); (* sinon on le marque *) e :: delete_rec l | [] -> [] in delete_rec l
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager