Java: Die manuell abgewickelte Schleife ist immer noch schneller als die ursprüngliche Schleife. Warum?

Betrachten Sie die folgenden zwei Codeausschnitte in einem Array der Länge 2:

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

und

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

Ich würde annehmen, dass die Leistung dieser beiden Stücke nach ausreichendem Aufwärmen ähnlich sein sollte.
Ich habe dies mit dem JMH-Mikro-Benchmarking-Framework überprüft, wie z. B. hier und hier beschrieben, und festgestellt, dass das zweite Snippet mehr als 10% schneller ist.

Frage: Warum hat Java mein erstes Snippet nicht mithilfe der grundlegenden Technik zum Abrollen von Schleifen optimiert?
Insbesondere möchte ich Folgendes verstehen:

1. Ich kann leicht einen Code erstellen, der für Fälle von 2 Filtern optimal ist und bei einer anderen Anzahl von Filtern trotzdem funktioniert (stellen Sie sich einen einfachen Builder vor) :
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters). Kann JITC dasselbe tun und wenn nicht, warum?
2. Kann JITC erkennen, dass ' filter.length == 2 ' der häufigste Fall ist, und nach einer gewissen Aufwärmphase den für diesen Fall optimalen Code erzeugen? Dies sollte fast so optimal sein wie die manuell abgewickelte Version.
3. Kann JITC erkennen, dass eine bestimmte Instanz sehr häufig verwendet wird, und dann einen Code für diese bestimmte Instanz erstellen (für die bekannt ist, dass die Anzahl der Filter immer 2 beträgt)?
   Update: Ich habe die Antwort erhalten, dass JITC nur auf Klassenebene funktioniert. OK habe es.

Im Idealfall möchte ich eine Antwort von jemandem erhalten, der ein tiefes Verständnis für die Funktionsweise von JITC hat.

Details zum Benchmark-Lauf:

• Bei den neuesten Versionen von Java 8 OpenJDK und Oracle HotSpot wurden ähnliche Ergebnisse erzielt
• Verwendete Java-Flags: -Xmx4g -Xms4g -server -Xbatch -XX: CICompilerCount = 2 (ähnliche Ergebnisse auch ohne die ausgefallenen Flags erhalten)
• Übrigens bekomme ich ein ähnliches Laufzeitverhältnis, wenn ich es einfach mehrere Milliarden Mal in einer Schleife ausführe (nicht über JMH), dh das zweite Snippet ist immer deutlich schneller

Typische Benchmark-Ausgabe:

Benchmark (filterIndex) -Modus Cnt-Score-
Fehlereinheiten LoopUnrollingBenchmark.runBenchmark 0 avgt 400 44,202 ± 0,224 ns / op
LoopUnrollingBenchmark.runBenchmark 1 avgt 400 38,347 ± 0,063 ns / op

(Die erste Zeile entspricht dem ersten Snippet, die zweite Zeile - der zweiten.

Vollständiger Benchmark-Code:

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 Der Hauptgrund für Leistungsunterschiede hängt hier nicht mit dem Abrollen der Schleife zusammen. Es ist eher die Typenspekulation und die Inline-Caches .

Abrollstrategien

In der HotSpot-Terminologie werden solche Schleifen als gezählt behandelt , und in bestimmten Fällen kann JVM sie abrollen. Nicht in deinem Fall.

HotSpot hat zwei Strategien zum Abrollen von Schleifen: 1) Maximales Abrollen, dh Entfernen der Schleife insgesamt; oder 2) mehrere aufeinanderfolgende Iterationen zusammenkleben.

Das maximale Abrollen kann nur durchgeführt werden, wenn die genaue Anzahl der Iterationen bekannt ist .

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

In Ihrem Fall kann die Funktion jedoch früh nach der ersten Iteration zurückkehren.

Ein teilweises Abrollen könnte wahrscheinlich angewendet werden, aber die folgende Bedingung bricht das Abrollen ab:

  // 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;
  }

Da in Ihrem Fall die erwartete Anzahl von Fahrten weniger als 2 beträgt, geht HotSpot davon aus, dass es nicht sinnvoll ist, auch nur zwei Iterationen abzuwickeln. Beachten Sie, dass die erste Iteration ohnehin in die Vorschleife extrahiert wird ( Optimierung des Schleifenschälens ), so dass das Abrollen hier in der Tat nicht sehr vorteilhaft ist.

Typenspekulation

In Ihrer abgewickelten Version gibt es zwei verschiedene invokeinterfaceBytecodes. Diese Sites haben zwei unterschiedliche Typprofile. Der erste Empfänger ist immer Filter1und der zweite Empfänger ist immer Filter2. Sie haben also im Grunde zwei monomorphe Anrufseiten, und HotSpot kann beide Anrufe perfekt inline - den sogenannten "Inline-Cache", der in diesem Fall eine Trefferquote von 100% aufweist.

Bei der Schleife gibt es nur einen invokeinterfaceBytecode und nur ein Typprofil wird erfasst. HotSpot JVM sieht, dass dies filters[j].isOK()86% Mal mit dem Filter1Empfänger und 14% Mal mit dem Filter2Empfänger aufgerufen wird . Dies wird ein bimorpher Aufruf sein. Glücklicherweise kann HotSpot auch bimorphe Anrufe spekulativ einbinden. Beide Ziele werden mit einem bedingten Zweig versehen. In diesem Fall beträgt die Trefferquote jedoch höchstens 86%, und die Leistung leidet unter den entsprechenden falsch vorhergesagten Zweigen auf Architekturebene.

Es wird noch schlimmer, wenn Sie 3 oder mehr verschiedene Filter haben. In diesem Fall handelt isOK()es sich um einen megamorphen Aufruf, den HotSpot überhaupt nicht einbinden kann. Der kompilierte Code enthält also einen echten Schnittstellenaufruf, der größere Auswirkungen auf die Leistung hat.

Weitere Informationen zum spekulativen Inlining finden Sie im Artikel The Black Magic of (Java) Method Dispatch .

Fazit

Um virtuelle Aufrufe / Schnittstellenaufrufe zu integrieren, sammelt HotSpot JVM Typprofile pro aufgerufenem Bytecode. Wenn sich in einer Schleife ein virtueller Anruf befindet, gibt es nur ein Typprofil für den Anruf, unabhängig davon, ob die Schleife abgewickelt ist oder nicht.

Um die Optimierungen für virtuelle Anrufe optimal nutzen zu können, müssen Sie die Schleife manuell aufteilen, hauptsächlich zum Aufteilen von Typprofilen. HotSpot kann dies bisher nicht automatisch tun.

Die dargestellte Schleife fällt wahrscheinlich unter die Kategorie "nicht gezählt" von Schleifen, bei denen es sich um Schleifen handelt, für die die Iterationszahl weder zur Kompilierungszeit noch zur Laufzeit bestimmt werden kann. Nicht nur wegen des @ Andrew-Arguments über die Array-Größe, sondern auch wegen der zufälligen Bedingung break(die früher in Ihrem Benchmark war, als ich diesen Beitrag schrieb).

Hochmoderne Compiler optimieren sie nicht aggressiv, da beim Abrollen nicht gezählter Schleifen häufig auch die Exit-Bedingung einer Schleife dupliziert wird, wodurch die Laufzeitleistung nur dann verbessert wird, wenn nachfolgende Compiler-Optimierungen den abgewickelten Code optimieren können. In diesem Papier von 2017 finden Sie Einzelheiten dazu, wo Vorschläge gemacht werden, wie solche Dinge auch abgewickelt werden können.

Daraus folgt, dass Ihre Annahme nicht zutrifft, dass Sie die Schleife sozusagen "manuell abgewickelt" haben. Sie betrachten es als eine grundlegende Technik zum Abrollen von Schleifen, um eine Iteration über ein Array mit bedingter Unterbrechung in einen &&verketteten booleschen Ausdruck umzuwandeln . Ich würde dies als einen besonderen Fall betrachten und wäre überrascht, wenn ein Hot-Spot-Optimierer ein komplexes Refactoring im laufenden Betrieb durchführen würde. Hier diskutieren sie, was es tatsächlich tun könnte, vielleicht ist diese Referenz interessant.

Dies würde die Mechanik eines zeitgenössischen Abrollens näher widerspiegeln und ist vielleicht noch lange nicht annähernd so, wie der abgerollte Maschinencode aussehen würde:

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

Sie kommen zu dem Schluss, dass die Schleife nicht abgewickelt wurde, da ein Codeteil schneller als ein anderes Codeteil ausgeführt wird. Selbst wenn dies der Fall wäre, könnten Sie den Laufzeitunterschied feststellen, da Sie verschiedene Implementierungen vergleichen.

Wenn Sie mehr Sicherheit gewinnen möchten, gibt es den Jitwatch- Analysator / Visualisierer der tatsächlichen Jit-Operationen, einschließlich Maschinencode (Github) (Präsentationsfolien) . Wenn es irgendwann etwas zu sehen gibt, würde ich meinen eigenen Augen mehr vertrauen als jeder Meinung darüber, was JIT im Allgemeinen tun kann oder nicht, da jeder Fall seine Besonderheiten hat. Hier ärgern sie sich über die Schwierigkeit, allgemeine Aussagen für bestimmte Fälle in Bezug auf JIT zu treffen, und bieten einige interessante Links.

Da Ihr Ziel eine minimale Laufzeit ist, ist das a && b && c ...Formular wahrscheinlich das effizienteste, wenn Sie sich nicht auf die Hoffnung auf das Abrollen von Schleifen verlassen möchten, zumindest effizienter als alles andere, was bisher vorgestellt wurde. Aber das kann man nicht generisch haben. Mit der funktionalen Zusammensetzung von java.util.Function entsteht wieder ein enormer Overhead (jede Funktion ist eine Klasse, jeder Aufruf ist eine virtuelle Methode, die versendet werden muss). In einem solchen Szenario ist es möglicherweise sinnvoll, die Sprachstufe zu untergraben und zur Laufzeit benutzerdefinierten Bytecode zu generieren . Andererseits erfordert eine &&Logik auch eine Verzweigung auf Bytecode-Ebene und kann if / return entsprechen (was auch nicht ohne Overhead generiert werden kann).