+ Répondre à la discussion
Page 2 sur 3 PremièrePremière 123 DernièreDernière
Affichage des résultats 21 à 40 sur 43
  1. #21
    alex_pi
    Invité(e)

    Par défaut

    Citation Envoyé par gorgonite
    pas cool... pourtant l'optimisation existe belle et bien, j'avais pensé qu'elle serait déjà dans ocaml
    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 ?

  2. #22
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    octobre 2005
    Messages
    2 683
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : Singapour

    Informations forums :
    Inscription : octobre 2005
    Messages : 2 683
    Points : 9 012
    Points
    9 012

    Par défaut

    Citation Envoyé par Dark3
    Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.
    Je ne te demandais pas la solution mais juste un peu d'aide comme ce forum nous le propose quand on a un souci.
    Je me range du coté de gorgonite: le problème du Caml, c'est qu'on ne peut pas donner "un peu" d'aide.

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

    Citation Envoyé par alex_pi
    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 ?
    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).

  3. #23
    alex_pi
    Invité(e)

    Par défaut

    Citation Envoyé par pcaboche
    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).
    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 !

  4. #24
    Membre Expert
    Avatar de InOCamlWeTrust
    Inscrit en
    septembre 2006
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : septembre 2006
    Messages : 1 036
    Points : 1 265
    Points
    1 265

    Par défaut

    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.

  5. #25
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    pour l'algo je pensais à un truc du style

    Code :
    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
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  6. #26
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    pour l'algo je pensais à un truc du style

    Code :
    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
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  7. #27
    Membre Expert
    Avatar de InOCamlWeTrust
    Inscrit en
    septembre 2006
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : septembre 2006
    Messages : 1 036
    Points : 1 265
    Points
    1 265

    Par défaut

    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.

    Citation Envoyé par gorgonite
    ... 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
    Oui, on est d'accord.

  8. #28
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par InOCamlWeTrust
    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.


    ç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
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  9. #29
    alex_pi
    Invité(e)

    Par défaut

    Citation Envoyé par InOCamlWeTrust
    Pour information, ocamlopt n'optimise presque rien.
    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 !

    Citation Envoyé par InOCamlWeTrust
    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.
    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 Caml

    Vali valou !

  10. #30
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par alex_pi
    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.

    ça doit être là que je l'ai lu effectivement... où quelqu'un a parlé de ce papier pendant un de mes cours

    Citation Envoyé par alex_pi
    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 :-)

    il est clair qu'ocamlopt optimise plus que ghc par défaut...
    mais il est vrai aussi que -ccopt est parfois bien utile
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  11. #31
    Membre Expert
    Avatar de InOCamlWeTrust
    Inscrit en
    septembre 2006
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : septembre 2006
    Messages : 1 036
    Points : 1 265
    Points
    1 265

    Par défaut

    Citation Envoyé par alex_pi
    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 !
    C'est Xavier Leroy lui-même qui le dit.

    http://caml.inria.fr/pub/old_caml_si...numerical.html

    Citation Envoyé par Document
    Author: Xavier Leroy
    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.

    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.

  12. #32
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par InOCamlWeTrust
    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

    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...
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  13. #33
    Membre Expert
    Avatar de InOCamlWeTrust
    Inscrit en
    septembre 2006
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : septembre 2006
    Messages : 1 036
    Points : 1 265
    Points
    1 265

    Par défaut

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

  14. #34
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par InOCamlWeTrust
    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.

    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
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  15. #35
    Membre Expert
    Avatar de InOCamlWeTrust
    Inscrit en
    septembre 2006
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : septembre 2006
    Messages : 1 036
    Points : 1 265
    Points
    1 265

    Par défaut

    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.

  16. #36
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par InOCamlWeTrust
    C'était exactement le même code, la même commande, les mêmes commandes de compilation ?

    ben oui, tout pareil... mais ne te prends pas la tête pour cela, je demanderais moi-même quand je les verrais
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  17. #37
    Membre Expert
    Avatar de InOCamlWeTrust
    Inscrit en
    septembre 2006
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : septembre 2006
    Messages : 1 036
    Points : 1 265
    Points
    1 265

    Par défaut

    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.

  18. #38
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par InOCamlWeTrust
    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.


    pas trop, nan... le code asm généré par un compilateur est moche, à la limite de l'illisible, j'ai déjà donné durant mon stage
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  19. #39
    Membre Expert
    Avatar de InOCamlWeTrust
    Inscrit en
    septembre 2006
    Messages
    1 036
    Détails du profil
    Informations forums :
    Inscription : septembre 2006
    Messages : 1 036
    Points : 1 265
    Points
    1 265

    Par défaut

    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.

  20. #40
    Invité régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2012
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2012
    Messages : 7
    Points : 8
    Points
    8

    Par défaut

    Ton algorithme est assez lent, puisqu'il s'exécute en O(n²).

    Voici un algorithme linéaire :

    Code :
    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

+ Répondre à la discussion
Cette discussion est résolue.
Page 2 sur 3 PremièrePremière 123 DernièreDernière

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •