Tests de performance avec JMH

L’occasion se présente…

Performance dans une application de gestion

J’ai régulièrement eu l’occasion de faire des mesures de performances, principalement sur des applications d’informatique de gestion. Pour cela, les profileurs sont particulièrement utiles pour cibler rapidement la source du problème. J’ai plusieurs fois pu utiliser AppDynamics, qui est très efficace. Il en existe d’autres (JProfiler, DynaTrace, etc.) que je n’ai que peu testés. Enfin, à défaut d’outils payants, il est possible de tirer beaucoup d’informations de JVisualVM (embarquée dans le JDK).

Dans la très (très) grosse majorité des cas, le problème de performances provient d’une requête SQL non optimisée (parfois à cause d’une mauvaise utilisation d’un ORM, comme Hibernate). Moins fréquemment, ils peuvent provenir d’un traitement java, mais c’est dans ce cas le plus souvent un algorithme mal écrit (complexité N^2, voire plus). Les derniers cas auxquels j’ai été confronté, sont liés à des frameworks un peu longs à traiter des opérations I/O (sérialisation/désérialisation de messages, copie profonde de larges grappes d’objets avec Dozer, etc.).

Dans aucun de ces cas, la résolution n’a nécessité de pousser l’analyse jusqu’à un microbenchmark : des solutions "macroscopiques" suffisent pour revenir à des performances acceptables pour une application de gestion.

Pire, je préfère souvent échanger un peu de microperformance contre une meilleure lisibilité du code. Toujours dans le cadre d’une application de gestion, ces "concessions" sur les performances sont totalement invisibles par rapport au temps passé dans les I/O (appels à la base de données, traitement de la requête http, etc.).

En toute rigueur, un microbenchmark serait utile pour étayer cette dernière affirmation. Je ne l’ai jamais fait, mais j’ai pu en avoir confirmation via les profileurs sus-mentionnés.

Codingame

Il y a quelques mois, avec des collègues (qui se reconnaîtront), nous nous sommes inscrits à Codingame, qui propose des jeux et compétitions de programmation et d’algorithmie.

Pour ceux qui veulent me suivre, voici mon (peu glorieux) profil.

D’abord, il y a les puzzles : des jeux à résoudre en fournissant un code, qui sera validé par une suite de tests automatisés. Les puzzles vont en difficulté croissante, et fournissent une très bonne occasion de revoir, voire d’apprendre des algorithmes : tris, plus court chemin, théorie des graphes, etc.

Les puzzles doivent être résolus en un temps limité. Mais là encore, si on dépasse le temps autorisé, c’est plus un problème d’algorithme que de micro-optimisation.

Et puis… il y a les compétitions et jeux multijoueurs, dans lesquelles on doit développer une IA, qui sera mise en concurrence avec celle des autres joueurs lors de matchs. C’est là que les choses intéressantes commencent. Les règles de ces matchs sont le plus souvent de la forme :

Au début d’un tour, on reçoit l’état courant du "plateau de jeu". On doit alors renvoyer le prochain mouvement qu’on choisit de faire, en ayant pour cela *un
temps limité à quelques millisecondes*.

Pour ces compétitions, les vainqueurs (qui sont interviewés) expliquent avoir recours à des algorithmes de type génétique ou Monte-Carlo.

Ces algorithmes reposent en gros sur le principe suivant : on tire une suite de mouvements aléatoirement et on simule leur valeur plusieurs coups à l’avance. On répète le processus un grand nombre de fois. Avant la fin du temps imparti, on conserve le meilleur mouvement.

Conséquence : plus l’algorithme est rapide, plus on peut tester les combinaisons sur une profondeur importante (ou alors tester plus de combinaisons possibles). Et donc, meilleur sera le résultat. Pendant les quelques centaines de millisecondes accordées, il s’agit donc de simuler un maximum de coups.

Dans ce scénario, où il faut faire jouer à l’algorithme plusieurs centaines de milliers de coups, les petites optimisations comptent !

La problématique

Présentation du challenge

Intéressons-nous à la modélisation du challenge Smash The Code. Il s’agit d’un Tetris dans lequel les combos polluent la grille de l’adversaire (un joli clin d’œil à Dr Robotnik’s Mean Bean Machine).

Au début d’un tour de jeu, on reçoit l’état du jeu (le contenu de 6 cases de large sur 12 de haut), ainsi que les 8 prochains blocs qui vont tomber. A partir de ces informations, on va simuler un maximum de parties différentes, afin de voir laquelle rapporte le maximum de points.

Chaque bloc peut être placé dans chacune des 6 colonnes, avec 4 possibilités de rotation. Nous avons donc (6*4)^8 simulations possibles… soit plus de 110 milliards. En 100 ms, on ne pourra pas tester autant de parties, mais on doit essayer d’en jouer un maximum.

Dans le challenge, on connaît également la grille de l’adversaire. Si on souhaite calculer ses simuler ses prochains coups possibles (pour deviner combien de pierres vont nous être envoyées et à quel tour… ce qui modifie la suite du jeu). La simulation d’un véritable tour de jeu consiste donc à vérifier les possibilités de placement pour chacune des grilles. On se retrouve alors avec (6*4*6*4)^8 simulations possibles (soit plus de 10^22).

Voici donc, (de manière très simplifiée), comment l’algorithme va procéder :

Nous avons un plateau de 6*12 cases à stocker.
Sur ce plateau, nous allons simuler une partie.
On remet le plateau à son état initial (en début de tour) pour la simulation suivante.

Afin de réaliser un maximum de simulations, on essaye de trouver :

La structure de données la plus efficace pour stocker notre plateau de jeu.
La manière la plus efficace de réinitialiser ce plateau.

Les différentes solutions testées

On va tester deux structures de données pour stocker notre plateau :

Un tableau d’entier à deux dimensions de 6 * 12 cases.
Un tableau d’entier à une seule dimension de taille 6 * 12. On accède à la ligne x colonne y en prenant l’indice 6*x + y du tableau.

Au niveau de la réinitialisation, on va garder de côté un tableau contenant l’état initial. On va tester les différentes méthodes de réinitialisation :

Instanciation d’un nouveau tableau par "clonage" (profond) du tableau de référence.
Réutilisation d’un unique tableau de jeu, dont on "écrase" les valeurs par celles du tableau de référence pour la prochaine simulation :
- Par copie "manuelle" des valeurs du tableau.
- En utilisant "System.arraycopy()".

Mise en place du projet JMH

Présentation

Il y a quelques années de cela, j’aurais réalisé ce benchmark avec "System.currentTimeMillis()" et "System.out.println()", voire avec une librairie comme Perf4J (qui utilise les mêmes méthodes).

C’est en fait une mauvaise idée. Quelques arguments de cet article en vrac :

La JVM optimise analyse le code exécuté à la volée et l’optimise au fur et à mesure des exécutions. Pour réaliser un benchmark pertinent, il faut donc que la JVM "chauffe".
Si la méthode à tester n’a pas d’effet de bord, dans ces optimisations, la JVM peut optimiser le code en ne l’exécutant simplement pas.
Un test de performance en multithread est assez compliqué à mettre en place.

Le framework JMH a été conçu spécialement pour éviter ces problèmes et obtenir des microbenchmarks java dont les résultats soient pertinents.

Initialisation du projet

Le plus simple pour initialiser un projet JMH, c’est de passer par l’archetype Maven fourni :

mvn archetype:generate \
          -DinteractiveMode=false \
          -DarchetypeGroupId=org.openjdk.jmh \
          -DarchetypeArtifactId=jmh-java-benchmark-archetype \
          -DgroupId=org.courtine.benchmark \
          -DartifactId=squashthecode \
          -Dversion=1.0

Pour ajouter des benchmarks à un projet existant, il suffit d’ajouter les dépendances JMH :

<project>
  <modelVersion>4.0.0</modelVersion>

  <groupId>org.courtine.benchmark</groupId>
  <artifactId>squashthecode</artifactId>
  <version>1.0-SNAPSHOT</version>
  <packaging>jar</packaging>

  <name>Squash the code benchmarks</name>

  <properties>
    <jmh.version>1.13</jmh.version>
  </properties>

  <dependencies>
    <dependency>
      <groupId>org.openjdk.jmh</groupId>
      <artifactId>jmh-core</artifactId>
      <version>${jmh.version}</version>
    </dependency>
    <dependency>
      <groupId>org.openjdk.jmh</groupId>
      <artifactId>jmh-generator-annprocess</artifactId>
      <version>${jmh.version}</version>
      <scope>provided</scope>
    </dependency>
  </dependencies>
</project>

Les classes de test

Les classes suivantes montrent une utilisation basique de JMH. Il est possible d’affiner les paramètres du benchmark via différentes annotations sur la classe ou les méthodes. Pour aller plus loin, cet article explique très bien quelles sont les principales options disponibles et quelle est leur influence sur le benchmark.
La méthode "main()" n’est pas obligatoire pour lancer le benchmark. Les options de lancement peuvent être remplacées par des annotations (cf. ci-dessus). Il est ensuite possible de lancer l’ensemble des benchmarks du projet en une seule passe avec la méthode "main()" de la classe "org.openjdk.jmh.Main".

Tableau à deux dimensions

Classe de test du tableau à deux dimensions

@State(Scope.Thread)
public class Array2D {

  private int[][] reference = new int[6][12];

  private int[][] game = new int[6][12];

  @Benchmark
  public int[][] cloneNewGame() {
    int[][] gameClone = new int[6][];

    for (int i = 0; i < 6; i++) {
      gameClone[i] = reference[i].clone();
    }
    return gameClone;
  }

  @Benchmark
  public int[][] manualCopy() {
    for (int i = 0; i < 6; i++) {
      for (int j = 0; j < 12; j++) {
        game[i][j] = reference[i][j];
      }
    }
    return game;
  }

  @Benchmark
  public int[][] systemCopy() {
    for (int i = 0; i < 6; i++) {
      System.arraycopy(reference[i], 0, game[i], 0, 12);
    }
    return game;
  }

  public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
        .include(Array2D.class.getSimpleName())
        .warmupIterations(5)
        .measurementIterations(5)
        .forks(3)
        .build();

    new Runner(opt).run();
  }
}

Tableau à une dimension

Classe de test du tableau à une dimension

@State(Scope.Thread)
public class Array1D {

  private int[] reference = new int[72];

  private int[] game = new int[72];

  @Benchmark
  public int[] cloneNewGame() {
    return reference.clone();
  }

  @Benchmark
  public int[] manualCopy() {
    for (int i = 0; i < reference.length; i++) {
      game[i] = reference[i];
    }
    return game;
  }

  @Benchmark
  public int[] systemCopy() {
    System.arraycopy(reference, 0, game, 0, reference.length);
    return game;
  }

  public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
        .include(Array1D.class.getSimpleName())
        .warmupIterations(5)
        .measurementIterations(5)
        .forks(3)
        .build();

    new Runner(opt).run();
  }
}

Résultats

Résultats bruts

Utilisation d’un tableau à deux dimensions

Benchmark              Mode  Cnt         Score        Error  Units
Array2D.cloneNewGame  thrpt   15  11845616,763 ± 617325,240  ops/s
Array2D.manualCopy    thrpt   15  26147670,759 ± 594266,541  ops/s
Array2D.systemCopy    thrpt   15  22629807,820 ± 194914,096  ops/s

Utilisation d’un tableau à une dimension

Benchmark              Mode  Cnt         Score         Error  Units
Array1D.cloneNewGame  thrpt   15  23912990,376 ±  558054,944  ops/s
Array1D.manualCopy    thrpt   15  55101414,047 ± 1766818,773  ops/s
Array1D.systemCopy    thrpt   15  67799799,658 ± 2198781,240  ops/s

Interprétation

Ces résultats confirment ce qu’on pouvait attendre par "intuition" :

Le stockage du plateau de jeu sous la forme d’un tableau à une dimension est bien plus efficace que sous la forme d’un tableau à deux dimensions.
L’instanciation d’un nouveau tableau pour chaque partie à simuler est beaucoup moins efficace que le recyclage d’une instance de tableau existante.
L’écrasement du tableau à une dimension par la méthode "System.arraycopy()" est plus efficace qu’avec une copie manuelle.

En revanche, je ne m’attendais pas à ce que l’utilisation de "System.arraycopy()" soit moins efficace que la copie manuelle pour un tableau à deux dimensions. La taille du tableau à copier (12) est trop faible pour compenser le coût d’appel. Avec un tableau à deux dimensions dont la deuxième dimension est plus importante, "System.arraycopy()" redevient plus intéressant (j’ai vérifié ce point en utilisant un sous-tableau de taille 120).

Ce petit test nous donne l’implémentation la plus efficace pour le challenge. Il ne reste plus qu’à coder l’IA qui va avec…

Pour aller plus loin

Mise à jour le 02/09/2016 : deux articles résumant bien comment utiliser JMH.

Introduction to JMH :
- Présentation des principales annotations et de la manière dont elles modifient le benchmark.
- Rappels des pièges à éviter pour avoir un benchmark pertinent (la méthode testée doit avoir un "effet de bord", ne pas renvoyer une valeur constante, etc.).
Introduction to JMH profilers :
- Présention des profileurs, ajoutant des métriques aux benchmarks effectués (suivi du garbage-collector, de la taille mémoire utilisée, de la pile, etc.) en fonction de ce que l’on souhaite mesurer.

Benoît Courtine