Journal Javascript plus rapide que python ! (une suite possible)

Posté par (page perso) .
Tags : aucun
24
7
juil.
2010

Bonjour, suite au journal de Kopec et au commentaire d'Axioplase ıɥs∀, je me suis amusé à tester l'algorithme pour trouver des nombres amis avec plusieurs langages : Python, C, Lisp, Lua et forth.



Voici les résultats que j'ai obtenu.



C                                            0.466      1

sbcl (compilé, optim, sans cons) 0.468 1
sbcl (compilé, optimisation) 0.511 1.09
sbcl (compilé, sans optimisation) 0.878 1.88
gforth-fast 1.025 2.19
sbcl (sans optimisation) 1.59 3.41
gforth 2.761 5.92
lua 7.377 15.8
python 29.877 64.1


Ce qu'on peut voir, c'est que le Lisp peut-être aussi rapide que le C avec quelques déclarations de types pour garantir au compilo que le type des nombres ne changera pas. Le Forth ne s'en tire vraiment pas mal pour un langage interprété. Et Lua commence à être un peu plus lent.



Là dessus, gaaaaaAab sort un nouvel algo en python qui écrase tout le monde ! Qu'a cela ne tienne testons le en C et en Lisp (flemme pour la version en Forth et Lua :) ). Voila les résultats :



C                                            0.002           1

sbcl (compil) 0.000 0 ?!?
python 0.073 36.5


Et là, les versions en C et en Lisp sont 36 fois plus rapide que la version en Python. Et surprise, on ne voit rien avec la version en Lisp.
On prend alors une loupe en exécutant le code 100 fois de suite.



                                                           C ref    Lisp ref

C 0.061 1 1.56
sbcl (compil) 0.039 0.64 1
python 3.037 49.8 77.8


Et la grosse surprise : la version en Lisp est presque 2 fois plus rapide que la version en C !!!



Bon, je sais, c'est juste un cas particulier et on ne teste que la vitesse d'exécution mais comme Axioplase ıɥs∀, je suis content d'utiliser le Common Lisp : un langage de haut niveau et qui déchire sa race pardon : qui peut-être très rapide :)



J'ai mis le code et les résultats ici : http://hocwp.free.fr/friend_bench.tar.gz . Pour verifier que j'ai pas fais n'importe nawak.


Pis, je serais vraiment curieux de voir ce que ça donne avec d'autres langages. Si quelqu'un n'a pas trop la flemme :)



PS : On n'est pas vendredi mais c'est les vacances pour certains == tous les jours vendredi.

  • # Correction mineure

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

    Avant que les puristes me tombent dessus, c'est dans un forum que la discution s'est déroulée.
  • # Pour le code lua

    Posté par . Évalué à 5.

    http://lua-users.org/wiki/OptimisingUsingLocalVariables

    Il faut utiliser les variables locales pour gagner en vitesse.

    Sur ma machine, avec utilisation de variables locales :
    real 0m18.339s
    user 0m17.366s
    sys 0m0.003s


    Sans :
    real 0m21.045s
    user 0m20.059s
    sys 0m0.007s

    The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

    • [^] # Re: Pour le code lua

      Posté par . Évalué à 6.

      Puis pour mettre un peu de JIT, LuaJIT (http://luajit.org/) en version 1.1.6.

      Variables locales :
      real 0m3.440s
      user 0m2.623s
      sys 0m0.003s


      Sans :
      real 0m4.894s
      user 0m3.556s
      sys 0m0.007s

      Il faudrait voir ce que ça donne sur la machine qui a fait les benchs. :)

      The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

      • [^] # Re: Pour le code lua

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

        Avec les variables locales, je passe de 7.099 à 5.891 et avec le luajit 1.716 sans les variables locales et 1.337 avec.
        On obtient des résultats vraiment intéréssants.
  • # Un bench vaut ce qu'il vaut

    Posté par . Évalué à 10.

    Et on ne peut donc jamais en tirer de vraie conclusion sur la vie réelle.
    Il faut savoir garder la tête froide devant ce genre de résultat. Je dirais que l'important c'est la différence de perfs sur les parties d'une application qui réclament normalement le plus de temps, là on peut voir les intérêts des différents langages.

    Si ce test avait été fait proprement, il aurait démontré qu'en fait c'est OCaml le plus rapide!

    --------------->[ ]
    • [^] # Re: Un bench vaut ce qu'il vaut

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

      Oui, un bench ne donne qu'une petite idée du langage. Celui la ne dit rien sur l'occupation en mémoire du programme ou la vitesse avec laquelle on peut développer une application plus complexe.
      Par contre je serais curieux de voir ce que donne OCaml sur ce genre d'algo (chouette je sens que je vais apprendre des choses :) .
    • [^] # Re: Un bench vaut ce qu'il vaut

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

      Ce genre de commentaire revient à chaque fois que quelqu'un réalise un bench, mais il me semble qu'il n'apporte rien.

      Certes, un bench vaut ce qu'il vaut, et les résultats peuvent ne pas être extrapolables d'une application à l'autre. Cependant, comme on ne peut pas développer toutes les applications dans tous les langages, c'est souvent le meilleur outil disponible pour estimer la performance d'un compilateur/interpréteur au moment de faire des choix technologiques.

      D'autre part, les résultats des nombreux benchmarks que j'ai pu voir sont remarquablement réguliers (du moins pour ceux qui sont bien réalisés), ce qui semble indiquer que les performances des différents environements sont assez stables d'une application à l'autre.
    • [^] # Re: Un bench vaut ce qu'il vaut

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

      J'ai fait le bench avec OCaml, et le code natif est plus rapide que le C compilé avec gcc sans optimisations, par contre il y a un facteur deux en faveur du C avec -O3.


      let entries = 10000

      let loop entries =
      let d = Array.make entries 1 in
      for i = 2 to pred (entries / 2) do
      let j = ref (2 * i) in
      while !j < entries do
      d.(!j) <- d.(!j) + i;
      j := !j + i
      done
      done;
      for i = 0 to entries - 1 do
      if d.(i) < entries && d.(d.(i)) = i && i <= d.(i) then
      Printf.printf "%i %i\n" i d.(i)
      done

      let () = for i = 0 to 100 do loop entries done


      Par contre c'est clairement pas une manière fonctionnelle d'écrire les choses, et habituellement, je n'utilise jamais les boucles for et while en OCaml.
      • [^] # Re: Un bench vaut ce qu'il vaut

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

        Et tu n'as pas utilisé d'optimisation avec OCaml ?
      • [^] # Re: Un bench vaut ce qu'il vaut

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

        Merci beaucoup. Sur ma machine, j'obtiens

        Pour 10000 éléments : 0.049s en Ocaml, 0.039s en Lisp, 0.058 en C et 0.017 en C(O3)
        Pour 100000 éléments : 0.674s en Ocaml, 0.531s en Lisp, 0.799s en C et 0.412s en C(O3)
        Pour 1000000 éléments : 41.512s en Ocaml, 41.483s en Lisp, 43.523s en C et 43.449s

        Pour 10000000 éléments sans la boucle x100:
        Fatal error en Ocaml, 5.480s en Lisp et segfault en C
        • [^] # Re: Un bench vaut ce qu'il vaut

          Posté par . Évalué à 2.


          $ time lua friend.lua
          6 6
          28 28
          220 284
          496 496
          1184 1210
          2620 2924
          5020 5564
          6232 6368
          8128 8128
          10744 10856
          12285 14595
          17296 18416
          63020 76084
          66928 66992
          67095 71145
          69615 87633
          79750 88730
          100485 124155
          122265 139815
          122368 123152
          141664 153176
          142310 168730
          171856 176336
          176272 180848
          185368 203432
          196724 202444
          280540 365084
          308620 389924
          319550 430402
          356408 399592
          437456 455344
          469028 486178
          503056 514736
          522405 525915
          600392 669688
          609928 686072
          624184 691256
          635624 712216
          643336 652664
          667964 783556
          726104 796696
          802725 863835
          879712 901424
          898216 980984
          947835 1125765
          998104 1043096
          1077890 1099390
          1154450 1189150
          1156870 1292570
          1175265 1438983
          1185376 1286744
          1280565 1340235
          1328470 1483850
          1358595 1486845
          1392368 1464592
          1466150 1747930
          1468324 1749212
          1511930 1598470
          1669910 2062570
          1798875 1870245
          2082464 2090656
          2236570 2429030
          2652728 2941672
          2723792 2874064
          2728726 3077354
          2739704 2928136
          2802416 2947216
          2803580 3716164
          3276856 3721544
          3606850 3892670
          3786904 4300136
          3805264 4006736
          4238984 4314616
          4246130 4488910
          4259750 4445050
          4482765 5120595
          4532710 6135962
          4604776 5162744
          5123090 5504110
          5147032 5843048
          5232010 5799542
          5357625 5684679
          5385310 5812130
          5459176 5495264
          5726072 6369928
          5730615 6088905
          5864660 7489324
          6329416 6371384
          6377175 6680025
          6955216 7418864
          6993610 7158710
          7275532 7471508
          7288930 8221598
          7489112 7674088
          7577350 8493050
          7677248 7684672
          7800544 7916696
          7850512 8052488
          8262136 8369864
          8619765 9627915
          9071685 9498555
          9199496 9592504
          9339704 9892936
          9363584 9437056

          real 2m3.019s
          user 1m44.610s
          sys 0m4.500s


          :)

          The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

        • [^] # Re: Un bench vaut ce qu'il vaut

          Posté par . Évalué à 3.

          Le 2ème algo. en neko [http://nekovm.org/index]

          var NB_ENTRIES = 10000000
          var HALF_NB_ENTRIES = NB_ENTRIES / 2
          var d = $amake(NB_ENTRIES)

          var i = 2
          while (i <= HALF_NB_ENTRIES)
          {
          var j = 2 * i
          while (j <= NB_ENTRIES)
          {
          if (d[j] == null)
          d[j] = 1 + i
          else
          d[j] += i

          j += i
          }
          i += 1
          }

          i = 1
          while (i <= NB_ENTRIES)
          {
          if (d[i] < NB_ENTRIES && d[d[i]] == i && i <= d[i])
          $print(i, " ", d[i], "\n")

          i += 1
          }


          real 0m48.915s
          user 0m39.157s
          sys 0m0.327s

          Erf…

          PS: J'ai ajouté HALF_NB_ENTRIES parce que j'ai vu dans le bytecode que NB_ENTRIES/2 était calculé à chaque itération.

          The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

          • [^] # Re: Un bench vaut ce qu'il vaut

            Posté par . Évalué à 2.

            Ch'uis chaud. La température dans l'apart. aussi.

            Comme j'avais l'impression que l'affichage des résultats prenait pas mal de temps, j'ai commenté la dernière boucle pour avoir une idée du temps nécessaire afin de remplir la table.

            real 0m36.748s
            user 0m36.238s
            sys 0m0.243s

            Pratiquement un tiers en plus pour l'affichage. :/

            On arrive à un temps légèrement supérieur (5s de plus avec l'affichage), sur un nombre de calculs dix fois plus grand et sur une machine moins puissante que celle qui a servie à exécuter les programmes (Archlinux sur un Celeron Tualatin 1,2 GHz).

            Je suis pris d'un doute soudainement.

            The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

            • [^] # Re: Un bench vaut ce qu'il vaut

              Posté par . Évalué à 2.

              > Pratiquement un tiers en plus pour l'affichage. :/

              on progresse, on progresse

              bientot tu prendras l'heure avant et après la partie intéressante de ton bout de programme et tu nous donneras la différence plutot qu'utiliser la commande time.
              • [^] # Re: Un bench vaut ce qu'il vaut

                Posté par . Évalué à 2.

                Et pour gagner encore plus de temps, on pourra aussi segmenter le crible en différents morceaux qui tiennent dans le cache L1 plutôt que de faire des accès tous les "i"ièmes éléments ! (aucune proximité spatiale ni temporelle sauf pour les petits i).

                par exemple, un code de crible d'Eratosthene http://joux.biz/algcrypt/PROGRAMS/Sieve_4-2.html à comparer avec le crible naïf http://joux.biz/algcrypt/PROGRAMS/Sieve_4-1.html
                • [^] # Re: Un bench vaut ce qu'il vaut

                  Posté par . Évalué à 2.

                  > on pourra aussi segmenter le crible en différents morceaux qui tiennent dans le cache L1

                  Ce qu'il faut c'est un alignement des données (+padding) afin que le CPU n'ait pas à décaler des octets pour accéder aux éléments et un code assez compact. Le code généré à partir du C doit être tout riquiqui, donc il ne pose pas problème. On doit, à vue de nez, tenir sur une trentaine d'instructions assembleur max pour l'algo.

                  L'optimisation -O3 est tentante mais elle se fait battre assez (trop ?) souvent par -Os.

                  ÀMHA le problème à résoudre ici est surtout un problème de pénalités suite à l'adressage d'une quantité importante de mémoire.

                  Si il me restait de la motivation pour ces choses là, j'aurais tenté de faire des tronçons de 100 000 éléments (à voir et à expérimenter) avec les données dans le code, puis stocker les résultats à la fin de tout les calculs du tronçon. Ça sur n boucles, sans malloc(), sans free(), il me semble que ça donnerait quelque chose d'assez intéressant.

                  The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

                  • [^] # Re: Un bench vaut ce qu'il vaut

                    Posté par . Évalué à 3.

                    Oui il s'agit bien de gérer les accès au cache de données, le cache d'instructions étant comme tu le dis sans doutes très petit.

                    Déjà on peut faire un calcul simple : si le cache L1 de données fait 32 KB (processeurs Intel) ou 64 KB (processeurs AMD), sachant qu'un entier fait 32 bits soit 4 octets, il faut segmenter le crible en tableaux de taille 32 768/4 = 8192 ou 65536/4 = 16 384 éléments.
                    • [^] # Re: Un bench vaut ce qu'il vaut

                      Posté par . Évalué à 3.

                      s/le cache d'instructions/le code généré/ mais vous aurez rectifiés de vous-même.
                      • [^] # Re: Un bench vaut ce qu'il vaut

                        Posté par . Évalué à 2.

                        d'ailleurs je viens de regarder ce que ça donne dans valgrind : valgrind --tool=cachegrind ./a.out > /dev/null

                        avec 100 000 éléments dans le tableau, j'ai environ 120 M accès au cache L1/D et parmi ces accès, 71 M de cache miss, soit 60% de miss environ, ce qui fait plutôt beaucoup. Le taux augmente quand on passe à 1M éléments.
                        • [^] # Re: Un bench vaut ce qu'il vaut

                          Posté par . Évalué à 3.

                          Ah oui, effectivement, je pensais naïvement – je suis resté bloqué à l'époque de mon valeureux P3 sauvé d'une destruction imminente alors qu'il était encore plein de vie – que le cache L1 avait subit une croissance au moins proportionnelle à celle du cache L2. J'avais donc écrit 10.000 éléments que j'ai modifié en 100.000.

                          C'est sûr que ça ne le fait pas à 100.000 éléments avec un cache à 32KB. Ni même à 10.000, d'ailleurs.

                          Ah, la joie d'aller combattre les cache-misses sur les CPU. Tout fout l'camp. :D

                          Merci pour les infos.

                          The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

                        • [^] # Re: Un bench vaut ce qu'il vaut

                          Posté par . Évalué à 4.

                          Je viens de retrouver le site qui m'avait servi de lecture de chevet il y a quelques paires d'années : http://www.agner.org/optimize/

                          Rhââ, de jolies histoires d'opimisation de boucles, de register stall…

                          The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

                    • [^] # Re: Un bench vaut ce qu'il vaut

                      Posté par . Évalué à 2.

                      J'ai pas regarder l'algo mais je pense qu'il faut aussi garder la place pour le résultat.
                      Les variables intermédiaires, si elles sont assez petites pourront être dans des registres.

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

              • [^] # Re: Un bench vaut ce qu'il vaut

                Posté par . Évalué à 2.

                Correction: je n'avais pas commenté la seconde boucle, juste la sortie à l'affichage.

                Il y a maintenant récupération de la date* (je ne sais pas faire autrement avec ce langage que je n'ai pratiquement jamais utilisé, la précision à la seconde devrait suffire) en trois lieux :
                – entrée de la première boucle
                – entrée de la seconde boucle
                – sortie du programme.

                J'ai fait tourner le programme dans une application VTE (sakura) et en console TTY.

                Dans Sakura, il y a 41 secondes pour la première boucle et 10 secondes la boucle de l'affichage (+ vérification des conditions). Dans un autre test il y a eu 10 secondes pour l'affichage et 42 secondes pour le calcul. On est pas à un arrondi de seconde près.

                En TTY, 41 secondes pour les calculs et 4 secondes pour l'affichage. Idem lors d'un deuxième test.

                C'est cohérent. J'essaierai de refaire les tests à la fraîche car il commence à faire horriblement chaud, ce afin de voir si ça revient aux 36 secondes de cette nuit.

                * http://nekovm.org/doc/view/date

                The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

            • [^] # Re: Un bench vaut ce qu'il vaut

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

              Ben oui, on test tout en même temps : affichage, temps de chargement, algorithme en lui même... C'est pour ça que ce test ne veux pas dire grand chose il donne juste une petite indication sur le langage.
        • [^] # Re: Un bench vaut ce qu'il vaut

          Posté par . Évalué à 1.

          En OCaml tu peux tenter d'augmenter l'inline et virer la vérification sur les tableaux (qui sur ce genre de programmes doit prendre du temps).

          Ce sont les options -inline et -unsafe de ocampopt (après tout si on compile en -O3 pour le C, autant tricher aussi en OCaml...)
  • # Plus d’infos !

    Posté par . Évalué à 9.

    Quels sont les compilateurs et optimisations ?

    Parce qu’en restant en C :
    nicolas:~/data/friend_bench% gcc toto2.c;time ./a.out>/dev/null;gcc -O3 toto2.c;time ./a.out>/dev/null
    ./a.out > /dev/null 0,08s user 0,00s system 97% cpu 0,078 total
    ./a.out > /dev/null 0,03s user 0,00s system 95% cpu 0,029 total
    • [^] # Re: Plus d’infos !

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

      J'ai utiliser gcc tout seul sans optimisations. Je test avec O3 dès que j'ai un peu plus de temps.
      • [^] # Re: Plus d'infos !

        Posté par . Évalué à 2.

        T'aurais pu attendre un peu avant de vendre la mèche! J'étais à deux doigts de tester chez moi...
    • [^] # Re: Plus d’infos !

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

      Bon ben avec O3, j'ai la même chose que sans pour la première version de l'algo.
      Par contre pour le deuxième algo je passe de 0.058 à 0.017. La version en Lisp reste à 0.038 donc elle se place entre le C sans optimisation et le C avec optimisation.
  • # code php :

    Posté par . Évalué à 5.

    code python porté à l'identique ; la version perl ne doit pas être bien différente à mon avis.

    <?php

    error_reporting(E_ALL);

    for($a=2;$a<=20000;$a++)
    {
    $sa=1;
    for($d=2;$d<=$a-2;$d++) {if ($a%$d==0) $sa=$sa+$d;}
    $b=$sa ; $sb=1;
    for($d=2;$d<=$b-2;$d++) {if ($b%$d==0) $sb=$sb+$d;}
    if ($sb==$a && $a<=$b)
    printf("a = $a ; b = $b\n");
    }

    ?>



    marc@lucid:~/Bureau/Dev/php$ /usr/bin/time php -q bench.php
    a = 6 ; b = 6
    a = 28 ; b = 28
    a = 220 ; b = 284
    a = 496 ; b = 496
    a = 1184 ; b = 1210
    a = 2620 ; b = 2924
    a = 5020 ; b = 5564
    a = 6232 ; b = 6368
    a = 8128 ; b = 8128
    a = 10744 ; b = 10856
    a = 12285 ; b = 14595
    a = 17296 ; b = 18416

    41.68user 0.02system 0:41.73elapsed 99%CPU (0avgtext+0avgdata 81808maxresident)k
    0inputs+0outputs (0major+5548minor)pagefaults 0swaps
  • # "x100 pour y voir clair"

    Posté par . Évalué à 10.

    Petite question sur ton x100 : as-tu lancé 100x l'exécutable (ou le script), ou as-tu rajouté à l'intérieur de l'algo une boucle x100 ?

    En effet, je pense que ça change pas mal : le résultat est largement influencé par le temps de lancement du runtime (ou et des libs ou des machines) de chaque langage dans le premier cas, et en fait totalement abstraction sur le 2nd.

    Il n'y a pas de bonne ou mauvaise solution (tout dépend de ce que tu veux mesurer), mais il serait intéressant d'avoir cette info.
    • [^] # Re: "x100 pour y voir clair"

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

      J'ai rajouté une boucle dans l'algo parce que j'était curieux de voir la vitesse du langage et non la vitesse à laquelle il se lance. D'ailleurs sur ce terrain là le Lisp est clairement perdant. Mais bon, la REPL permet de compenser ce temps de démarrage.
      • [^] # Re: "x100 pour y voir clair"

        Posté par . Évalué à 4.

        Sinon si tu veux augmenter les temps de calcul pour y voir plus clair et rendre un peu moins important le temps de démarrages, tu peux augmenter le nombre de paires amicales à trouver, les algos sont rarement linéaires donc ça peut grossir les écarts assez facilement.
        • [^] # Re: "x100 pour y voir clair"

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

          Très bonne idée. Voila ce que j'obtiens pour 100000 éléments pour le 1er algorithme.
          Python : 48m7.524s
          Lisp : 46.021s
          C : 46.012s
          • [^] # Re: "x100 pour y voir clair"

            Posté par . Évalué à 2.

            Un facteur 60, comme tes premiers résultats à peu prêt, c'est cohérent.
            • [^] # Re: "x100 pour y voir clair"

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

              Bon voila en poussant un peu plus loin le nombre d'éléments.

              Avec le 2eme algorithme :

              Pour 100000: Lisp = 0.005s C = 0.009s C(O3) = 0.006s
              Pour 1000000: Lisp = 0.409s C = 0.432s C(O3) = 0.407s
              Pour 10000000: Lisp = 5.469s C = Segmentation fault (normal à cause des indices du tableau)
              Pour 100000000: Lisp = 68.193s C = Segmentation fault
              Pour 1000000000: Lisp = Plein de warning à la compilation : on atteint la limite de l'implémentation actuelle et des fixnum qui est à 536870911.

              Je n'ai rien changer au code en Lisp (juste incrémenté nb-entries). Pour le code en C, je pense qu'il faut passer au malloc à la main et changer le type des indices.

              Sinon, voila les derniers nombres amis trouvé avec 100000000 éléments testés :

              (89477984 92143456)
              (90437150 94372450)
              (91996816 93259184)
              (93837808 99899792)
              (95629904 97580944)
              (96304845 96747315)
              (97041735 97945785)
      • [^] # Re: "x100 pour y voir clair"

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

        Correction le Lisp n'est pas si perdant que ça à condition de lui compiler le code avant. Ce que j'ai fais avec les dernières mesures que j'ai donné au dessus.
        En deux passes:
        $ sbcl
        Lisp> (compile-file "toto.lisp")
        $ time sbcl --noinform --load toto.fasl

        On obtient les temps donnés ici par exemple : http://linuxfr.org/comments/1142006.html#1142006
  • # Rosetta Code

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

    Apparemment ce problème n'est pas encore sur Rosetta Code [http://rosettacode.org/], ça pourrait être intéressant de l'y ajouter.
  • # Python et psyco

    Posté par . Évalué à 1.

    Psyco booste pas mal les performances de python

    time python toto.py
    17,45s user 0,01s system 97% cpu 17,903 total


    time python toto_psyco.py
    0,69s user 0,00s system 88% cpu 0,790 total
  • # Code lua toto2

    Posté par . Évalué à 5.


    local nb_entries = 10000
    local d = {}
    local i, j

    for i=2,nb_entries/2 do
    for j=2*i,nb_entries,i do
    d[j]= (d[j] or 1) + i
    end
    end

    for i=1,#d do
    if d[i] ~= nil and d[i] < nb_entries and d[d[i]] == i and i <= d[i] then
    print(i,d[i])
    end
    end


    real 0m0.099s
    user 0m0.050s
    sys 0m0.007s

    Ça roxe du ponayz, sachant que l'approche naïve (toto.lua) mettait 21 secondes sur la même machine.

    The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

    • [^] # Re: Code lua toto2

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

      C'est ça qui est rigolo : on s'extasie sur le premier algo avec le javascript plus rapide que le python, puis le Lisp plus rapide que les 2. Et tout le monde est mis d'accord avec un changement d'algo qui place le python en 1er loin devant les autres. Et enfin le Lisp et le C qui se tire la bourre laissant le python derrière.
      Tout ça pour dire que l'algo est vraiment le point central !
      • [^] # Re: Code lua toto2

        Posté par . Évalué à 2.

        vi. Pas la peine d'optimiser le code tant qu'on a pas poussé l'approche algorithmique dans ses derniers retranchements.

        à noter qu'il y a un appel à sorted inutile dans mon code python, scorie pas nettoyée d'une version intermédiaire.
        • [^] # Re: Code lua toto2

          Posté par . Évalué à 3.

          Tu peux également utiliser enumerate() dans la dernière ligne, ce qui donne:

          print [(i, v) for i, v in enumerate(d) if v < NB_ENTRIES and d[v] == i and i <= v]
          • [^] # Re: Code lua toto2

            Posté par . Évalué à 2.

            oué !
            je ne connaissais pas (encore) enumerate. C'est plus lisible, je vais m'en servir très vite :)

            sinon, précision utile pour le lecteur de passage, msieur_happy répond en fait au commentaire que j'ai posté dans l'entrée du forum sur le sujet :)
            (cf lien dans le corps du journal)
        • [^] # Re: Code lua toto2

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

          > à noter qu'il y a un appel à sorted inutile dans mon code python, scorie pas nettoyée d'une version intermédiaire.
          Oui. Sans le tri, on obtient 0.068s au lieu de 0.073s
  • # code perl - + benchmarks

    Posté par . Évalué à 2.

    De mon côté en recompilant je ne trouve pas vraiment la même chose:

    (En bouclant 100 fois)

    C (gcc -O3 toto2.c; time ./toto2 >out ) 0.017s 1
    lisp (toto4.lisp with loop) 0.037 2
    perl (time ./toto2.pl >out2 1.566s 92
    python (time python toto2_with_loop.py ) 1.807s 106


    toto2.pl
    #! /usr/bin/env perl

    use strict;
    use warnings;

    my $NB_ENTRIES = 10000;
    my $NB_LOOPS = 100;

    test() foreach ( 1..$NB_LOOPS);

    sub test {

    my @d = (1)x $NB_ENTRIES;
    my $mid = int($NB_ENTRIES / 2);
    my ($i, $j);

    for ($i = 2; $i < $mid; $i++) {
    for ($j = $i*2; $j < $NB_ENTRIES; $j += $i) {
    $d[$j] += $i;
    }
    }

    my $di;
    for ($i = 0; $i < $NB_ENTRIES; $i++) {
    $di = $d[$i];
    print "$i $di\n" if $di < $NB_ENTRIES && $d[$di] == $i && $i <= $di;
    }

    }
  • # go !

    Posté par . Évalué à 4.

    soyons modernes :)
    package main
    
    import "fmt"
    
    const n int = 10000
    
    func main() {
            var d [n] int;
    
            for i := 0; i < n; i++ {
                    d[i] = 1
            }
    
            for i := 2; i < n / 2; i++ {
                    for j := 2 * i; j < n; j += i {
                            d[j] += i
                    }
            }
    
            for i := 2; i < n; i ++ {
                    if (d[i] < n) && (i <= d[i]) {
                            if d[d[i]] == i {
                                    fmt.Print("(", i, d[i], "), ")
                            }
                    }
            }
            fmt.Print("\n")
    }
    
    bon, pas sûr qu'on puisse pas faire mieux, c'est limite mon premier essai en go. Chez moi, en faisant 50 itérations sur des entiers jusqu'à 1000000, go prend 15%/20 % de temps de plus que le C. (100 boucles sur 10000, c'est trop court, les fluctuations entre 2 essais sont trop importantes) Aussi, j'utilise le compilo go qui avait été fourni genre à l'annonce officielle du langage, la dernière version fait peut-être mieux
  • # Scala

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

    J'ai traduit littéralement les 2 versions Python en Scala:

    Version 1 :

    #!/usr/bin/env scala
    !#

    class Toto {
    for (a <- Range(2,100000)) {
    var sa = 1
    for (d <- Range(2,a-2))
    if (a%d == 0)
    sa += d
    var (b,sb) = (sa, 1)
    for (d <- Range(2,b-2))
    if (b%d == 0)
    sb += d
    if (sb == a && a < b)
    println(a+","+b)
    }
    }

    new Toto


    Version 2 :

    #!/usr/bin/env scala
    !#

    class Toto {
    //Pour ajouter la fonction "sort" à (x,y) comme dans le code Python
    implicit def tupl(t:Tuple2[Int,Int]) = new {
    def sort = if (t._1 > t._2) t.swap else t
    }

    val NB_ENTRIES = 1000000
    val d = Array.fill(NB_ENTRIES)(1)

    for (i <- Range(2, NB_ENTRIES / 2))
    for (j <- Range(2 * i, NB_ENTRIES, i))
    d(j) += i

    println ( for (i <- Range(0, d.length) if d(i) < NB_ENTRIES && d(d(i)) == i && i <= d(i)) yield (i, d(i)).sort )
    }

    new Toto


    Là ce sont les versions "script". Pour avoir une version pré-compilée en bytecode, enlever l'entête et remplacer "new Toto" par:

    object Pouet {
    def main(args:Array[String]) {
    new Toto
    }
    }

    Compiler avec scalac Toto.scala
    Exécuter avec scala Pouet


    Résultats avec 1M éléments :
    Python V1 : j'ai arrêté après 14 minutes
    Python V2 : entre 3.7s et 4s
    Scala V1 : environ 50 minutes
    Scala V2 : entre 1.3s et 1.6s
    Scala V2 compilé : entre 0.60s et 0.66s

    J'espère que ça va donner envie aux programmeurs Python qui voudraient passer à un langage qui a au moins la même expressivité que Python et qui est plus rapide et plus fiable (typage statique...) ;-)
    • [^] # Re: Scala

      Posté par . Évalué à 2.

      Généralement les programmeurs python adorent le duck typing...

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

      • [^] # Re: Scala

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

        Justement. Si on compare les deux versions (en indentant comme il faut), on peut voir qu'à quelques conversions syntaxiques près, on a le "même" code qu'en Python. On peut même se passer de la création d'une classe dans la version "script" en Scala.

        Exemples de conversion Python => Scala :
        "in" => "<-"
        "xrange" => "Range"
        indentation => accolades
        ...

        Et on gagne le typage statique, la compatibilité avec les biblio Java/Scala/autres langages sur la JVM, la rapidité, etc. tout en conservant le Duck Typing.
        • [^] # Re: Scala

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

          Typage statique et duck typing en même temps ? C'est pas un poil contradictoire ?
          • [^] # Re: Scala

            Posté par . Évalué à 2.

            Non. Typage statique c'est qu'une variable reste du même type tout au long de son cycle de vie. Typage dynamique c'est qu'une variable peut être réaffectée à n'importe quel type.

            Le duck typing c'est encore autre chose : le type est défini par un l'ensemble des méthodes et/ou attributs et leur signature d'un objet.

            Deux objets sont compatibles au niveau des types si ils sont compatibles au niveau de la signatures des méthodes, par exemple si t'as une fonction, ce qui est requis pour "variable" c'est d'avoir un type qui fournit la méthode cacul, et rien de plus. Son type est défini par ça -> elle fournit une méthode cacul.
            Ça peut être du typage statique si tu peux plus lui réaffecter n'importe quoi derrière, et c'est du "duck typing".

            fun fonction(variable) -> retourne variable.calcul()

            Regarde aussi inférence de types, c'est une technique qui permet de typer statiquement une variable à la compilation, même si quand tu écris ta méthode tu ne précise pas le type de ses paramètres. C'est une manière de faire de la généricité.
            • [^] # Re: Scala

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

              En Scala si tu veux utiliser le Duck typing, tu fais :

              def pouet(a: {def yeah}) {
              a.yeah
              }

              C'est-à-dire que la méthode "pouet" prend en argument n'importe quel objet ayant une méthode "yeah" (ne prenant pas d'argument et ne renvoyant rien, dans cet exemple).

              Après on utilise très rarement ce genre de code en pratique. Là où Scala ressemble à un langage de script, c'est principalement grâce à son système d'inférence de type, qui est très bien fait, et aussi grâce aux implicits qui permettent d'étendre des classes déjà existantes (à la Ruby).
            • [^] # Re: Scala

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

              Le problème vient probablement de définitions divergeantes sur la chose. Tout dépend de ce qu'on appelle type, typage statique et dynamique et duck typing. D'après la définition de Wikipedia, (que je partage), le duck typing est une technique utilisée dans les langages dynamiques, où l'on utilise sa liste de méthodes plutôt qu'un hierarchie de classes / mixin / interface autre pour déterminer si l'appel est valide ou pas.

              La programmation générique, et / ou l'inférence de type (qui n'est pas vraiment l'apanage des langages de script vu que ça vient plutôt de ML / haskell ...) sont si tu veux du "duck typing static", mais font pour moi partie du système de typage (voir typeclass en Haskell, feu concept en C++) . De plus, en général, la notion de typeclass / concept est un peu plus riche que l'existence d'une "méthode", et en générale une plus forte connotation sémantique. Ça permet d'éviter des choses étranges parce que des objets différents ont un nom de méthode en commun, mais avec des sémantiques absolument pas cohérentes.
              • [^] # Re: Scala

                Posté par . Évalué à 2.

                Pas vraiment, si je me trompe pas en Haskell la sémantique des méthodes n'est cohérente que si tu le veux bien, et par convention : les monades sont supposées repecter certains axiomes, mais rien dans le langage ne peut t'interdire de ne pas les respecter, faudrait que les axiomes soient explicitement déclarés dans le langage et qu'il existe un moteur de preuve.

                Sinon, j'ai simplifié, ce n'est pas simplement un nom de méthode, le duck typing, c'est aussi la signature, même si la signature est forcément moins informative que dans un système à typage plus contraignant.
                • [^] # Re: Scala

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

                  La signature dans un langage dynamique, ça se limite à peu près à l'arité de la fonction ce qui nous amène pas bien loin.

                  Pour les typeclass, on peut évidemment se tirer une balle dans le pied mais bon, on y peut pas grand chose (à par oui peutêtre rajouter un moteur de preuve dans le compilateur et un générateur de claque). Mais ça reste moins erreur prone puisqu'on explicite qu'on veut que ce "type" réponde à un certain typeClass (donc à une certaine sémantique), en l'implémentant d'une certain façon.
                  • [^] # Re: Scala

                    Posté par . Évalué à 2.

                    Tu peux faire le même genre de truc avec du duck typing dynamique, des gens ont implémentés des monades en python, par exemple.
                    • [^] # Re: Scala

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

                      Je n'en doute pas, enfin l'intérêt premier des monade c'est de garantir par le système de typage la présence (et surtout l'absence) de certaines action impures. Je ne vois pas vraiment sur de l'intérêt en python (à par pour montrer qu'on puisse le faire, ou rigoler sur la théorie des catégories)).
              • [^] # Re: Scala

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

                Ça tombe bien, Josh Suereth vient de publier un article qui explique comment implémenter l'équivalent des "type classes" d'Haskell en Scala : http://suereth.blogspot.com/2010/07/monkey-patching-duck-typ(...) Ça se fait en combinant les "structural types" :
                scala> def pouet(a:{def ping: String}) = println("kekidi? " + a.ping)
                pouet: (a: AnyRef{def ping: String})Unit
                
                scala> class Yop {
                     | def ping = "checku"
                     | }
                defined class Yop
                
                scala> val truc = new Yop
                truc: Yop = Yop@1c45484a
                
                scala> pouet(truc)                                                                                                                                         
                kekidi? checku 
                
                Avec les traits :
                scala> trait MyTypeClass {                                                                                                                                 
                     | def ping: String                                                                                                                                    
                     | }                                                                                                                                                   
                defined trait MyTypeClass 
                
                scala> def pouet(a:MyTypeClass) = println("kekidi? " + a.ping)                                                                                              
                pouet: (a: MyTypeClass)Unit  
                
                scala> pouet(truc)
                :14: error: type mismatch;
                 found   : Yop
                 required: MyTypeClass
                       pouet(truc)
                             ^
                
                Et avec les implicits. Si Yop supporte la type-class MyTypeClass, alors on définit un implicit comme ça :
                scala> implicit def yop_mtc(a:Yop): MyTypeClass = new MyTypeClass {
                     | def ping = a.ping
                     | }
                yop_mtc: (a: Yop)MyTypeClass
                
                Ce qui permet ensuite d'écrire, sachant que truc est de type Yop :
                scala> pouet(truc)
                kekidi? checku
                
    • [^] # Re: Scala

      Posté par . Évalué à 1.

      J'espère que ça va donner envie aux programmeurs Python qui voudraient passer à un langage qui a au moins la même expressivité que Python et qui est plus rapide et plus fiable (typage statique...)

      Ou alors ils peuvent utiliser Cython [http://cython.org/] pour certains morceaux de leur programme (typage statique possible et même conseillé pour obtenir des performances assez proches du C il parait).

      Cela dit, Scala semble être un langage intéressant, que je n'ai regardé que de loin sans le pratiquer. En fait, le soucis avec les langages sur la JVM me semble du côté de la consommation mémoire [http://shootout.alioth.debian.org/u32/benchmark.php?test=all(...)]. Constatation réelle ou non significative ?
      • [^] # Re: Scala

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

        Sur shootout, la version 2.7.7 de Scala est utilisée. Elle commence à dater. Il faudrait voir ce que ça donne avec la 2.8.

        L'utilisation mémoire de la JVM et le garbage collector utilisé se configurent. Si jamais la consommation mémoire devient un problème, il est possible de regarder de ce côté là.

Suivre le flux des commentaires

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