Java Lambdas 20 mal langsamer als anonyme Klassen

Question

Ich habe eine Menge Fragen über Java Lambdas Leistung gesehen, aber die meisten von ihnen gehen wie "Lambdas sind etwas schneller, aber langsamer bei der Verwendung von Verschlüsse" oder "Warm-up vs Ausführungszeiten sind anders "oder andere solche Dinge.

Allerdings traf ich hier eine ziemlich seltsame Sache. Betrachten this LeetCode problem:

einen Satz von nicht überlappenden Intervallen gegeben, legt ein neues Intervall in die Intervalle (merge falls erforderlich).

Sie können davon ausgehen, dass die Intervalle zunächst nach ihren Startzeiten sortiert wurden.

Das Problem wurde hart markiert, also nahm ich an, dass ein linearer Ansatz nicht das ist, was sie dort wollen. Also entschied ich mich, eine clevere Möglichkeit zu finden, die binäre Suche mit Änderungen an der Eingabeliste zu kombinieren. Nun ist das Problem beim Ändern der Eingabeliste nicht sehr klar - es heißt "Einfügen", obwohl die Signatur einen Verweis auf die Liste zurückgeben muss, aber das ist für jetzt gleichgültig. Hier ist der vollständige Code, aber nur die ersten Zeilen sind für diese Frage relevant. Ich behalte den Rest hier einfach so, dass jeder kann es versuchen:

public List<Interval> insert(List<Interval> intervals, Interval newInterval) { 
    int start = Collections.binarySearch(intervals, newInterval, 
             (i1, i2) -> Integer.compare(i1.start, i2.start)); 
    int skip = start >= 0 ? start : -start - 1; 
    int end = Collections.binarySearch(intervals.subList(skip, intervals.size()), 
             new Interval(newInterval.end, 0), 
             (i1, i2) -> Integer.compare(i1.start, i2.start)); 
    if (end >= 0) { 
     end += skip; // back to original indexes 
    } else { 
     end -= skip; // ditto 
    } 
    int newStart = newInterval.start; 
    int headEnd; 
    if (-start - 2 >= 0) { 
     Interval prev = intervals.get(-start - 2); 
     if (prev.end < newInterval.start) { 
      // the new interval doesn't overlap the one before the insertion point 
      headEnd = -start - 1; 
     } else { 
      newStart = prev.start; 
      headEnd = -start - 2; 
     } 
    } else if (start >= 0) { 
     // merge the first interval 
     headEnd = start; 
    } else { // start == -1, insertion point = 0 
     headEnd = 0; 
    } 
    int newEnd = newInterval.end; 
    int tailStart; 
    if (-end - 2 >= 0) { 
     // merge the end with the previous interval 
     newEnd = Math.max(newEnd, intervals.get(-end - 2).end); 
     tailStart = -end - 1; 
    } else if (end >= 0) { 
     newEnd = intervals.get(end).end; 
     tailStart = end + 1; 
    } else { // end == -1, insertion point = 0 
     tailStart = 0; 
    } 
    intervals.subList(headEnd, tailStart).clear(); 
    intervals.add(headEnd, new Interval(newStart, newEnd)); 
    return intervals; 
} 

Dies funktionierte gut und wurde angenommen, aber mit 80 ms Laufzeit, während die meisten Lösungen waren 4-5 ms und einige 18-19 ms. Als ich nach ihnen suchte, waren sie alle linear und sehr primitiv. Nicht etwas, was man von einem "hart" genannten Problem erwarten würde.

Aber hier kommt die Frage: meine Lösung ist auch im schlimmsten Fall linear (weil add/clear Operationen lineare Zeit sind). Warum ist es dass langsamer? Und dann tat ich das:

Comparator<Interval> comparator = new Comparator<Interval>() { 
     @Override 
     public int compare(Interval i1, Interval i2) { 
      return Integer.compare(i1.start, i2.start); 
     } 
    }; 
    int start = Collections.binarySearch(intervals, newInterval, comparator); 
    int skip = start >= 0 ? start : -start - 1; 
    int end = Collections.binarySearch(intervals.subList(skip, intervals.size()), 
             new Interval(newInterval.end, 0), 
             comparator); 

Von 80 ms bis zu 4 ms! Was ist denn hier los? Leider habe ich keine Ahnung, welche Tests LeetCode unter welcher Umgebung durchführt, aber trotzdem ist es nicht 20 mal zu viel?

Answer 1

Sie haben offensichtlich den ersten Initialisierungsaufwand für Lambda-Ausdrücke. Wie bereits in den Kommentaren erwähnt, werden die Klassen für Lambda-Ausdrücke zur Laufzeit generiert und nicht aus dem Klassenpfad geladen.

Die Generierung ist jedoch nicht die Ursache für die Verlangsamung. Schließlich kann das Erzeugen einer Klasse mit einer einfachen Struktur sogar schneller sein als das Laden der gleichen Bytes von einer externen Quelle. Und die innere Klasse muss auch geladen werden. Wenn die Anwendung jedoch noch keine Lambda-Ausdrücke verwendet hat, muss sogar das Framework zum Generieren der Lambda-Klassen geladen werden (die aktuelle Implementierung von Oracle verwendet ASM unter der Haube). Dies ist die eigentliche Ursache für die Verlangsamung, das Laden und die Initialisierung von einem Dutzend intern verwendeter Klassen, nicht des Lambda-Ausdrucks selbst.

Sie können dies leicht überprüfen. In Ihrem aktuellen Code, der Lambda-Ausdrücke verwendet, haben Sie zwei identische Ausdrücke (i1, i2) -> Integer.compare(i1.start, i2.start). Die aktuelle Implementierung erkennt dies nicht (tatsächlich liefert der Compiler auch keinen Hinweis). Hier werden also zwei Lambda-Instanzen erzeugt, die sogar unterschiedliche Klassen haben.Sie können den Code Refactoring nur einen Komparator, ähnlich wie Ihre innere Klasse Variante haben:

final Comparator<? super Interval> comparator 
    = (i1, i2) -> Integer.compare(i1.start, i2.start); 
int start = Collections.binarySearch(intervals, newInterval, comparator); 
int skip = start >= 0 ? start : -start - 1; 
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()), 
            new Interval(newInterval.end, 0), 
            comparator); 

Sie werden keine signifikanten Leistungsunterschied bemerken, da es nicht die Anzahl der Lambda-Ausdrücke, was zählt, sondern nur die Klasse Laden und Initialisieren des Frameworks, was genau einmal passiert.

Sie können es sogar max durch Einfügen zusätzlicher Lambda-Ausdrücke aus wie

final Comparator<? super Interval> comparator1 
    = (i1, i2) -> Integer.compare(i1.start, i2.start); 
final Comparator<? super Interval> comparator2 
    = (i1, i2) -> Integer.compare(i1.start, i2.start); 
final Comparator<? super Interval> comparator3 
    = (i1, i2) -> Integer.compare(i1.start, i2.start); 
final Comparator<? super Interval> comparator4 
    = (i1, i2) -> Integer.compare(i1.start, i2.start); 
final Comparator<? super Interval> comparator5 
    = (i1, i2) -> Integer.compare(i1.start, i2.start); 

ohne eine Verlangsamung zu sehen. Es ist wirklich der anfängliche Overhead des allerersten Lambda-Ausdrucks der gesamten Laufzeit, den Sie hier bemerken. Da Leetcode selbst vor dem Eingeben des Codes offensichtlich keine Lambda-Ausdrücke verwendet, deren Ausführungszeit gemessen wird, addiert sich dieser Overhead hier zu Ihrer Ausführungszeit.

Siehe auch “How will Java lambda functions be compiled?” und “Does a lambda expression create an object on the heap every time it's executed?”