Java lambdas 20 volte più lento delle classi anonime

Question

Qui ho visto molte domande sulle prestazioni lambda di Java, ma la maggior parte di esse è simile a "Lambdas è leggermente più veloce, ma diventa più lento quando si usano chiusure" o "Warm-up vs i tempi di esecuzione sono diversi "o altre cose simili.

Tuttavia, ho trovato una cosa piuttosto strana qui. Consideriamo this LeetCode problem:

Dato un insieme di intervalli non sovrapposti, inserire un nuovo intervallo in intervalli (merge se necessario).

Si può supporre che gli intervalli siano stati inizialmente ordinati in base allo loro orari di inizio.

Il problema è stato taggato con difficoltà, quindi ho assunto che un approccio lineare non è quello che vogliono lì. Così ho deciso di inventare un modo intelligente per combinare la ricerca binaria con le modifiche alla lista di input. Ora il problema non è molto chiaro sulla modifica della lista di input, dice "insert", anche se la firma richiede di restituire un riferimento alla lista, ma non importa per ora. Ecco il codice completo, ma solo le prime poche righe sono rilevanti per questa domanda. Sto mantenendo il resto qui solo in modo che chiunque può provare:

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

Questo ha funzionato bene, ma ho accettato, ma con 80 ms tempo di esecuzione, mentre la maggior parte delle soluzioni erano 4-5 ms e alcuni 18-19 ms. Quando li ho visti, erano tutti lineari e molto primitivi. Non qualcosa che ci si aspetterebbe da un problema taggato "difficile".

Ma ecco che arriva la domanda: la mia soluzione è anche lineare nel caso peggiore (perché le operazioni di aggiunta/cancellazione sono di tempo lineare). Perché è che è più lento? E poi ho fatto questo:

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); 

Da 80 ms fino a 4 ms! Cosa sta succedendo qui? Sfortunatamente non ho idea di che tipo di test esegua LeetCode o in quale ambiente, ma non è 20 volte troppo?

Answer 1

Si sta ovviamente verificando il sovraccarico di inizializzazione per la prima volta delle espressioni lambda. Come già menzionato nei commenti, le classi per le espressioni lambda vengono generate in fase di esecuzione anziché essere caricate dal percorso della classe.

Tuttavia, l'essere generato non è la causa del rallentamento. Dopo tutto, la generazione di una classe con una struttura semplice può essere persino più veloce del caricamento degli stessi byte da una fonte esterna. E anche la classe interiore deve essere caricata. Ma quando l'applicazione non ha usato espressioni lambda prima, deve essere caricato anche il framework per generare le classi lambda (l'attuale implementazione di Oracle usa ASM sotto il cofano). Questa è la vera causa del rallentamento, del caricamento e dell'inizializzazione di una dozzina di classi usate internamente, non l'espressione lambda stessa.

È possibile verificare facilmente questo. Nel tuo codice corrente che utilizza espressioni lambda, hai due espressioni identiche (i1, i2) -> Integer.compare(i1.start, i2.start). L'attuale implementazione non lo riconosce (in realtà, il compilatore non fornisce nemmeno un suggerimento). Quindi qui vengono generate due istanze lambda che hanno classi anche diverse.È possibile refactoring del codice per avere un solo confronto, simile alla vostra variante di classe interna:

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); 

Non si dovrebbe notare alcuna differenza significativa delle prestazioni, in quanto non è il numero di espressioni lambda che conta, ma solo la classe caricamento e inizializzazione del framework, che avviene esattamente una volta.

È anche possibile max fuori inserendo le espressioni lambda aggiuntivi come

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); 

senza vedere alcun rallentamento. È davvero l'overhead iniziale della primissima espressione lambda dell'intero runtime che stai notando qui. Poiché apparentemente il codice stesso non utilizza le espressioni lambda prima di inserire il codice, il cui tempo di esecuzione viene misurato, questo sovraccarico aggiunge al tempo di esecuzione qui.

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