Java: la boucle déroulée manuellement est toujours plus rapide que la boucle d'origine. Pourquoi?

Considérez les deux extraits de code suivants sur un tableau de longueur 2:

boolean isOK(int i) {
    for (int j = 0; j < filters.length; ++j) {
        if (!filters[j].isOK(i)) {
            return false;
        }
    }
    return true;
}

et

boolean isOK(int i) {
     return filters[0].isOK(i) && filters[1].isOK(i);
}

Je suppose que les performances de ces deux pièces devraient être similaires après un échauffement suffisant.
J'ai vérifié cela en utilisant le cadre de micro-analyse comparative JMH comme décrit par exemple ici et ici et j'ai observé que le deuxième extrait est plus de 10% plus rapide.

Question: pourquoi Java n'a-t-il pas optimisé mon premier extrait en utilisant la technique de déroulement de boucle de base?
En particulier, j'aimerais comprendre ce qui suit:

1. Je peux facilement produire un code qui est optimal pour les cas de 2 filtres et peut encore fonctionner en cas d'un autre nombre de filtres (imaginez un constructeur simple requise ):
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters). Le JITC peut-il faire de même et sinon, pourquoi?
2. Le JITC peut-il détecter que ' filters.length == 2 ' est le cas le plus fréquent et produire le code optimal pour ce cas après un certain échauffement? Cela devrait être presque aussi optimal que la version déroulée manuellement.
3. JITC peut-il détecter qu'une instance particulière est utilisée très fréquemment, puis produire un code pour cette instance spécifique (pour lequel il sait que le nombre de filtres est toujours 2)?
   Mise à jour: obtenu une réponse que JITC ne fonctionne qu'au niveau de la classe. OK, j'ai compris.

Idéalement, j'aimerais recevoir une réponse d'une personne ayant une compréhension approfondie du fonctionnement du JITC.

Détails de l'analyse comparative:

• Testé sur les dernières versions de Java 8 OpenJDK et Oracle HotSpot, les résultats sont similaires
• Indicateurs Java utilisés: -Xmx4g -Xms4g -server -Xbatch -XX: CICompilerCount = 2 (a obtenu des résultats similaires sans les indicateurs fantaisie également)
• Soit dit en passant, j'obtiens un rapport de durée d'exécution similaire si je l'exécute simplement plusieurs milliards de fois dans une boucle (pas via JMH), c'est-à-dire que le deuxième extrait est toujours nettement plus rapide

Sortie de référence typique:

Benchmark (filterIndex) Mode Cnt Score Erreur Unités
LoopUnrollingBenchmark.runBenchmark 0 avgt 400 44,202 ± 0,224 ns / op
LoopUnrollingBenchmark.runBenchmark 1 avgt 400 38,347 ± 0,063 ns / op

(La première ligne correspond au premier extrait, la deuxième ligne - à la seconde.

Code de référence complet:

public class LoopUnrollingBenchmark {

    @State(Scope.Benchmark)
    public static class BenchmarkData {
        public Filter[] filters;
        @Param({"0", "1"})
        public int filterIndex;
        public int num;

        @Setup(Level.Invocation) //similar ratio with Level.TRIAL
        public void setUp() {
            filters = new Filter[]{new FilterChain1(), new FilterChain2()};
            num = new Random().nextInt();
        }
    }

    @Benchmark
    @Fork(warmups = 5, value = 20)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public int runBenchmark(BenchmarkData data) {
        Filter filter = data.filters[data.filterIndex];
        int sum = 0;
        int num = data.num;
        if (filter.isOK(num)) {
            ++sum;
        }
        if (filter.isOK(num + 1)) {
            ++sum;
        }
        if (filter.isOK(num - 1)) {
            ++sum;
        }
        if (filter.isOK(num * 2)) {
            ++sum;
        }
        if (filter.isOK(num * 3)) {
            ++sum;
        }
        if (filter.isOK(num * 5)) {
            ++sum;
        }
        return sum;
    }


    interface Filter {
        boolean isOK(int i);
    }

    static class Filter1 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 3 == 1;
        }
    }

    static class Filter2 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 7 == 3;
        }
    }

    static class FilterChain1 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            for (int j = 0; j < filters.length; ++j) {
                if (!filters[j].isOK(i)) {
                    return false;
                }
            }
            return true;
        }
    }

    static class FilterChain2 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            return filters[0].isOK(i) && filters[1].isOK(i);
        }
    }

    private static Filter[] createLeafFilters() {
        Filter[] filters = new Filter[2];
        filters[0] = new Filter1();
        filters[1] = new Filter2();
        return filters;
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }
}

TL; DR La principale raison de la différence de performances ici n'est pas liée au déroulement de la boucle. C'est plutôt la spéculation de type et les caches en ligne .

Stratégies de déroulement

En fait, dans la terminologie HotSpot, ces boucles sont traitées comme comptées et, dans certains cas, la JVM peut les dérouler. Mais pas dans votre cas.

HotSpot propose deux stratégies de déroulement de boucle: 1) dérouler au maximum, c'est-à-dire supprimer complètement la boucle; ou 2) coller plusieurs itérations consécutives ensemble.

Un déroulement maximal ne peut être effectué que si le nombre exact d'itérations est connu .

  if (!cl->has_exact_trip_count()) {
    // Trip count is not exact.
    return false;
  }

Dans votre cas, cependant, la fonction peut revenir tôt après la première itération.

Un déroulement partiel pourrait probablement être appliqué, mais la condition suivante interrompt le déroulement:

  // Don't unroll if the next round of unrolling would push us
  // over the expected trip count of the loop.  One is subtracted
  // from the expected trip count because the pre-loop normally
  // executes 1 iteration.
  if (UnrollLimitForProfileCheck > 0 &&
      cl->profile_trip_cnt() != COUNT_UNKNOWN &&
      future_unroll_ct        > UnrollLimitForProfileCheck &&
      (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {
    return false;
  }

Étant donné que dans votre cas, le nombre de voyages prévu est inférieur à 2, HotSpot suppose qu'il n'est pas digne de dérouler même deux itérations. Notez que la première itération est de toute façon extraite en pré-boucle ( optimisation du pelage de boucle ), donc le déroulement n'est en effet pas très bénéfique ici.

Spéculation de type

Dans votre version déroulée, il y a deux invokeinterfacebytecodes différents . Ces sites ont deux profils de type distincts. Le premier récepteur est toujours Filter1, et le deuxième récepteur est toujours Filter2. Donc, vous avez essentiellement deux sites d'appels monomorphes, et HotSpot peut parfaitement aligner les deux appels - ce qu'on appelle le "cache en ligne" qui a un taux de réussite de 100% dans ce cas.

Avec la boucle, il n'y a qu'un seul invokeinterfacebytecode et un seul profil de type est collecté. HotSpot JVM voit que cela filters[j].isOK()est appelé 86% fois avec le Filter1récepteur et 14% fois avecFilter2 récepteur. Ce sera un appel bimorphique. Heureusement, HotSpot peut également incorporer des appels bimorphiques spéculatifs. Il insère les deux cibles avec une branche conditionnelle. Cependant, dans ce cas, le taux de réussite sera au maximum de 86%, et les performances souffriront des branches imprévues correspondantes au niveau de l'architecture.

Les choses seront encore pires si vous avez 3 filtres différents ou plus. Dans ce cas, isOK()il s'agit d'un appel mégamorphique que HotSpot ne peut pas du tout intégrer. Ainsi, le code compilé contiendra un véritable appel d'interface qui aura un impact plus important sur les performances.

Plus d'informations sur l'incrustation spéculative dans l'article The Black Magic of (Java) Method Dispatch .

Conclusion

Pour aligner les appels virtuels / d'interface, HotSpot JVM collecte les profils de type par bytecode d'appel. S'il y a un appel virtuel dans une boucle, il n'y aura qu'un seul type de profil pour l'appel, que la boucle soit déroulée ou non.

Pour tirer le meilleur parti des optimisations d'appels virtuels, vous devez fractionner manuellement la boucle, principalement dans le but de fractionner les profils de type. Pour l'instant, HotSpot ne peut pas le faire automatiquement.

La boucle présentée tombe probablement dans la catégorie des boucles "non comptées", qui sont des boucles pour lesquelles le nombre d'itérations ne peut être déterminé ni au moment de la compilation ni au moment de l'exécution. Non seulement à cause de l'argument @Andreas sur la taille du tableau, mais aussi à cause de la condition aléatoire break(qui était dans votre benchmark lorsque j'ai écrit ce post).

Les compilateurs à la pointe de la technologie ne les optimisent pas de manière agressive, car le déroulement des boucles non comptées implique souvent la duplication de la condition de sortie d'une boucle, ce qui n'améliore les performances d'exécution que si les optimisations ultérieures du compilateur peuvent optimiser le code déroulé. Voir cet article de 2017 pour plus de détails sur les propositions de déroulement de ces choses.

De cela suit, que votre hypothèse ne soutient pas que vous avez en quelque sorte "déroulé manuellement" la boucle. Vous le considérez comme une technique de déroulement de boucle de base pour transformer une itération sur un tableau avec rupture conditionnelle en une &&expression booléenne chaînée. Je considérerais cela comme un cas assez spécial et serais surpris de trouver un optimiseur de points chauds effectuant une refactorisation complexe à la volée. Ici, ils discutent de ce que cela pourrait réellement faire, peut - être que cette référence est intéressante.

Cela refléterait de plus près la mécanique d'un déroulement contemporain et n'est peut-être pas encore à quoi ressemblerait le code machine déroulé:

if (! filters[0].isOK(i))
{
   return false;
} 
if(! filters[1].isOK(i))
{
   return false;
}
return true;

Vous concluez que, parce qu'un morceau de code s'exécute plus rapidement qu'un autre morceau de code, la boucle ne s'est pas déroulée. Même si c'est le cas, vous pouvez toujours voir la différence d'exécution en raison du fait que vous comparez différentes implémentations.

Si vous voulez gagner en certitude, il y a l' analyseur / visualiseur jitwatch des opérations Jit réelles, y compris le code machine (github) (diapositives de présentation) . S'il y a quelque chose à voir, je ferais plus confiance à mes propres yeux qu'à toute opinion sur ce que JIT peut ou ne peut pas faire en général, car chaque cas a ses spécificités.Ici, ils s'inquiètent de la difficulté de parvenir à des déclarations générales pour des cas spécifiques en ce qui concerne JIT et fournissent des liens intéressants.

Étant donné que votre objectif est une durée d'exécution minimale, le a && b && c ...formulaire est probablement le plus efficace, si vous ne voulez pas dépendre d'espoir de déroulement de boucle, au moins plus efficace que tout autre élément présenté à ce jour. Mais vous ne pouvez pas avoir cela de manière générique. Avec la composition fonctionnelle de java.util.Function, il y a encore une énorme surcharge (chaque fonction est une classe, chaque appel est une méthode virtuelle qui doit être envoyée). Peut-être que dans un tel scénario, il pourrait être judicieux de renverser le niveau de langue et de générer du code d'octet personnalisé lors de l'exécution. D'un autre côté, une &&logique nécessite également une ramification au niveau du code d'octet et peut être équivalente à if / return (qui ne peut pas non plus être générée sans surcharge).