Java lambdas 20 fois plus lent que les classes anonymes

J'ai vu beaucoup de questions à propos de Java lambdas de la performance, mais la plupart d'entre eux vont comme des "Lambdas sont légèrement plus rapide, mais plus lent lors de l'utilisation de fermetures" ou "Warm-up contre les temps d'exécution sont différentes", ou d'autres choses.

Cependant, j'ai frappé un peu étrange chose ici. Envisager cette LeetCode problème:

Donné un ensemble de non-chevauchement des intervalles, insérer un nouvel intervalle en
les intervalles (fusion si nécessaire).

Vous pouvez supposer que les intervalles ont été d'abord triées en fonction de
leur temps de départ.

Le problème a été marqué dur, donc je suppose qu'une approche linéaire n'est pas ce qu'ils veulent là. J'ai donc décidé de venir avec un astucieux moyen de combiner la recherche binaire avec les modifications apportées à la liste d'entrée. Maintenant, le problème n'est pas très clair sur la modification de la liste d'entrée—il dit "insérer", même si la signature nécessite de retourner une référence à la liste, mais jamais l'esprit pour l'instant. Voici le code complet, mais seulement les premières lignes sont concernées par cette question. Je vais garder le reste ici simplement pour que tout le monde peut l'essayer:

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

Cela a bien fonctionné et j'ai été accepté, mais avec 80 ms de l'exécution, alors que la plupart des solutions étaient de 4 à 5 ms et certains 18-19 mme. Quand j'ai regardé en eux, ils étaient tous linéaire et très primitif. Pas quelque chose que l'on pourrait attendre d'un problème tagged "dur".

Mais ici se pose la question: ma solution est également linéaire au pire des cas (car ajouter/effacer des opérations sont en temps linéaire). Pourquoi est-il que plus lent? Et puis, j'ai fait ceci:

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

De 80 ms 4 ms! Ce qui se passe ici? Malheureusement je n'ai aucune idée de quel genre de tests LeetCode pistes ou en vertu de quel environnement, mais encore, n'est-ce pas 20 fois trop?