Single instruction, Multiple Data (SIMD)

Nous allons utiliser l'API jdk.incubator.vector intégré au JDK 23 (en incubation).

Comme pour les TPs précédents, nous allons utiliser Maven comme outil de build. Dans ce TP, nous avons trois besoins spécifiques

• Pour les tests, en plus de la bibliothèque JUnit habituelle, nous allons utiliser la bibliothèque junit-jupiter-params qui permet de déclarer des tests paramétrés, des tests qui peuvent prendre plusieurs algorithmes en entrée.

        <dependency>
           <groupId>org.junit.jupiter</groupId>
           <artifactId>junit-jupiter-api</artifactId>
           <version>5.11.0</version>
           <scope>test</scope>
        </dependency>
        <dependency>
          <groupId>org.junit.jupiter</groupId>
          <artifactId>junit-jupiter-params</artifactId>
          <version>5.11.0</version>
          <scope>test</scope>
        </dependency>
       

• On va utiliser la bibliothèque JMH qui permet de tester la performance de code écrit Java. JMH fonctionne avec un ensemble d'annotation comme @Benchmark et un processeur d'annotation qui transforme le code des benchmarks en tests exécutables isolés du reste du système (donc les résultats seront reproductibles).

       <dependency>
         <groupId>org.openjdk.jmh</groupId>
         <artifactId>jmh-core</artifactId>
         <version>1.37</version>
       </dependency>
       <dependency>
         <groupId>org.openjdk.jmh</groupId>
         <artifactId>jmh-generator-annprocess</artifactId>
         <version>1.37</version>
         <scope>provided</scope>
       </dependency>
      

  Il faut configurer le maven-compiler-plugin pour qu'il utilise le processeur d'annotation de JMH lors de la compilation.

       <plugin>
         <groupId>org.apache.maven.plugins</groupId>
         <artifactId>maven-compiler-plugin</artifactId>
         <version>3.13.0</version>
         <configuration>
           <release>23</release>
           <annotationProcessorPaths>
             <path>
               <groupId>org.openjdk.jmh</groupId>
               <artifactId>jmh-generator-annprocess</artifactId>
               <version>1.37</version>
             </path>
           </annotationProcessorPaths>
         </configuration>
       </plugin>
      

  Enfin, on utilise le plugin maven-shade-plugin qui prend un code et ses dépendances et créer un seul jar exécutable nommé benchmarks.jar.

       <plugin>
         <groupId>org.apache.maven.plugins</groupId>
         <artifactId>maven-shade-plugin</artifactId>
         <version>3.6.0</version>
         <executions>
           <execution>
             <phase>package</phase>
             <goals>
               <goal>shade</goal>
             </goals>
             <configuration>
               <finalName>benchmarks</finalName>
               <transformers>
                 <transformer implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
                   <mainClass>org.openjdk.jmh.Main</mainClass>
                 </transformer>
               </transformers>
               <filters>
                 <filter>
                   <artifact>*:*</artifact>
                   <excludes>
                     <exclude>**/module-info.class</exclude>
                     <exclude>META-INF/MANIFEST.MF</exclude>
                   </excludes>
                 </filter>
               </filters>
             </configuration>
           </execution>
         </executions>
       </plugin>
      

• De plus on utilise le module jdk.incubator.vector qui est un module en incubation (l'API n'est pas finalisée), il faut l'activer explicitement avec --add-modules à la compilation et à l'exécution des tests.

       <plugin>
         <groupId>org.apache.maven.plugins</groupId>
         <artifactId>maven-compiler-plugin</artifactId>
         <version>3.13.0</version>
         <configuration>
           <release>23</release>
           <compilerArgs>
             <compilerArg>--add-modules</compilerArg>
             <compilerArg>jdk.incubator.vector</compilerArg>
           </compilerArgs>
         </configuration>
       </plugin>
  
       <plugin>
         <groupId>org.apache.maven.plugins</groupId>
         <artifactId>maven-surefire-plugin</artifactId>
         <version>3.5.0</version>
         <configuration>
           <argLine>--add-modules jdk.incubator.vector</argLine>
         </configuration>
       </plugin>
      

Comme précédemment, créer un projet Maven en cochant create simple project au niveau du premier écran, puis passer à l'écran suivant en indiquant Next.
Pour ce TP, le groupId est fr.uge.simd , l'artefactId est simd et la version est 0.0.1-SNAPSHOT. Pour finir, cliquer sur Finish.

Le but de cet exercice est de calculer la somme et le minimum d'un tableau de façon vectorisée (en utilisant des vecteurs de valeurs). Nous allons pour cela créer une classe fr.uge.simd.VectorComputation (dans src/main/java) qui contiendra les différentes méthodes statiques.
Les tests unitaires correspondants s'appellent fr.uge.simd.VectorComputationTest (dans src/test/java).
Note : il est possible de lancer les tests directement, mais il faut penser à rajouter --add-modules jdk.incubator.vector dans les options de la VM.
Pour Maven, sous Eclipse, clic droit sur le projet, "run as..." puis maven clean et maven install.
De plus la classe fr.uge.simd.VectorComputationBenchmark (dans src/main/java) contient les tests de performance JMH pour vérifier que le code que vous avez écrit est bel et bien plus performant qu'une simple boucle sur les données du tableau.
Note : par défaut les benchmarks (les méthodes annotées avec @Benchmark) sont commentés, il faut les dé-commenter si vous voulez exécuter un benchmark. Et il faut penser à produire le jar correspondant.

On souhaite améliorer la vitesse moyenne (pas le pire cas, pour cela il ne faut pas prendre une liste) des recherches dans une liste.
L'idée est la suivante : chercher dans une liste demande à appeler la méthode Object.equals() sur chaque élément de la liste. Or, on peut accélérer un peu les choses en comparant les hashCode() AVANT d'appeler equals()... En effet, cela peut permettre de gagner en performances : si, par exemple, les éléments sont des chaînes de caractères, cela revient à comparer un entier au lieu de parcourir la chaîne de caractères et comparer les caractères un à un (dans le cas où les chaines sont différentes).
On se propose de créer une classe FastScanList qui, en plus du tableau des éléments, maintient un tableau des hashCodes. Pour éviter d'utiliser trop d'espace mémoire (et pour pouvoir plus tard utiliser l'API des vectors), nous n'allons pas stocker le hashCode complet sur un int mais seulement une portion sur un byte.
Pour la classe FastScanList, on se propose d'utiliser le code suivant (dans src/main/java)

public class FastScanList<E> {
  private E[] array;
  private byte[] hashes;
  private int size;

  public FastScanList() {
    @SuppressWarnings("unchecked")
    var array = (E[]) new Object[16];
    this.array = array;
    this.hashes = new byte[16];
  }

  public int size() {
    return size;
  }

  private void resize() {
    var newLength = size << 1;
    array = Arrays.copyOf(array, newLength);
    hashes = Arrays.copyOf(hashes, newLength);
  }

  public void add(E element) {
    Objects.requireNonNull(element);
    if (array.length == size) {
      resize();
    }
    array[size] = element;
    hashes[size] = (byte) element.hashCode();
    size++;
  }

  @Override
  public String toString() {
    return IntStream.range(0, size)
        .mapToObj(i -> array[i] + " (" + (hashes[i] & 0xFF) + ")")
        .collect(Collectors.joining(", ", "[", "]"));
  }

  public boolean contains(Object o) {
    Objects.requireNonNull(o);
    var hash = (byte) o.hashCode();
    for(var i = 0; i < size; i++) {
      if (o.equals(array[i])) {
        return true;
      }
    }
    return false;
  }
}
  

Les tests unitaires correspondants s'appellent fr.uge.simd.FastScanListTest (dans src/test/java).
De plus la classe fr.uge.simd.FastScanListBenchmark (dans src/main/java) contient les tests de performance JMH.