Journal pythran rampe

Posté par (page perso) . Licence CC by-sa
23
16
juil.
2012

Le titre « pythran est en marche » me paraissait bizarre pour un outil qui a trait aux serpents…

Dans ma folie bienheureuse, et faisant fi des avis pessimistes, j'ai tenté de passer un code résolvant le problème des Nreines dans la moulinette pythran. Après de nombreux hacks optimisations, les résultats tombent:

  • python: 1.34s
  • pypy: 0.56s
  • nuitka: 1.34s
  • shedskin: 0.61s
  • pythran: 0.32s

\o/ le bébé s'en sort bien.

Pour être honnête il faut bien avouer que pythran ne supportant pas encore les paramètres par défaut dans les fonctions ni les generator expression, le code d'origine, tiré de unladden swallow a été légèrement modifié.

Chose amusante (c'est comme le gars qui se prend un seau sur la tête, c'est marrant quand ça arrive aux autres), shedskin demande une petite modification du source car il n'aime pas qu'un type NoneType et int cohabitent, comme dans

def foo(l, a=None):
    if a is None:
        a=len(l)
    ...

pythran s'en sort pas trop mal pour le coup, en utilisant une classe semblable à boost::variant spécialisée pour le cas du None.

Pour la petite histoire (après tout ceci est un journal, on peut lui raconter des histoires), le code généré par pythran était initialement très mauvais, à cause de :

  1. la gestion des subscripts
  2. la gestion de la mémoire

Pour 1. si on passe son temps à créer des sous tableaux copiant des parties du tableau initial alors qu'on y accède qu'en lecture, on est mal barré. La soluce classique - un peu comme quand on fait des coupes sur une matrice 3D - c'est de générer un objet proxy qui mémorise les paramètres de la coupe et surcharge les opérateurs [] et les méthodes begin() et end() pour faire croire qu'elle possèdent des données qu'elles n'ont pas.

Et pour le 2. l'utilisation de boost::pool m'a donné une accélération satisfaisante, mais si quelqu'un a mieux, je passe quand même 20% du temps dans ce cas (callgrind à l'appui) à trifouiller la mémoire et allouer des petits tableaux dont je ne connais la taille qu'à l'exécution.

  • # mais alors?

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

    Pour la petite histoire (après tout ceci est un journal, on peut lui raconter des histoires), le code généré par pythran était initialement très mauvais

    ça veux dire que tu as ensuite modifié le code c++ généré ou j'ai rien compris (parce que sinon, le benchmark est un peu beaucoup biaisé, quand même…)

    Ceci n'est pas une signature

    • [^] # Re: mais alors?

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

      mouarf l'aut'

      Bah non j'ai sorti l'huile de coude et j'ai optimisé le générateur de code, avec optim' mises dans le journal :-)

      • [^] # Re: mais alors?

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

        Ah oui c'est comme les pilotes de carte graphique qui sont optimisés pour un benchmark précis.

        • [^] # Re: mais alors?

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

          Je ne pense pas :-)
          C'est juste que ce benchmark mettait en avant le mauvais comportement de pythran en cas de création de nombreux tableaux.

      • [^] # Re: mais alors?

        Posté par (page perso) . Évalué à 1. Dernière modification le 16/07/12 à 21:38.

        ha ok… bon je m'étais couvert grâce à l'option 2 (j'ai rien compris). Donc hé ben bravo, d'autant que ça me donne l'occasion de découvrir cet outil que je ne connaissais pas!

        Ceci n'est pas une signature

  • # allocation de tableau

    Posté par . Évalué à 4.

    Concernant la gestion de mémoire, cela dépend de la durée de vie des tableaux en question. Si tu fais des agrandissements tu peux tenter le mmap et remap, mais cela fonctionne uniquement par tranche de 4ko, par contre, l'agrandissement doit être bien plus rapide, qu'une nouvelle allocation suivi d'une copie.

    Si la duré de vie des tableaux est courte, je ferais simplement une zone mémoire avec une gestion de pile (comme le gc mineur de ocaml) en utilisant mmap pour l'allocation de chaque pile.

    "La première sécurité est la liberté"

    • [^] # Re: allocation de tableau

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

      Je me demande si il ne vaudrait pas mieux faire les optimisations du cotés du programme en python, au lieu de l'interpréteur / convertisseur / compilateur.

      Envoyé depuis mon lapin.

      • [^] # Re: allocation de tableau

        Posté par . Évalué à 3.

        Si les fonctions de base sont lentes, tu ne pourras jamais rien faire avec le langage.

        "La première sécurité est la liberté"

    • [^] # Re: allocation de tableau

      Posté par . Évalué à 2.

      Tu est en train de faire un traducteur/compilateur. Tu ne peux vraiment pas présager la durée de vie de tes variables, ni comment elles vont être utilisées. Tu peux juste faire des suppositions en l'air… ou tenter d'éliminer des accès au tableau, mais ça c'est plutôt le rôle du compileur C++ dans ce cas.

      Et parce que python n'a même pas de notion de tableau mais plutôt de listes, si tu veux représenter une liste python de manière contiguë avec des mmap, attend toi à des représailles si ton code python insère souvent des éléments en plein milieu.

      • [^] # Re: allocation de tableau

        Posté par . Évalué à 3.

        Et parce que python n'a même pas de notion de tableau mais plutôt de listes, si tu veux représenter une liste python de manière contiguë avec des mmap, attend toi à des représailles si ton code python insère souvent des éléments en plein milieu.

        Les listes de Python sont des tableaux dynamiques.

      • [^] # Re: allocation de tableau

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

        Tu ne peux vraiment pas présager la durée de vie de tes variables, ni comment elles vont être utilisées. Tu peux juste faire des suppositions en l'air…

        Curieux, j'aurais dit tout le contraire. Prenons un exemple

        def higher_frequency(l,n):
          """Assumes l contains n kind of values."""
          histo= [0]*n
          for v in l:
            histo[v]+=1
          return max(histo)
        
        

        Le compilateur a toutes les informations pour décider que histo est un tableau avec une durée de vie faible, qu'il n'est jamais aliasé et que sa taille ne change pas après sa définition. Au lieu d'utiliser une classe tableau générique (implémentant un compteur de référence etc) on peut basculer sur un tableau natif.

        Pythran ne le fait pas …

      • [^] # Re: allocation de tableau

        Posté par . Évalué à 2.

        Tu est en train de faire un traducteur/compilateur. Tu ne peux vraiment pas présager la durée de vie de tes variables, ni comment elles vont être utilisées.

        Les compilateurs qui génèrent du code statiques font de l'élimination de variables non-utilisées et font de la recopie de valeur s'ils peuvent justement parce qu'ils ont toutes les informations.

        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

        • [^] # Re: allocation de tableau

          Posté par . Évalué à 2.

          Même pas. Les compilateurs n'éliminent les variables que s'ils ont la garantie qu'elles ne seront pas utilisées. Si par exemple elles sont utilisées que si une certaine condition est fausse, et que tu ne peux pas garantir le résultat de la condition, et bien tu ne peux que faire des suppositions.

          • [^] # Re: allocation de tableau

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

            Dans ce cas, on peut quand même s'en sortir en déléguant l'évaluation de la condition à l'exécution, ce qui a quelques défauts (dont augmentation de la taille du code) mais pas mal d'avantages aussi.

            Un cas classique pour gérer l'aliasing:

            #include <stdint.h>
            void foo(size_t n,   float a[n], float b[n]) {
              // aucune garantie que a et b ne se chevauchent pas partiellement ou totalement
              for(size_t i=1;i< n ; i++) { // cette boucle n'est parallèle que si a et b ne se chevauchent pas
                a[i] = 2*b[i-1];
              }
            
            

            Dans ce cas un petit test dynamique permet de suppléer aux carences de l'analyse statique

            void foo(size_t n,   float a[n], float b[n]) {
              if( &a[n]<=&b[0] || &b[n] <= &a[0] ) foo_parallel(n,a,b);
              else foo_sequential(n,a,b);
            }
            
            

            icc fait ça à fond !

            • [^] # Re: allocation de tableau

              Posté par . Évalué à 2.

              Tu fait quand même une présupposition majeure : le code parallèle sera forcement plus rapide que le code séquentiel, ce qui reviens à peu près à dire que ton nombre d'élément est élevé. Alors que si ça se trouve, cette fonction ne sera jamais appelée avec des tableaux de plus de 10 éléments, et tout ces trésors d'optimisations seront vains.

              • [^] # Re: allocation de tableau

                Posté par . Évalué à 2.

                Pourquoi voudrais-tu que le code parralèle soit plus lent avec 10 élements qu'en mode scalaire ?

                "La première sécurité est la liberté"

                • [^] # Re: allocation de tableau

                  Posté par . Évalué à 2.

                  L'utilisation de threads a une coût.

                  Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                  • [^] # Re: allocation de tableau

                    Posté par . Évalué à 2.

                    Avant les threads, il y a les version SIMD. DE toutes façon, les threads n'ont d'intéret qu'à gros grain, sinon il y a trop de cycles perdus pour la gestion et pour la cohérence de cache.

                    "La première sécurité est la liberté"

  • # LLVM

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

    As tu envisagé d'écrire un frontend pour LLVM ?
    En passent par C++, tu perds sans doute pas mal d'informations qui pourraient être utile pour faire des optimisations.

    • [^] # Re: LLVM

      Posté par . Évalué à 2.

      Il me semble que pypy cible déjà LLVM.

    • [^] # Re: LLVM

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

      Il y a déjà pymothoa qui vise à faire ça.

      Deux arguments pour la génération de C++:

      1. Cela simplifie grandement la génération de code, le debug etc. D'après les test faits jusqu'à présent, c'est pas dégueux niveaui perf non plus :-)

      2. pythran vise à être compatible OpenMP (à faire à faire, ça devrait être prêt pour les PyconFR). Et là encore c'est plus facile à faire au niveau source qu'au niveau bytecode

      Sinon lire l'excellente thèse de Serge Guelton sur les atouts de la compilation source-à-source ;-)

      • [^] # Re: LLVM

        Posté par . Évalué à 2.

        Comment fais-tu pour le gc ? J'ai l'impression qu'il est impossible de faire un bon système de GC en passant par du C ou du C++. C'est une des raisons qui a fait choisir Ocaml de générer directement de l'assembleur.

        "La première sécurité est la liberté"

        • [^] # Re: LLVM

          Posté par . Évalué à 2.

          J'ai l'impression qu'il est impossible de faire un bon système de GC en passant par du C ou du C++.

          Certains diraient :

          J'ai l'impression qu'il est impossible de faire un bon système de GC.

          Mais ça doit être possible puisque c'est un point qui avait beaucoup était discuté pour la version 2011 du C++.

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

          • [^] # Re: LLVM

            Posté par . Évalué à 2.

            Les compilo C++ génère de l'assembleur pas du C. Ils ont donc le contrôle exacte de l'utilisation des pointeurs. Cela n'est pas le cas quand tu as un compilo de langage à GC qui génère du C.

            "La première sécurité est la liberté"

        • [^] # Re: LLVM

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

          Pour le moment, j'ai des compteurs de références sur chacun des conteneurs (liste / ensemble uniquement donc). Comme il n'y a pas de classes utilisateur, je ne pense pas qu'il soit possible de créer des références croisées.

          Ça suffit, non ?

          • [^] # Re: LLVM

            Posté par . Évalué à 2.

            bah, c'est un peu le degré zéro du GC mais bon :) Le problème est l'accès à ce compteur pour chaque manipulation de donné ou presque.

            Mais si tu arrives à utiliser un maximum la pile d'appel pour les objets temporaires, cela ne doit pas être trop pénalisant.

            "La première sécurité est la liberté"

      • [^] # Re: LLVM

        Posté par . Évalué à 2.

        On dirait que les softeux ont toujours autant de mal avec le hardware. J'ai à peine commencé la thèse qu'il y a quelques "imprécisions" :

            "La loi de Moore [Moo65] a été invalidée il y a cinq ans, quand les transistors sont devenus si petits que le silicium ne pouvait plus dissiper l’énergie libérée par l’activité des processeur utilisés à leur fréquence maximale."
        
        

        La loi de moore est une relation entre le temps et le prix d'un transistor unitaire : le nombre de transistore d'une puce double tous les 18 mois/ 2 ans pour le même prix. Cela n'a rien à avoir avec la performance, ni avec le "mur de la chaleur". D'ailleurs, si tous les cpus sont multicores, c'est bien grace à la continuation de la loi de moore.

             "Il est apparu que de nombreux studios de développement de jeux vidéos ont trouvé la ps3 et son architecture hétérogène trop difficile à programmer.[...] Celle complexité était peut-être de trop pour le développeur moyen."
        
        

        C'est surtout une histoire de cout de développement qui explose. Les moteurs de jeu peuvent aujourd'hui prendre 5 ans de développement. Il parait difficile d'augmenter encore le temps de développement, la compétence du développeur n'est pas tout.

        "La première sécurité est la liberté"

        • [^] # Re: LLVM

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

          On dirait que les softeux ont toujours autant de mal avec le hardware.

          Ça c'est sûr :-) trois années passées à m'y frotter (le moins possible) n'ont malheureusement pas apportées de grands changements :-(

          le nombre de transistors d'une puce double tous les 18 mois/ 2 ans pour le même prix.

          Il me semblait que c'était à surface constante, d'où problème de « mur de la chaleur » etc. Pareillement les moulti-cœurs ne changent rien au problème d'intégration.

          C'est surtout une histoire de cout de développement qui explose.

          Oui. La difficulté de programmation de l'archi n'y est pas étrangère, puisqu'il faut embaucher des développeurs spécialisés au lieu de développeurs généralistes.

          • [^] # Re: LLVM

            Posté par . Évalué à 2.

            Non, cela n'a jamais été à surface constante. http://fr.wikipedia.org/wiki/Loi_de_Moore

            "la complexité des semiconducteurs proposés en entrée de gamme doublait tous les ans à coût constant depuis 1959" (1965)

            "le nombre de transistors des microprocesseurs sur une puce de silicium double tous les deux ans" (1975)

            Le principe de microelectronique est d'avoir une grosse galette de silicium qui augmente de taille lentement (wafer), on doit être à 300 mm. Dessus on dessine avec un trait de plus en plus fin et donc avec des machines de plus en plus couteuse. Le coùt fixe augmente, mais le nombre de transistor sur le waffer augmente plus vite. A nombre de transistors fixes pour une puce, le nombre de puce augmente par wafer, d'ou la baisse de coute unitaire et l'explosion du prix des usines (on doit être à 10 G$/usine).

            Concernant les développeurs spécialisés, cela n'est qu'une question de formation. Ton développeur avec son architecture bizarre va forcément être moins productif qu'avec un système classique, quelques soit son niveau. Il existe un gros pdf d'un producteur de jeu qui parle de ça très bien. slides

            "La première sécurité est la liberté"

          • [^] # Re: LLVM

            Posté par . Évalué à 3.

            Il me semblait que c'était à surface constante, d'où problème de « mur de la chaleur » etc. Pareillement les moulti-cœurs ne changent rien au problème d'intégration.

            Techniquement la surface est constante, non ? Je veux dire, j'ai pas vu d'augmentation significative de la taille des puces qu'on met dans un PC. :)

            Concernant la programmation des PS3 & co:

            Le gros problème du Cell B.E. était surtout qu'à sa sortie (i.e. à la sortie de la PS3) il n'y avait pas de bonne chaîne de compilation pour développer sur la plate-forme. Quand le problème de programmabilité de la PS3 avait été soulevé à l'époque, j'en avais parlé à un pote qui avait bossé sur la PS2 pour faire du middleware à destination d'autres studios de dév. Sa réponse était en substance « Non mais c'est n'importe quoi, la PS2 aussi avait l'équivalent de 2 SPU. Simplement maintenant il y a plus de gens s'intéressant à comment on programme ces machines qu'avant, du coup la difficulté pour les programmer est plus largement connue. »

            Pour avoir eu à faire un peu de prog sur Cell et sur d'autres machines exotiques (pas de caches, juste des scratchpads, aka des mémoires locales sans mémoire virtuelle, etc.), je peux dire que oui, c'est assez compliqué, surtout si y'a pas d'outils pour aider. Depuis (mais hélas bien trop tard), des gens ont développé des chargeurs automatiques de code et données depuis/vers les SPU de la PS3 (une amélioration sur les code overlays, un truc qui avait été pas mal utilisé pour … MS-DOS et DR-DOS, par ex), des systèmes de cache logiciel aussi — qui permettent de proposer un système de « constance¹ » plus faible que ce qu'on utilise habituellement dans les architectures multicœur classiques, etc.

            Donc bien entendu que l'archi a un impact sur les perfs, mais c'est bien le problème de beaucoup d'archis en règle générale : elles viennent avec des trucs révolutionnaires, mais les architectes ne pensent pas suffisamment aux gens qui vont programmer ces trucs. Après, c'est la responsabilité du fabricant aussi de fournir les bons outils (chaîne de compilation, etc.) pour que ça soit suffisamment simple à utiliser.

            [1] « constance » est la meilleure approximation que j'ai pu trouver pour « consistency » (qui est différence de « coherency » ou « cohérence »).

Suivre le flux des commentaires

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