Switch on String

Exercice 1 - Switch on strings

1. Dans le répertoire java-inside, créer un sous-répertoire lab5, recopier dans celui-ci le fichier POM du lab4 et changer le contenu du POM de java-inside et du lab5 pour indiquer que le lab5 est un sous module.
2. Lors du lab3, on avait implanter un switch sur les Strings plus ou moins de la façon suivante

     package fr.umlv.javainside;
     ...  
     public class StringMatcher {
       private static final MethodHandle EQUALS;
       static {
           try {
               EQUALS = publicLookup().findVirtual(String.class, "equals", methodType(boolean.class, Object.class));
           } catch (NoSuchMethodException | IllegalAccessException e) {
               throw new AssertionError(e);
           }
       }
   
       public static MethodHandle matchWithGWTs(Map<String, Integer> mapping) {
           var mh = dropArguments(constant(int.class, -1), 0, String.class);
           for(var entry: mapping.entrySet()) {
               var text = entry.getKey();
               var index = entry.getValue();
               var test = insertArguments(EQUALS, 1, text);
               var target = dropArguments(constant(int.class, index), 0, String.class);
               mh = guardWithTest(test, target, mh);
           }
           return mh;
       }
       

   Vous pouvez noter qu'ici, on utilise une Map pour indiquer pour chaque chaine de caractères quelle doit être la valeur correspondante.
   On se propose de tester la vitesse de ce code en utilisant le test JMH suivant

   @Warmup(iterations = 5, time = 2, timeUnit = TimeUnit.SECONDS)
   @Measurement(iterations = 5, time = 2, timeUnit = TimeUnit.SECONDS)
   @Fork(3)
   @BenchmarkMode(Mode.AverageTime)
   @OutputTimeUnit(TimeUnit.NANOSECONDS)
   @State(Scope.Benchmark)
   public class SwitchBenchMark {
     private static final List<String> TEXTS = List.of("foo", "bar", "boo", "abc");
     private static final Map<String, Integer> CASES = Map.of("foo", 0, "bar", 1, "baz", 2, "boo", 3, "booze", 4, "Aa", 5, "BB", 6);
   
     private static final MethodHandle MATCH_WITH_GWTS = StringMatcher.matchWithGWTs(CASES);
     //private static final MethodHandle MATCH_INLINE_CACHE = StringMatcher.matchWithAnInliningCache(CASES);
     //private static final MethodHandle MATCH_USING_HASHCODES = StringMatcher.matchUsingHashCodes(CASES);
   
     @Benchmark
     public int match_with_gwts() throws Throwable {
       var sum = 0;
       for(var text: TEXTS) {
         sum += (int) MATCH_WITH_GWTS.invokeExact(text);
       }
       return sum;
     }    
       

   
   CASES correspond au dictionnaire des valeurs possibles du switch tandis que TEXTS correspond à différentes valeur que l'on veut tester.
   Configurer le POM correctement pour que vous puissiez exécuter le test de performance ci-dessus.
3. On veut maintenant introduire une nouvelle façon d'implanter un switch sur les String, en effet, on peut remarquer que dans notre exemple certain CASES ne servent à rien car ils ne sont jamais tester (il n'y a pas de chaine de caractère dans TEXTS correspondant).
   En fait, c'est un cas assez courant le switch permet de gérer plus de cas que notre exemple à besoin.
   Dans ce cas, il n'est pas efficace de créer les GWTs pour gérer des CASES qui ne servent à rien donc on se propose de ne gérer un GWT que si il y a au moins un texte qui correspond au case.
   Pour cela, on va utiliser un inlining cache en utilisant la classe MutableCallSite. Un MutableCallSite est une boite qui contient un method handle qui change peu fréquemment et qui est censé plus changer de valeur après un certain temps (au moment du stteady state). La méthode setTarget permet de changer le method handle à l'intérieur d'un MutableCallSite, la méthode dynamicInvoker permet de créer un method handle sur un MutableCallSite.
   L'idée de l'algorithme d'inlining cache est la suivante
   • si la string n'a jamais été vu, la méthode slowPath est appelée et utilise String.indexOf pour trouver l'index puis installe dynamiquement un guardWithTest pour que la prochaine fois l'appel ne passe plus dans slowPath mais renvoie la valeur directement en passant dans le guardWithTest.
   • si la string a déjà été vu, on renvoie la même valeur que la fois précédente (d'où la notion de cache).
   
   Voici un squelette du code

       public static MethodHandle matchWithAnInliningCache(Map<String, Integer> mapping) {
           return new InliningCache(mapping).dynamicInvoker();
       }
   
       private static class InliningCache extends MutableCallSite {
           private static final MethodHandle SLOW_PATH;
           static {
               var lookup = lookup();
               try {
                   SLOW_PATH = lookup.findVirtual(InliningCache.class, "slowPath", methodType(int.class, String.class));
               } catch (NoSuchMethodException | IllegalAccessException e) {
                   throw new AssertionError(e);
               }
           }
   
           private final Map<String, Integer> mapping;
   
           public InliningCache(Map<String, Integer> mapping) {
               super(methodType(int.class, String.class));
               this.mapping = mapping;
               setTarget(MethodHandles.insertArguments(SLOW_PATH, 0, this));
           }
   
           private int slowPath(String text) {
             var index = mapping.getOrDefault(text, -1);
             
             var test = ...
             var target = ...
             var guard = guardWithTest(test, target, getTarget());
             
             setTarget(guard);
             return index;
           }
       }   
       

   Ecrire le code de slowPath et vérifier que le test correspondant dans StringMatcherTest passe.
4. Ecire le test de performance correspondant et vérifier que l'inlining cache est plus rapide que d'utiliser matchWithGWTs.
5. On peut remarquer qu'il existe deux façon d'ajouter un nouveau guardWithTest, soit on peut le mettre devant soit devant soit derrière les autres guardWithTest existants.
   Sachant que statistiquement la première chaine de caractère que l'on demande est celle qui est le plus demandée, quelle est la meilleure implantation ?
   Modifier votre implantation en conséquence

Exercice 2 - HashCode

    public static MethodHandle lookupSwitch(int[] hashCodes, MethodHandle[] methodHandles) { ... }
   

1. La classe LookupSwitchGenerator dépend de la librarie ASM, il faut donc ajouter la dépendance dans le fichier POM

        <dependency>
          <groupId>org.ow2.asm</groupId>
          <artifactId>asm</artifactId>
          <version>9.0</version>
        </dependency>
       

   Vérifier que LookupSwitchGenerator compile correctement.
2. On se propose d'écrire la méthode statique matchUsingHashCodes dans la classe StringMatcher

       private static final MethodHandle HASH_CODE;
       static {
           var lookup = lookup();
           try {
               HASH_CODE = ...
           } catch (NoSuchMethodException | IllegalAccessException e) {
               throw new AssertionError(e);
           }
       }
   
        public static MethodHandle matchUsingHashCodes(Map<String, Integer> mapping) {
           ...
           int[] hashes = ...
           MethodHandle[] mhs = ...
           ...
           return foldArguments(LookupSwitchGenerator.lookupSwitch(hashes, mhs), HASH_CODE);
       }
       

   dans un premier temps, indiquer ce que fait la méthode MethodHandles.foldArguments.
3. Implanter la méthode matchUsingHashCodes sans oublier que plusieurs Strings peuvent avoir le même hashCode.
4. Ecrire un test de performance vérifiant que matchUsingHashCodes est plus efficace que les deux méthodes précédentes.