IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Optimisation automatique de boucles


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut Optimisation automatique de boucles
    Bonjour tout le monde !
    Une question me trotte dans la tête depuis maintenant très longtemps.
    Est-il possible (existe-t-il) de faire un programme qui en entrée prend une série d'instructions haut niveau (voire même en C). Typiquement :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    int p, i;
    p=0;
    for (i=0 ; i<MAX ; ++i)
    {
      p+=2;
    }
    On peut clairement faire beaucoup mieux ^^. La question est donc, est-il possible d'avoir un algo qui soit capable de trouver, peut-être pas l'optimal, mais en tout cas qui se rapproche du code optimal ?

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Il faut regarder du coté des infrastructures de compilation, comme LLVM.

    Mais je ne pense pas que l'algo actuel de "loop strength reduction" de LLVM soit capable de remplacer cette boucle par une simple affectation p=2*MAX.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    Je vais regarder cela.
    Mais ça me parait pourtant imaginable de faire ce remplacement, non ?

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Ah si. J'etais de mauvaise foi. LLVM a optimisé la boucle.

    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    int main(int argc, char** argv) {
      int MAX=10;
      int p, i;
      p=0;
      for (i=0 ; i<MAX ; ++i)
      {
        p+=2;
      }
      return p;
    }

    Test en direct live:

    1. Aller sur --> http://llvm.org/demo/index.cgi
    2. Copier/Coller du code si dessus + Bouton "Envoyer"
    3. Résultat compilé par LLVM (et desassemblé):

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    define i32 @main(i32 %argc, i8** %argv) {
    entry:
    	ret i32 20
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    En revanche, on est obligé de lui mettre un code qui fonctionne en entrée, on ne peut pas lui donner juste une boucle ?

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par progfou
    En revanche, on est obligé de lui mettre un code qui fonctionne en entrée, on ne peut pas lui donner juste une boucle ?
    ?!?

    Bah il faut au moins un code C valide, sous entendu "compilable". De plus, pour "optimiser", il faut connaitre le contexte: le type des variables, les valeurs retournées, ...

    Par exemple, remplacer "MAX=10" par "MAX=argc" ne fait pas le meme genre d'optimisation ! Dans ce dernier cas, l'optimiseur effectuera le calcul au run-time (return argc*2), alors qu'avant il effectuait le calcul au compil-time (return 20).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Optimisation d'une boucle
    Par ccobaye dans le forum Macros et VBA Excel
    Réponses: 2
    Dernier message: 28/08/2008, 08h28
  2. [Optimisation]Améliorer ma boucle
    Par progfou dans le forum C
    Réponses: 3
    Dernier message: 13/04/2007, 10h00
  3. [Optimisation]Eviter les boucles imbriquées
    Par progfou dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 09/03/2007, 17h03
  4. [Optimisation] SQL et boucles
    Par schnito dans le forum PHP & Base de données
    Réponses: 75
    Dernier message: 24/03/2006, 16h20
  5. [Debutant] Optimisation d'une boucle
    Par Javatator dans le forum Langage
    Réponses: 3
    Dernier message: 25/10/2004, 18h50

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo