Les Mongueurs de Perl / Groupe de travail Articles / Conférences Perl

Nous rejoindre / SVN / Relecture / Rédaction / Planning / Liens /

Publications : Linux Magazine France, Perles, Brèves, Production, Comptes-Rendus, Interviews, Traductions, Spoofathon

• temps écoulé
• temps CPU utilisateur
• temps CPU système
• temps CPU utilisateur (processus fils)
• temps CPU système (processus fils)
• nombre d'itérations

C'est évidemment le temps CPU utilisé qui est l'information la plus intéressante quand on compare différents algorithmes ou techniques. Le nombre d'itérations donne une idée de la vitesse de chaque méthode.

Par défaut, le module Benchmark exporte les fonctions suivantes :

• timeit()

  Exécute $code $count fois et mesure la durée de son exécution :

      my $b = timeit( $count, $code );

  L'object $b renvoyé est de type Benchmark.

• timethis()

  Exécute un bout de code un certain nombre de fois :

      my $b = timethis( $count, $code );

  Si $count est négatif ou nul, ce ne sera plus un nombre d'exécutions mais une durée minimale pendant laquelle le code devra tourner. (0 signifie 3 secondes.)

  La différence de cette fonction avec la précédente est qu'elle a un certain nombre de paramètres optionnels (titre, format de sortie).

• timethese()

  Exécute plusieurs bouts de code un même nombre de fois :

      my $b = timethese( $count, \%code );

  %code est une table de hachage contenant les bouts de code à tester, et $b est cette fois une référence à un hachage contenant les objets Benchmark associés à chaque test, indexés par le nom du test.

      Benchmark: timing 10 iterations of clank, thwack...
           clank:  5 wallclock secs ( 4.80 usr +  0.02 sys =  4.82 CPU)
                  (warning: too few iterations for a reliable count)
          thwack:  2 wallclock secs ( 1.07 usr +  0.80 sys =  1.87 CPU)
                  (warning: too few iterations for a reliable count)

• timediff()

  Calcule la différence de temps d'exécution entre deux objets Benchmark, et renvoie un objet Benchmark utilisable par timestr().

• timestr()

  Renvoie une chaîne correspondant au résultat du calcul de timediff(). Ce sont les chaînes utilisées pour l'affichage des résultats :

      38 wallclock secs ( 30.07 usr +  1.90 sys = 31.97 CPU)

Toutes ces fonctions affichent leurs résultats sur la sortie standard.

             Rate  zlott   ouch  swish
    zlott  8.03/s     --   -98%   -98%
    ouch    333/s  4050%     --    -3%
    swish   345/s  4193%     3%     --

• List::Util::max()

  A priori, le plus rapide, puisqu'écrit en C.

• sub max { my $max = shift; $_ > $max and $max = $_ for @_; $max }

  Algorithme en O(n), on ne peut pas faire mieux algorithmiquement.

• sub max { my $max = shift; $max = $_ > $max ? $_ : $max for @_; $max } }

  Cette version devrait être un peu plus lente que la précédente, car l'affectation à $max est faite à chaque tour de boucle (dans le cas précédent, on profite du court-circuit de l'opérateur and).

• sub max { (sort @_)[-1] }

  Le plus lent, puisqu'il fait le tri de la liste complète et qu'on sait que les algorithmes de tri de Perl sont en moyenne en O(n log(n)).

  Il sera encore plus long pour des tris utilisant un bloc, comme expliqué dans l'article Tris en Perl de Jérôme Quelin, paru dans GLMF 48.

Pour réaliser un graphique de comparaison de la fonction max() avec gnuplot, nous aurons besoin de fournir un tableau de valeurs numériques (nombre d'itérations par seconde en fonction de la taille de la liste). Les affichages réalisés par Benchmark n'ont donc aucun intérêt pour nous.

Nous allons utiliser la fonction countit(), qui compte le nombre d'itérations d'un bout de code réalisées pendant un temps minimum et ne fait aucun affichage. C'est la fonction utilisée en interne par les fonctions que nous avons vu précédemment.

    use strict;
    use Benchmark qw( countit );
    use List::Util qw( max shuffle );

    # les 4 fonctions à comparer
    sub max_list_util  { max(@_) }
    sub max_sort       { ( sort { $a <=> $b } @_ )[-1] }
    sub max_perl_court { my $m = shift; $_ > $m and $m = $_ for @_; $m }
    sub max_perl_long  { my $m = shift; $m = $_ > $m ? $_ : $m for @_; $m }

    # le tableau à trier
    use vars qw( @t );
    my %code = (
        max_list_util  => sub { max_list_util(@t) },
        max_sort       => sub { max_sort(@t) },
        max_perl_court => sub { max_perl_court(@t) },
        max_perl_long  => sub { max_perl_long(@t) },
    );

    # un petit entête qui rappelle l'ordre des champs
    print join( " ", '#', sort keys %code ), $/;

    # Affichage logarithmique :
    # $n va prendre toutes les valeurs
    # entre 10 et 90 par incrément de 10,
    # entre 100 et 900 par incrément de 100,
    # entre 1000 et 9000 par incrément de 1000, etc.
    # et on termine par 1000000 pour boucler la liste
    for my $n (
        map( { my $m = $_; ( map { $_ * $m } 1 .. 9 ) }
             qw( 10 100 1000 10000 100000 ) ),
        1000000 )
    {
        # construit un tableau mélangé de $n éléments,
        # qui sera utilisé par toutes les fonctions max_...
        @t = shuffle 1 .. $n;

        my $str = "$n";
        for ( sort keys %code ) {

            # le code tournera pendant au moins 5 secondes et pendant au
            # moins 10 secondes si la liste contient plus de 100000 éléments
            my $b = countit( $n > 100000 ? 10 : 5, $code{$_});

            # la fonction countit() renvoie un object Benchmark ($b)
            # qu'on utilise pour calculer le nombre d'itérations par seconde
            $str .= " " . ( $b->[5] / ( $b->[1] + $b->[2] ) );
        }

        # affichage des données pour ce jeu de test
        print "$str\n";
    }

Ce programme est assez long à exécuter, puisqu'il va tourner entre 5 et 10 secondes par jeu de test (il y en a 46 fois 4, soit 184). La sortie du script est la suivante :

    # max_list_util max_perl_court max_perl_long max_sort
    10 129490.494296578 37575.0965250965 34128.677839851 59022.9249011857
    20 97861.111111111 26700.5747126437 22675.8964143426 38079.4171220401
    30 77597.8142076501 19775.0469043152 17195.0495049505 28267.1875
    40 65993.1818181817 16719.961612284 14092.3220973782 20720.527306968
    50 57475.1999999999 14827.485380117 12686.5346534654 16759.7999999999
    60 49918.4824902723 12291.2871287128 10101.5748031496 13199.6183206107
    70 43939.3442622953 10639.8452611218 8765.58935361213 11428.624535316
    80 39075.6385068764 9372.82809611834 7781.71846435097 9773.90476190476
    90 36536.7924528303 8488.98916967506 6792.44935543281 8629.77099236649
    100 33212.4271844665 8012.85988483688 6400.56603773589 7772.1062618596
    200 18874.5596868886 4265.09433962263 3406.50557620818 3528.5444234404
    300 12952.4344569289 2951.89620758483 2450.09746588696 2200.1872659176
    400 9554.8983364141 2155.55555555558 1722.36842105262 1516.15969581751
    ...

Nous disposons maintenant de données utilisables par gnuplot pour afficher l'image suivante, qui confirme nos prédictions :

On remarque quelques « bosses » dans la courbe. Celles-ci sont dues aux variations d'activité de la machine qui faisait tourner le script de calcul des valeurs. J'ai essayé de faire tourner le script à une période d'activité minimale de la machine, afin de réduire le nombre de ces artefacts et obtenir une courbe « lisse ».

À toutes fins utiles, voici le script gnuplot utilisé :

    reset
    set terminal png
    set out "max.png"
    set autoscale
    set logscale xy
    set title "Comparaison des implémentations de max()\n(Echelle logarithmique)"
    set xlabel "Taille de la liste"
    set ylabel "Nombre d'itéraions par seconde"

    # ordre des champs :
    # max_list_util max_perl_court max_perl_long max_sort
    plot \
        "max.dat" using 1:2 with lines title "max() de List::Util (XS)", \
        "max.dat" using 1:3 with lines title "$max > $_ and $max = $_ for @liste", \
        "max.dat" using 1:4 with lines title "$max = $max > $_ ? $max : $_ for @liste", \
        "max.dat" using 1:5 with lines lt 6 title "(sort @liste)[-1]"

• Benchmark(3)

  La documentation du module est beaucoup plus complète que cette perle, mais en anglais. ;)

• Mastering Algorithms with Perl, par Jon Orwant, Jarkko Hietaniemi et John Macdonald (O'Reilly)

  Les chapitres 1 et 4 donnent quelques exemples et conseils d'utilisation de Benchmark, dans le cadre des tris pour le chapitre 4. Le chapitre 1 explique aussi la notation O(N) pour la complexité des algorithmes.

Copyright © Les Mongueurs de Perl, 2001-2011 pour le site.
Les auteurs conservent le copyright de leurs articles.