Caliper me : Ou pourquoi les microbenchmarks aident !

Contexte

Dans les news récemment

  • Guava 13.0 réduit la consommation en mémoire de plusieurs structures [source]
  • J’ai passé des tests d’algorithmie [source]

Premier point, on sait que Google est attentif sur les performances de ses librairies. Sur le deuxième point, ben j’ai finalement loupé un des exercices “timeboxés”, je n’ai pas eu le temps de le finir a temps, du coup le code soumis était 100 % foireux. Mais bon ce n’est pas le sujet du billet, ce qui est important c’est que j’ai fini après cet algo, puis je me suis rendu compte que celui-ci n’était pas optimal, il ressemblait à un algo en O(n2) O(n log n) (Merci Sam pour cette correction). Du coup j’ai repris le papier et le crayon, et je me suis rendu compte que je pouvais utiliser une technique similaire à celle que j’ai utilisé sur le premier algo du test (comment n’ai-je pas pu y penser à ce moment d’ailleurs ?).

De mémoire l’algo porte grosso modo sur le comptage de paires d’entier distante d’un nombre K dans un tableau A.

Ma première version :

Alors pourquoi je pense que cet algo n’est pas optimal : simplement du fait des boucles inbriquée, on dirait du O(n2) O(n log n) (voir ici pourquoi). Mais quand on parle de la performance ou de la complexité d’un algorithme il ne faut prendre uniquement compte de l’invariant mais aussi du jeu de données : quelle taille ? quelle distribution ? quel type de données ?

En effet un algorithme pour être efficace doit être adapté aux jeux de données qu’il aura à traiter et à l’usage qu’on en a ; peut-être à travers des paramètres ou des structures différentes, typiquement un des constructeur d’une HashMap prend des paramètres comme le facteur de charge et la taille initiale, on pourra choisir une TreeMap au lieu d’une HashMap si la recherche est un cas d’utilisation de la structure de donnée.

Bref du coup voilà à quoi ressemble la nouvelle version de cet algo :

Donc ici l’idée c’est de préparer dans un premier temps un dictionnaire  inversé basé sur un des entier et la distance demandée, en incrémentant pour chaque occurence. Ici une seule boucle for, car on parcours en entier le tableau. Dans un second temps on cherche les entiers qui correspondent effectivement à l’entrée de ce dictionnaire, et si oui on incrémente le compteur de paires. Là aussi une seule boucle sur le tableau donc O(n). Sachant qu’une HashMap a souvant une complexité de O(1) pour l’insertion et la recherche, a vue de nez l’algo est plutot pas mal.

Bon mais dans la réalité ca donne quoi, en effet comme Kirk Pepperdine et bien d’autres disaient : Measure ! Don’t guess !

Caliper me voilà !

Caliper est un outil codé par des personnes de chez Google, il est notamment utilisé par l’équipe en charge de Guava. On peut d’ailleurs voir dans les sources de Guava les benchmarks ici par exemple.

Avec un projet “mavenisé” on récupère la dernière version de caliper, la version 0.5-rc1 aujourd’hui.

Pour écrire un benchmark caliper il suffit d’étendre la classe SimpleBenchmark, puis d’écrire des méthodes public int avec le préfixe times et un paramètre répétition utilisé dans une boucle for. Pour passer des paramètres particuliers au benchmark on utilisera un ou des champs annoté(s) par @Param.

Enfin comme Caliper lance une nouvelle VM, fait quelques travaux pour chauffer la VM (warmup), etc, il faut pour l’instant lancer ces tests avec une commande manuelle :

La ligne de commande pourra varier suivant les besoins ; on peut notamment se rendre sur leur site pour y voir les options (le lien wiki est à ce jour en retard par rapport au code) à passer au Runner Caliper. Malgré la jeunesse du framework sa documentation parfois spartiate, le projet a de réelles forces et s’avère de plus en plus populaire dans le domaine. Bien que le développement de ce projet avance lentement, ce projet est aujourd’hui maintenu par des membres de l’équipe Guava.

Donc le benchmark que j’ai mis en place :

Dans le temps

Voilà il faut maintenant lancer le benchmark en ligne de commande. Et voici une partie de la sortie standard :

Donc en fait Caliper créé une matrice multi-dimensionnelle des différents paramètres et pour chaque coordonnée dans cette matrice lance le test, bref un Scénario.

On voit dans les mesures faites par Caliper le temps pris par chaque méthode, l’écart type, et le nombre d’essai. Enfin dans une deuxième partie Caliper donne un synopsis des différents run et en particulier une colonne très intéressante ‘linear time‘.

En observant le temps pris en fonction du nombre d’éléments pour chaque algo, on s’aperçoit que le temps pris par le premier algo augmente en effet par rapport au deuxième algo d’un facteur 5 qui augmente avec la taille du tableau. Bref on est loin d’un temps linéaire aka O(n).

Ce qui est aussi intéressant, c’est que le premier algo est plus efficace tant que le nombre d’élément dans le tableau d’entrée est inférieur à 100. Alors que la deuxième  qui utilise une structure plus élaboré ne montre des signes avantageux qu’à partir d’une centaine d’éléments. Ca me rappelle étrangement l’électronique ou les comportements des capacités et inductances changeant de nature lorsqu’on passe en haute fréquence.

Dans l’espace

Alors pour faire les mesures des allocations, on peut aussi utiliser caliper, mais à l’heure de l’écriture de ce blog, il faut faire quelques petites choses en plus.

  1. Caliper 0.5 RC1 vient avec le jar java-allocation-instrumenter-2.0.jar qui est sensé servir d’agent, cependant ce jar n’a pas été généré correctement pour servir d’agent. En fait il faut télécharger le jar allocation.jar de ce projet : http://code.google.com/p/java-allocation-instrumenter/ daté du 1 er février 2012.
  2. Avant de lancer le Runner en ligne de commande il faut ajouter la variable d’environnement ALLOCATION_JAR
  3. Enfin il est possible de lancer le même benchmark avec des tests sur la mémoire :

 

A noter : Ne pas renommer allocation.jar en autre chose, sans ça vous n’aurez pas d’instrumentation !

Ce qui donne le résultat suivant, quasiment la même chose, mais avec les infos sur les allocations mémoire.

C’est effectivement une information utile, la première version de l’algo, ne fait en fait qu’une seule allocation de 16B (donc en fait un seul objet), c’est à dire peanuts, on est dans du O(1) en complexité spatiale. La deuxième qui est notamment basée sur une HashMap alloue nettement plus d’objets, mais est définitivement plus rapide, on a on ici une complexité spatiale de O(n).

Comme quoi il y a potentiellement des compromis à faire dans le choix d’un algo, la rapidité ou la faible consommation mémoire peuvent venir avec un coût dans une autre dimension.

Pour conclure

  • Premier point, il faut absolument être au point pour des tests d’embauche plus sur le sujet, même si je trouve limité ces tests dans leur capacité à identifier ou filtrer les bons développeurs (l’algorithmie n’est pas certainement pas le seul critère d’un individu doué), c’est toujours bien de pouvoir les reéussir !
  • Caliper offre un outillage plutôt facile d’utilisation pour faire des microbenchmark, dans la limite de validité d’un microbenchmark, il y a plein de mise en garde sur le sujet, sur le site de Caliper [1][2], Cliff Click en a parlé aussi à JavaOne [3][4].
  • Quand on écrit du code c’est une bonne idée de penser à la complexité temporelle et spatiale, dont la notation pour les deux est le grand O. Caliper pourrait d’ailleurs se voir ajouter le moyen de mesurer la consommation mémoire (en lien avec la complexité spatiale). Évidement ce que je dis ne veut pas dire optimiser prématurément, mais juste de réfléchir à quel type de performance on peut s’attendre pour telle ou telle partie du code, et éventuellement de porter plus tard un effort spécifique.

A noter que Caliper offre d’autres possibilités de mesurer la performance à travers une méthode annotée par @ArbitraryMeasurement.

6 thoughts on “Caliper me : Ou pourquoi les microbenchmarks aident !”

    1. Oui effectivement ça me reviens, tu avais écris quelque chose sur le sujet.

      C’est bien dommage pour le job, mais bon du coup ça motive pour s’améliorer :)

      A+

  1. Merci pour le post Brice.
    J’avais vu Caliper en effet dans les sources de guava, mais sans vraiment chercher à l’utiliser. Et là il me semble très interessant. En général je fais ce genre de truc à la main avec des StopWatch puis graphite voir excel ou autre tableur pour analyser les temps d’execution. Mais là
    c’est clair que je gagne beaucoup.
    Quant au sujet des micro benchmarks, je pense aussi qu’ils sont interessants, mais ils ont leurs limites, car en général un algo fait partie d’un tout, sur la JVM plusieurs facteurs viennent vite altérer ton algo (GC, logging abusif, accès disk, etc.).
    Quant aux entretiens d’embauche, je pense plus qu’il importe plus de savoir si un candidat sait raisonner de façon analytique, écrire un algo corerct, qu’il peut detecter des points de contentions. Mais pas nécessairement un gourou du sujet qui maitrise tous les algos de tri et trucs exotiques. Sauf si bien sûr l’algorithmique est le coeur de métier de la boite.

    Par contre dans ton premier algo, tu parles de complexité en o(n²), à cause des nested loops. Mais ta seconde boucle ne fait presque jamais le tour complet de ta structure à cause de la condition j<i. Et du coup je verrais plutôt une complexité en n*log(n).
    D'ailleurs si tu lis les logs de caliper sur PairCounts_V1, on est plus dans cet ordre de grandeur que sur o(n²).

    1. Hey merci :)

      Sinon effectivement, mon idée de départ était de s’inspirer du quicksort, c’est d’ailleurs ce qui m’a perdu dans l’exo !
      Bref avec les modifications que j’ai du apporter, j’ai eu l’impression que dans le pire cas on tombe limite sur O(n²), mais tu as probablement raison, on dirait bien du n log n !

Leave a Reply

Your email address will not be published. Required fields are marked *


7 − one =

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">