Examen de Collection Concurrente 2026 - Session 1

À lire absolument

Exercice 1 - TreiberStack

public final class TreiberStack<E> {
  private record Node<E>(E element, Node<E> next) {}

  private Node<E> head;

  public void push(E element) {
    throw new UnsupportedOperationException("TODO");
  }

  public E pop() {
    throw new UnsupportedOperationException("TODO");
  }
}
   

  var stack = new TreiberStack<Integer>();
  stack.push(100);
  stack.push(1024);
  IO.println(stack.pop());  // 1024
  IO.println(stack.pop());  // 100
  IO.println(stack.pop());  // null
   

1. Écrire les méthodes push et pop en utilisant l'API des VarHandle.
   Vérifier que les deux premiers tests unitaires passent.


2. On veut maintenant ajouter une méthode pushAll(list) qui prend en paramètre une liste d'élément et ajoute ceux-ci dans la liste en une opération atomique.
   Vérifier que le dernier test passent.
   Note: ne m'oubliez pas les wildcards.

Exercice 2 - SimdBitSet

public final class SimdBitSet {

  private int[] words;

  private SimdBitSet(int[] words) {
    this.words = words;
    super();
  }

  public SimdBitSet() {
    this(new int[0]);
  }

  public void set(int bit) {
    if (bit < 0) {
      throw new IndexOutOfBoundsException("bit index out of range: " + bit);
    }
    var wordIndex = bit >> 5;
    if (wordIndex >= words.length) {  // resize if necessary
      words = Arrays.copyOf(words, wordIndex + 1);
    }
    words[wordIndex] |= 1 << (bit & 31);
  }

  public boolean get(int bit) {
    if (bit < 0) {
      throw new IndexOutOfBoundsException("bit index out of range: " + bit);
    }
    if (bit >= words.length << 5) {
      return false;
    }
    var mask = 1 << (bit & 31);
    return (words[bit >> 5] & mask) != 0;
  }

  @Override
  public boolean equals(Object o) {
    return o instanceof SimdBitSet other &&
        words.length == other.words.length &&
        Arrays.equals(words, other.words);
  }

  @Override
  public int hashCode() {
    return Arrays.hashCode(words);
  }

  public int bitCount() {
    var count = 0;
    for (var word : words) {
      count += Integer.bitCount(word);
    }
    return count;
  }

  @Override
  public String toString() {
    var builder = new StringBuilder().append('{');
    var separator = "";
    for (var i = 0; i < words.length; i++) {
      var word = words[i];
      while (word != 0) {
        // Isolate the lowest set bit and find its position
        var lowestSetBitPos = Integer.numberOfTrailingZeros(word);
        builder.append(separator).append((i << 5) + lowestSetBitPos);
        separator = ", ";
        word &= word - 1; // clear the lowest set bit
      }
    }
    return builder.append('}').toString();
  }

  public SimdBitSet and(SimdBitSet other) {
    Objects.requireNonNull(other);
    var length = Math.min(this.words.length, other.words.length);
    var words = new int[length];
    for (var i = 0; i < length; i++) {
      words[i] = this.words[i] & other.words[i];
    }
    return new SimdBitSet(words);
  }
}
    

1. On va, dans un premier temps, implanter une nouvelle version de la méthode and qui utilise les opérations vectorisées.
   Écrire la nouvelle version de la méthode and et vérifier que les tests unitaires marqués "Q1" passent.
   Note: ici, on souhaite une implantation avec une post-loop.


2. On souhaite maintenant ajouter une méthode parallelAnd qui marche comme and mais effectue le calcul sur plusieurs cœurs (en utilisant le principe fork/join).
   Doit-on utiliser une RecursiveTask ou une RecursiveAction ici ?
   On va créer pour cela une classe interne ParallelAnd. En prenant le temps de réfléchir, quelles sont les champs de cette classe ?
   Dans la classe interne ParallelAnd, on va écrire une méthode sequentialAnd qui effectue le calcul séquentiel si le nombre de cases du tableau est trop petit.
   Écrire le code de cette méthode.
   Sachant que l'on va considérer que les tableaux de 32 cases ou moins doivent être traité séquentiellement, écrire le reste de la classe ParallelAnd.
   Enfin, écrire le code de la méthode parallelAnd.
   Vérifier que les tests unitaires marqués "Q2" passent.
   Note: pour être efficace, vous ne devriez y avoir qu'une seule allocation de tableau (le tableau contenant les bits résultant), pas 25 !
   Note2: on ne vous demande pas pour l'instant que l'implantation de sequentialAnd utilise des instructions vectorisées.


3. Changer le code de sequentialAnd (commenter l'ancien code), pour utiliser les instructions vectorisées.
   Vérifier que les tests unitaires marqués "Q2" continue de passer.


4. Sachant qu'il existe une opération VectorOperators.BIT_COUNT, modifier le code de bitCount pour utiliser des opérations vectorisées.
   Vérifier que les tests unitaires marqués "Q4" passent.
   Note: si vous faites bien les choses, il devrait y avoir deux raisons pour lesquelles on a des gains de performance


5. Enfin, on souhaite ajouter une méthode or qui marche comme and mais fait un "ou bit-à-bit" ("bitwise or" en anglais) utilisant aussi les opérations vectorisées.
   Vérifier que les tests unitaires marqués "Q5" passent.