Examen de Collection Concurrente 2025 - Session 1

À lire absolument

Exercice 1 - Initialisation paresseuse

public final class LazyValue<T> {
  private final Supplier<? extends T> supplier;
  private T value;

  public LazyValue(Supplier<? extends T> supplier) {
    this.supplier = Objects.requireNonNull(supplier);
  }

  public T value() {
    if (value == null) {
      value = Objects.requireNonNull(supplier.get());
    }
    return value;
  }
}
   

  var lazyValue = new LazyValue<>(() -> 42);
  ...
  System.out.println(lazyValue.value());  // 42
  System.out.println(lazyValue.value());  // toujours 42
   

1. Dans un premier temps, copier/coller le code de la classe LazyValue et indiquer en commentaire pourquoi le code n'est pas tread-safe.
   Puis modifier le code pour que la classe soit tread-safe sachant que l'on veut une implantation lock free efficace.
   Vérifier que les tests unitaires marqués "Q1" passent.
   Note: pour cette question, on présupposera que le supplier ne fait pas d'effet de bord, il est donc Okay que plusieurs threads l'exécutent. Mais comme on veut une implantation efficace, cela ne doit pas être vrai si la valeur n'est pas encore initialisée.
   Note2: si vous regardez les tests, il est possible que l'exécution d'un Supplier prenne beaucoup de temps, il serait malheureux que votre code fasse de l'attente active.


2. On veut maintenant créer une nouvelle classe LazyOnceValue qui marche comme LazyValue mais qui offre la garantie supplémentaire qu'un seul thread peut exécuter le code du Supplier.
   Sachant qu'il n'est plus possible d'avoir une implantation lock free, on va se rabattre sur une implantation qui ne coute pas trop chère.
   Quel technique doit-on utiliser ici ?
   Écrire l'implantation de LazyOnceValue.
   Vérifier que les tests unitaires marqués "Q2" passent.


3. Enfin, on veut créer une classe LazyOnceList qui est une java.util.List dont les éléments sont calculés de façon paresseuse.
   À la construction, LazyOnceList prend en paramètre un entier size qui correspond à la taille de la liste et une fonction d'initialisation qui associe à un index la valeur de l'élément.
   Voici un exemple d'utilisation

   List<String> list = new LazyOnceList<(5, index -> "Value " + index);
   
   System.out.println(list.size());  // 5
   System.out.println(list.get(3));  // Value 3
       

   
   La liste est non modifiable et ne permet pas les éléments null.
   En termes d'implantation, l'idée est d'avoir un tableau de valeurs et de faire l'initialisation pour une case du tableau de la même façon que pour la classe LazyOnceValue.
   Écrire l'implantation de LazyOnceList.
   Vérifier que les tests unitaires marqués "Q3" passent.
   Note: il existe la méthode MethodHandles.arrayElementVarHandle qui permet d'obtenir un VarHandle sur les cases d'un tableau. Dans ce cas, les méthodes get* prennent en paramètre le tableau et l'index de la case et les méthodes set* prennent en paramètre le tableau, l'index et la nouvelle valeur.
   Rappel de Java Avancé : on implante l'interface java.util.List en héritant de la classe abstraite AbstractList.

Exercice 2 - Le compte est bon

1. On souhaite écrire dans une classe ByteCounter une méthode countSpacesAndNewlines qui prend en paramètre un tableau de bytes et renvoie un objet qui contient un champ spaces qui correspond au nombre d'espaces (' ') dans le tableau et un champ newlines qui correspond au nombre de retour à la lignes ('\n') dans le tableau.
   On souhaite que l'implantation utilise les opérations vectorisées, et soit efficace. (Éviter plusieurs parcours du tableau SVP).
   Écrire l'implantation de la méthode countSpacesAndNewlines(array).
   Vérifier que les tests unitaires marqués "Q1" passent.
   Rappel: il existe une méthode trueCount() qui calcule le nombre de bit allumé d'un masque.
   Note: ici, on souhaite une implantation avec une post-loop.


2. On souhaite ajouter une surcharge à la méthode countSpacesAndNewlines qui en plus du tableau prend un index de début start et un index de fin end et en fait le calcul que sur la partie du tableau entre start (inclus) et end (exclus).
   Écrire l'implantation de la méthode countSpacesAndNewlines(array, start, end).
   Vérifier que les tests unitaires marqués "Q2" passent.
   Note: pour être efficace, il est mieux que lorsque l'on charge les valeurs dans un vecteur, l'offset de la valeur soit un multiple de la taille du nombre de lanes. Donc pour bien faire, il faudrait une pre-loop pour les valeurs qui ne sont pas alignées, avant l'algorithme habituel.
   Note2: si vous n'arrivez pas à faire la pre-loop, ce n'est pas grave, votre code devrait marcher, mais il ne sera pas le plus efficace possible.


3. Enfin, on souhaite écrire une méthode parallelCountSpacesAndNewlines qui prend en tableau en paramètre et fait le calcul en parallèle sur plusieurs threads en utilisant le mécanisme de fork-join. Bien sûr, chaque thread devra utiliser les instructions vectorisés pour rendre le calcul le plus rapide possible.
   Écrire l'implantation de la méthode parallelCountSpacesAndNewlines(array).
   Vérifier que les tests unitaires marqués "Q3" passent.