Journal Pythran : C++ pour les serpents

Posté par (page perso) . Licence CC by-sa
Tags :
26
5
déc.
2012

Salut à toi, mon petit journal
Ça fait bien longtemps que je ne t'ai pas parlé de mon petit bébé cybernétique, Pythran.

Tu te rappelles de lui ? C'est un convertisseur d'un sous ensemble du langage Python vers C++11. L'idée est de mutiler légèrement le langage Python (hop, plus de classes) et d'ajouter des contraintes de typage statique pour générer un module natif optimisé à partir d'un module écrit en Python.

Sommaire

  • Résumé des épisodes Précédents
  • Optimisations statiques
  • Projet Euler
  • Liens en folie

Résumé des épisodes Précédents

Pour ceux qui ont profité de leurs vacances, j'avais écrit quelques journaux sur le sujet, et les commentaires m'ont pas mal aidés, alors hop, les liens

Vous noterez les tentatives désespérées pour avoir des titres originaux. Hop une petite nimage de ma patte pour justifier le titre de celui-ci.

Optimisations statiques

Python, c'est tout dynamique et on peut pas faire grand chose en analyse statique dans le cas général (pensez donc, un zozo peux évaluer votre module dans un contexte différent en changeant les globales pour que l'identifiant int pointe sur l'intrinsèque float, ce qui va pas arranger nos histoires). Si on fige un peu les choses (comprendre on limite l'usage des modules à import ou __import__ et on oublie execfile et autres eval) on commence à pouvoir faire des choses intéressantes.

La plus grosse réalisation de Pythran dans ce domaine, c'est d'être capable de calculer si une fonction est pure (sans effet de bord, ni sur des globales ni sur les paramètres), ce qui a plein de conséquences amusantes. Par exemple

def fibo(n):
    return n if n <2 else (fibo(n-1) + fibo(n-2)

est pure, mais

def obif(n,l):
  if n > 0:
    l.append(n)

ne l'est pas.

Mais que faire de cette précieuse info ? On peut

  • décider si un map peut s'exécuter en parallèle (même si ce n'est pas toujours profitable)
  • faire profiter g++ de cette information précieuse
  • faire de l'évaluation partielle, du genre python fibo(42) # on peut évaluer ça à la compilation, mais attention au temps de compil :-)

Projet Euler

À la recherche de cas test, je suis tombé (sans me faire trop mal) sur http://www.s-anand.net/euler.html qui a la bonne idée de lister pleins de petits algos en python pour répondre à pleins de petits problèmes matheux. Déjà ça montre que Python c'est bien pour faire des algos tranquillou, et puis avec quelques modifs, on a pu gonfler la base de tests :-)

Liens en Folie

Y a pleins de trucs qui se passe en Python autour des modules natifs, alors pour les curieux, voilà le résultat de ma dernière pêche (attention, quelques liens sont un peu vieux, mais je les trouve tous intéressants)

  • Une bafouille du dev de Nuitka qui démonte le choix de C++11 par rapport C++03 comme back-end

  • un (long) fil sur la mliste de Cython concernant le support OpenMP

  • le projet de Haypo pour faire du constant folding de façon générique. Les problèmes rencontrés sont très instructifs

ssssssssssssssss fait le serpent

  • # Intéressant

    Posté par . Évalué à  6 .

    Je suppose que le but c'est de pouvoir coder plus vite grâce à la simplicité de Python et générer du code C++ qui une fois compilé tournera vite ?

    Par contre, si tu dis qu'il n'y a plus de classes, ça veut dire qu'il n'y a plus de notion d'objet dans ton langage Python-like ? Ça perd pas légèrement son intérêt du coup ?

    J'ai rien compris ?

    • [^] # Re: Intéressant

      Posté par (page perso) . Évalué à  2 .

      Je suppose que le but c'est de pouvoir coder plus vite grâce à la simplicité de Python et générer du code C++ qui une fois compilé tournera vite ?

      Oui :-) Dans la même veine que Cython, en moins intrusif

      Ça veut dire qu'il n'y a plus de notion d'objet dans ton langage Python-like

      C'est pas Python-like, c'est Python-embded mais c'est un détail. Tu as accès aux conteneurs de base (list/set/dict/tuple), à terme file, mais pas de classes utilisateurs. Tu peux avoir des classes au dessus (dans la partie non Pythran) et appeler le module devenu natif pour les parties gourmandes en calcul. Le but n'est pas de traduire tout Python, juste les parties gourmandes, qui n'ont pas forcément besoin de classe, comme l'illustre le lien sur le gars qui répond aux devinettes du projet euler sans utiliser de classes.

      Par exemple on a récemment convertit un petit code de simulation (~300SLOC), pas de classes, et un speedup de x50 à la clef.

      • [^] # Re: Intéressant

        Posté par (page perso) . Évalué à  1 .

        Est-ce que c'est pas aussi plus ou moins l'approche de NumPy ?

        • [^] # Re: Intéressant

          Posté par (page perso) . Évalué à  1 .

          Bah non… numpy c'est un module qui expose des structures de données optimisées (ndarray) pour le calcul scientifique et avec un coût de passage du monde python au monde natif quasi-nul et les fonctions pour travailler dessus.

        • [^] # Re: Intéressant

          Posté par . Évalué à  1 . Dernière modification : le 05/12/12 à 19:30

          Je ne pense pas NumPy, c'est un module mathématiques probablement écris dans un langage compilé nativement.

          Ce que propose Pytrhan c'est un compilateur pour un sous-ensemble de python.

          Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

          • [^] # Re: Intéressant

            Posté par (page perso) . Évalué à  1 .

            C'est ça.

            apt-cache show python-numpy
            
            

            Nous apprend qu'il y a des dépendances sur libgfortran3, libblas3gf | libblas.so.3gf | libatlas3gf-base ce qui annonce un peu la couleur :-)

        • [^] # Re: Intéressant

          Posté par . Évalué à  0 .

          Plutôt pypy non ?

  • # C++ oui mais pourquoi ?

    Posté par . Évalué à  1 .

    (hop, plus de classes)

    Du coup si on enlève la partie objet (sous ensemble purement impératif ?) quel est l'intérêt de générer du code C++11, pourquoi pas tout simplement du C ?

    Le but est il de trouver des solutions, ou bien des bonnes questions ?

    • [^] # Re: C++ oui mais pourquoi ?

      Posté par . Évalué à  8 .

      Les patrons (template), la surcharge, les flux, les conteneurs…

      • [^] # Re: C++ oui mais pourquoi ?

        Posté par (page perso) . Évalué à  7 .

        Oui ! Plus précisément

        Pour la lib standard

        • list -> std::vector
        • set -> std::unordered_set
        • dict -> std::unordered_map
        • tuple -> std::tuple (assez costaud celui là)
        • print(truc, muche) -> std::cout << truc << ' ' << muche

        Pour l'inférence de type

        decltype et declval font des merveilles

        Pour la gestion mémoire

        vive les std::shared_ptr

        Petit exemple

        def foo(a):
          b = bar
          return b() + a
        foo(10)
        
        

        qui devient (en simplifiant)

        struct foo {
          template<class T>
          decltype(std::declval<b>()() + std::declval<T>()) operator()(T&& a) {
            auto b = bar();
            return b() + a;
          }
        };
        foo()(10);
        
        

        La crème de la crème

        mais la crème, c'est les variadic templates qui permettent d'implémenter de façon élégante les fonctions intrinsèques de la lib standard du genre reduce et cie…

        • [^] # Re: C++ oui mais pourquoi ?

          Posté par . Évalué à  3 .

          Réponse super précise Merci !!

          C'est là que je vois que même si j'en fait de plus en plus, je ne suis encore qu'un ver de terre en C++ :-D

          Le but est il de trouver des solutions, ou bien des bonnes questions ?

          • [^] # Re: C++ oui mais pourquoi ?

            Posté par . Évalué à  7 .

            C'est là que je vois que même si j'en fait de plus en plus, je ne suis encore qu'un ver de terre en C++ :-D

            Le problème c'est que vu la complexité du langage c'est le cas de la plupart des développeurs..

            • [^] # Re: C++ oui mais pourquoi ?

              Posté par . Évalué à  6 .

              C’est surtout un problème de formation… on nous a tous appris c++ en nous parlant de classe, de P.O.O. alors que la force du langage vient de sa bibliothèque standard. L’approche objet n’est qu’un élément du langage. On peut avoir une approche « objet » ce qui est, pour moi, orienté data avec du C, du lua et même du c++. L’avantage de ce dernier, c’est que sa grammaire lui permet une écriture plus simple.

              Je verrai bien un cursus commençant par le langage, les opérateurs, la surcharge, les patrons puis étude de la STL. Ensuite quelques cours théorique sur l’approche objet (UML par exemple ou juste théorique), puis retranscrire les notions abordées en c++ pour appréhender sa grammaire. Et enfin, si le temps le permet, un petit tour du coté de boost.

  • # Plus de classes

    Posté par . Évalué à  5 .

    hop, plus de classes

    J'y vais de ma petite remarque à se sujet, je comprends que des classes dynamiques soient très compliquée à gérer, mais les classes « new-style » sont déjà bien plus simple, non ? Est-ce qu'il ne serait pas possible d'accepter les classes new-style qui ne dérive que de object (donc peu de polymorphisme et peu de dynamisme) ?

    Je suis dans ma tour d'ivoire (rien à foutre des autres, dites moi un truc pour moi), si je ne pose pas explicitement une question pour les 99%, les kévin, les Mm Michu alors c'est que je ne parle pas d'eux.

    • [^] # Re: Plus de classes

      Posté par (page perso) . Évalué à  1 .

      En théorie oui. D'ailleurs shedskin le fait.
      Deux points me gênent pour le moment :

      1. Gestion Mémoire :
        En utilisant l'hypothèse types non récursifs on peut se permettre une gestion simplifiée de la mémoire (par compteurs de référence). Bon, on peut toujours refuser les classes qui induisent des dépendances de type circulaire…

      2. Inférence de type :
        Le moteur d'inférence de type de Pythran a quelques limitations. Quand je rencontre un appel de méthode, je ne sais pas à quelle classe elle est rattachée. Quand l'ensemble des méthodes (i.e. celles des conteneurs) est connu, je m'en sors très bien, mais sinon, je pense que ça va être coton.

      • [^] # Re: Plus de classes

        Posté par . Évalué à  2 .

        J'ai du mal à voir pourquoi tu peux pas inférer les types des méthodes. Comment tu fait ton inférence de type avec tes opérateurs alors ? que ça soit en python ou en C++, les opérateurs et les méthodes, c'est la même chose.

        Au pire, il suffit juste de traduire tout les appels de méthodes en appels de fonctions.

        • [^] # Re: Plus de classes

          Posté par (page perso) . Évalué à  1 .

          mmmh, c'est un peu compliqué à expliquer, mais je me lance. Déjà tout est fonction, els appels de méthodes sont convertis en appels de fonctions. Prenons le cas de la fonction list.append. Les informations associées sont

          1. elle revoie None
          2. elle nous informe que le type de son premier paramètre self doit être compatible avec liste de . Je dis compatible parceque si on ajoute des int puis des float, au final on aura des float.

          ces informations sont spécifiées en Pythran par une forme de signature de l'intrinsèque.
          ensuite considérons, hors de son contexte (par exemple si la fonction n'est jamais appelée dans le module, on ne peut donc pas savoir le type des paramètres)

          class ique(object):
             def append(self, other):pass
          
          def foo(l,a):
            l.append(a)
          
          

          que faire pour append ? Je suis incapable de décider si c'est le append de list ou celui de ique. Quelles informations de type utiliser?

          Vu autrement, le problème est que je veux générer des fonctions c++ polymorphiques, et donc on ne manipule ques des types symboliques ce qui fait que quand j'ai un appel de méthode, je ne sais pas (jusque l'instanciation, mais qui arrive bien plus tard) quel est le type exact des objets que je manipule, je connais juste les relations entre les types.

          • [^] # Re: Plus de classes

            Posté par (page perso) . Évalué à  2 .

            Ben ajoutes un commentaire directive.

            def foo(l,a):
                #pythran:type:l:list
                l.append(a)
            
            

            ou sous forme de chaîne (peut-être plus accessible si tu utilises l'AST du compilo Python—je ne sais pas si les commentaires sont accessibles via celui-ci):

            def foo(l,a):
                _pythran = ["type:l:list"]
                l.append(a)
            
            

            Comme ça ton code reste exécutable par Python et Pythran peut trouver des informations complémentaires pour sa génération de C++.

            • [^] # Re: Plus de classes

              Posté par (page perso) . Évalué à  2 .

              C'est ce que fait https://github.com/numba/numba. (du moins pour la deuxième alternative). Tu ne trouves pas ça ultra moche ? Moi si. Bon ça garde la propriété « compatible python » mais je trouve ça très intrusif.

              Pour le moment on donne quelques directives pour les fonctions exportées

              #pythran export fibo(int)
              
              

              mais elles sont facultatives, auquel cas on génère un bon gros .h que l'utilisateur peut instancier comme il le sent. Donc on ne peut pas se servire de ses infos pour l'inférence de type.

              • [^] # Re: Plus de classes

                Posté par . Évalué à  2 .

                Je vois que Numba procure des facilités importantes pour intégrer la librairie compilée directement dans la code python, via des fonctions de fonctions et des annotations. Que conseilles-tu pour intégrer un module Pythran dans du code Python ?

                • [^] # Re: Plus de classes

                  Posté par (page perso) . Évalué à  1 .

                  Pour le moment, tu prends un module python, disons foo.py, tu l'annotes légèrement

                  #pythran export ma_fonction(int list, float set, int:str dict)
                  
                  

                  puis

                  pythran -O3 -DNDEBUG -g foo.py -o foo.so
                  
                  

                  et ensuite tu peux utiliser le module foocomme un module python normal, sauf que c'est le code natif qui s'execute

                  from foo import ma_fonction
                  
                  # là c'est le code natif qui s'execute si foo.so est dans le path
                  ma_fonction(range(10000), { 1./i for i in xrange(1,1000) }, { i, str(i) for i in range(10) })
                  
                  

                  l'avantage c'est que même si pythran disparait de ton environnement, tu touches rien à ton code et il continue de fonctionner. Le seul changement, c'est d'isoler les parties calcul intensif dans un module, mais on pourrait presque dire que c'est pas une mauvaise pratique d'ingénierie :-)

                  Remarque que rien n'empêche d'écrire un décorateur @pythran qui compile à la volée, mais le temps fuit sous mon clavier, et j'ai pas eu de demandes dans ce sens pour le moment.

                  Si tu as un code à passer, on peut en discuter sur Freenode #pythran ou pythran@freelists.org :-)

                  • [^] # Re: Plus de classes

                    Posté par . Évalué à  2 .

                    Je n'avais pas compris que c'était aussi simple. Le gain de vitesse est plutôt important :

                    #pythran export sumlist(int list)
                    def sumlist(l):
                        s = 0
                        for x in l:
                            for y in l:
                                s += x*y
                        return s
                    
                    

                    Sans Pythran

                    In [1]: import module
                    In [2]: l = range(10000)
                    In [3]: %timeit module.sumlist(l)
                    1 loops, best of 3: 8.35 s per loop
                    
                    

                    Avec Pythran -O3

                    In [1]: import module
                    In [2]: l = range(10000)
                    In [3]: %timeit module.sumlist(l)
                    10 loops, best of 3: 173 ms per loop
                    
                    

                    C'est curieux, Pythran -01 me donne des meilleurs performances, avec 97ms, idem pour -O2. Idem avec des listes plus grandes (testé avec 100000 éléments). Question de cache processeur ?

          • [^] # Re: Plus de classes

            Posté par . Évalué à  4 .

            que faire pour append ? Je suis incapable de décider si c'est le append de list ou celui de ique. Quelles informations de type utiliser?

            C'est ça que je comprend pas: qui à besoin de ces informations de types ? C++ n'en a pas besoin pour appeler des méthodes depuis un template. Tu peux écrire a.append(b) sans connaitre le type de a et b, et C++ s'en sortira tout seul. Tu peux même savoir le type de retour de a.append(b), savoir si elle garantie qu'elle ne lance pas d'exception, ou même savoir si la méthode append existe avec ce paramètre, et ce avant d'instancier le a.append(b) (qui de toute façon n'existe pas forcement). Tu peux juste pas connaître le type des arguments de base (à cause des templates et des surcharges…), mais tu peux tenter de les adapter avec des fonction/metafonctions intérmédiaires, ou des traits si elles sont fixées.

            La metaprogrammation en C++ est turing complete, je vois pas pourquoi il faudrai s'en priver.

            • [^] # Re: Plus de classes

              Posté par (page perso) . Évalué à  4 .

              Oui, oui, je fais déjà tout ça. Mon exemple n'était pas bon

              def foo(bar): bar.append(1)
              a= list()
              bar(a)
              print(a)
              
              

              traduit comme tu le proposes ça donnerait

              pythran::vector<MaisQuelType> a;
              bar()(a);
              pythran::print(a);
              
              

              L'info MaisQuelType == int vient de append caché dans foo. Et malheureusement je n'ai pas trouvé de moyen de faire remonter cette info au moment de l'instanciation, donc je suis obliger de mettre ça dans l'inférence de type interprocédurale… je ne sais pas si c'est plus clair comme ça ?

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.